算法，一门既不容易入门，也不容易精通的学问。但是作为一条有梦想的咸鱼，我决定努力一大把。

栈与队列分别是两种数据结构，不同语言对于栈和队列有着不同的声明，在 java 中 Stack 类是继承自 Vector 集合的子类，Queue 则是以接口形式存在，常用的其实现类是 LinkedList 这个双向队列。在java的标准模版库也是有这两个数据结构定义的具体类的。

栈数据结构的特点是 FILO（first in last out） 即先进后出，队列则是 FIFO（first in first out）即先进先出。

日常现实生活中处处可见，比如，学生在食堂买饭、在公交车上车排队等。这些排队规律都是先来先处理事件，都不能插队，要遵守一定的规范。其实。我们常用的计算机也有队列，操作系统中的进程、资源等待队列、作业队列等等。

​​​​​​

一、队列的概念：

　　队列（简称作队，Queue）也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作在其另一端进行删除操作。

队列中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。

下图是一个依次向队列中插入数据元素a0,a1,...,an-1后的示意图：

 

1、顺序队列的“假溢出”：

上图中，front指针指向队头元素，rear指针指向队尾元素的下一个位置。图(d)中b、c、d出队后，front指针指向元素e，rear指针在数组外面。假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经被占用，再向后加就会产生数组越界的错误，可实际上队列在下标为0、1、2、3、4的地方还是空闲的，我们把这种现象叫做“假溢出”。

2、循环顺序队列：

    所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种逻辑上首尾相连的顺序存储结构称为循环队列：

        当队列空时，条件就是from = rear,当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。 如下图所示，我们就认为此队列已经满了，

 

由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1) %QueueSize == front (取模“%的目的就是为了整合rear与front大小为一个问题)。

比如上面这个例子， QueueSize = 5，当 front=0，而 rear=4, (4+1) %5 = 0，所以此时队列满。再比如，front = 2而rear =1。(1 + 1) %5 = 2，所以此时 队列也是满的。而对于下图, front = 2而rear= 0, (0+1) %5 = 1，1!=2,所以此时队列并没有满。

另外，当rear > front时，此时队列的长度为rear—front。但当rear < front时，队列长度分为两段，一段是QueueSize-front，另一段是0 + rear，加在一起，队列长度为rear-front + QueueSize，

因此通用的计算队列长度公式为：

(rear—front + QueueSize) % QueueSize

总结

队空条件：front == rear

队满条件：(rear+1) %QueueSize == front

队列长度：(rear—front + QueueSize) % QueueSize

循环队列基本操作的实现

接口类

public interface IQueue {
    public void clear();
    public boolean isEmpty();
    public int length();
    public Object peek();
    public void offer(Object x)throws Exception;
    public Object poll();
    public void display();
}

入队操作

    public void offer(Object x) throws Exception {
        if ((rear+1)%queueElem.length==front)            //队列满
            throw  new Exception("队列已满");            //抛出异常
        else {
            queueElem[rear]=x;
                                          //x存入rear所指数组存储位置,使其成为队尾
            rear=(rear+1)%queueElem.length;            //修改队尾指针
        }
    }

出队

 public Object poll() {
        if (front==rear)
        return null;
        else{
            Object t=queueElem[front];
            front=(front+1)%queueElem.length;
            return t;                        //返回队列的队首元素
        }

代码总结

public class CircleSqQueue implements IQueue{
    private  Object[] queueElem;//队列存储空间
    private  int front;         //队首的引用
    private int rear;      //队尾 的引用

    public CircleSqQueue(int maxSize) {
        front=rear=0;                  //队尾、队首初始化尾0
      queueElem = new Object[maxSize];//尾队列分配maxSize个储存单元
    }

    @Override
    public void clear() {
        front=rear=0;//
    }

    @Override
    public boolean isEmpty() {
        return front==rear;
    }

    @Override
    public int length() {
        return (rear-front+queueElem.length)%queueElem.length;
    }
        //读取队首元素
    @Override
    public Object peek() {
        if (front==rear)

        return null;
        else
            return queueElem[front];
    }
//入队操作
    @Override
    public void offer(Object x) throws Exception {
        if ((rear+1)%queueElem.length==front)
            throw  new Exception("队列已满");
        else {
            queueElem[rear]=x;
            //x存入rear所指数组存储位置,使其成为队尾
            rear=(rear+1)%queueElem.length;//修改队尾指针
        }
    }

    @Override
    public void display() {
        //简单的遍历
        if(!isEmpty()) {
            for (int i=front;i!=rear;i=(i+1)%queueElem.length)
                System.out.print(queueElem[i].toString()+"\t");
        }else{
        }
        //思路从front开始遍历，遍历时候要遍历多少个元素就可以了
        //要求出当前队列的个数
        
    }
//出队操作
    @Override
    public Object poll() {
        if (front==rear)
        return null;
        else{
            Object t=queueElem[front];
            front=(front+1)%queueElem.length;
            return t;        //返回队列的队首元素
        }
        
        }
    }

用循环加switch  case写个测试类，测试成功！