Java基础数据结构之队列

一.什么是队列

队列是一种先进先出的数据结构，也就是从左边进从右边出，或者说，只允许在一端插入元素，在另一端删除元素

进行插入操作的一端称为队尾（tail/rear），删除操作的一段称为队头（front/head）。

二.队列的模拟实现

队列应该用链表来存放元素，因为要对头尾进行操作

成员变量：

入队：

首先要判断是否为第一次插入元素，因为要涉及到更新last的值。注意用到了尾插法

出队：

有三种情况，第一种是队列为空，第二种是只有一个元素，第三种是一般状态。注意一般状态下，不要仅仅把first往后移，虽然这样也可以，但最好勤快一点，把前后断的更干净些，不要都交给jvm去做

获取队首元素：

三.队列的使用

队列queue是一个接口

主要使用的就是它的offer方法，poll方法和peek方法

实例化队列对象：

队列的底层是链表，所以实例化队列时一般用LinkedList

有一个问题：能否通过LinkedList中的迭代器来遍历队列？不可以，向上转型的queue访问不到子类独有的方法！！

四.循环队列

循环队列的大小是固定的front表示队头，rear表示队尾，从队尾放元素，每放一个元素，rear就向前移一位，芙蓉厅始终指向第一个元素，出队时front就像前移动

我们可以发现，当队列为空时，rear和front在同一个位置，队列全满时，rear和front也指向同一位置，那怎么判断空与满呢？

1.如何判断空与满

方案一：使用usedsize来记录

方案二：浪费一个空间来表示满

比如数组有9个空，我们只使用8个空，当8个空全都使用上时rear和front就差一步，此时要是再像插入元素，rear就得再往前走，就和front相遇了，说明在放这个元素之前已经把8个空用完了，已经是满的状态了，所以这个元素不能放进去了。

而要是要删除一个元素，front往前走了一步，发现和rear相遇了，就说明空了。

所以说：rear向前走后与front相遇，就是满；front向前走后与rear相遇，就是空

也就是：

队列为空时的条件：rear=front

队列为满时的条件：rear+1=front

但仅仅这样是不对的，假设数组长度为7，现在已经放了6个元素，其实已经满了，此时front=0，rear=6，rear下一步本应是0，但rear+1=7了，不等于0，所以上面的写法不对，而应该为

队列为空时的条件：rear=front

队列为满时的条件：（rear+1）%arr.length=front

方案三：定义一个标记

设置一个flag，初始值为false

当入队时，rear向后移，flag=true；出队时front向后移，flag=false

当队列为空时front=rear并且flag=false（因为最后一步操作肯定是出队）

当队列为满时front=rear并且flag=true（因为最后一步操作肯定是入队）

2.循环队列的代码实现

class MyCircularQueue {
    public int []arr;
    public int front=0;
    public int rear=0;
    public int size;
    public MyCircularQueue(int k) {
        this.arr=new int[k];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        arr[rear]=value;
        rear=(rear+1)%arr.length;
        size++;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front=(front+1)%arr.length;
        size--;
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return arr[front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        else if(rear==0){
            return arr[arr.length-1];
        }
        else {
            return arr[rear - 1];
        }
    }
    
    public boolean isEmpty() {
        return size==0;
    }
    
    public boolean isFull() {
        return size==arr.length;
    }
}

我这里判断空与满用到的是size

首先enQueue是向队列中插入一个元素，这里就是向队尾插入元素，所以就是在rear下标插入元素，然后rear++，但这样更新rear的值不可以，比如arr.length=7，此时rear指向了6下标，那么rear加1就是7了，就是数组越界了，当rear是6时，表示它已经到了数组末尾，该往回返了，也就是应该到0下标，所以就有了(rear+1)%arr.length。但要判断是否为满。

然后是deQueue，是从队首删除一个元素，直接（front+1)%arr.length即可。还是注意是否空。但注意，要是存放的元素是某个引用类型，就要将front所指位置置为空之后再更新

Front是从队首获取元素，Rear是从队尾获取元素。注意从队尾获取元素的操作。当不为空时，一般情况下只要获取rear-1位置的元素即可，但有一种情况就是rear=0，此时rear-1=-1，下标越界了，所以rear=0时，要获取数组末尾的元素。

五.双端队列（Deque）

双端队列就是允许俩端都可以进行入队和出队操作的队列，Deque是一个接口，其实现类是LinkedList、ArrayDeque、LinkedBlockingDeque。首先LinkedList底层是链表，可以在两头进行插入删除操作，ArrayDeque底层是数组，是顺序表，也可进行。LinkedList最常用。下面是它的一些方法：