定义

队列是一种特殊的线性表，只能在头尾两端进行操作。

• 队尾（rear）：只能从队尾添加元素，一般叫做enQueue，入队
• 队头（front）：只能从队头移除元素，一般叫做deQueue，出队
• 先进先出原则，First In First Out，FIFO

队列的接口设计（使用双向链表）

PS：出队是从队列（Queue）中删除队头元素，而获取队头元素仅仅是为了访问，不删除。

队列（Queue）的内部实现是否可以直接利用以前学习过的数据结构呢？答案当然是可以。那使用链表还是数组呢？

我为什么要问这样一个问题呢？当然是为了复杂度而考虑。

因为队列（Queue）只能在队头或者队尾操作。对于数组来说，移除队尾元素复杂度是O(1)，但是移除队头元素，复杂度就是O(n)了。单向链表移除队尾元素复杂度是O(n)。所以，这里最好的选择就是双向链表！！

因为，双向链表操作头结点和尾结点都是复杂度是O(1)，非常适合作为队列（Queue）的底层框架。

下面我们来设计队列的接口，看看是怎么利用双向链表这一数据结构的。

• 首先队列（Queue）就是使用双向链表，只不过封装在队列（Queue）的函数内。让调用者觉得是在调用队列（Queue），本质是调用双向链表。

public class Queue<Type> {
    private List<Type> list = new DoubleLinkedList<>();
	//------
}

• 调用size()函数，返回队列的长度。我们这样设计，队列就是双向链表，因此直接清空双向链表就行了。

/**
 * 返回队列的长度
 * @return
 */
public int size(){
    return list.size();
}

• 调用isEmpty()，判断队列是否为空。那就是判断双向链表是否为空

/**
 * 判断队列是否为空
 * @return
 */
public boolean isEmpty() {
    return list.isEmpty();
}

• 调用enQueue(Type element)，执行入队操作。入队，只能从队尾入队，其实就是向队尾添加元素，那就是向链表尾部添加元素，调用双向链表的append(element)即可。

/**
 * 入队，只能从队尾入队，其实就是向队尾添加元素
 * @param element
 */
public void enQueue(Type element){
    list.append(element);
}

• 调用deQueue()，完成队头元素出队操作。出队，只能从队头弹出元素，其实就是删除index=0处的节点，并返回该值

/**
 * 出队，只能从队头弹出元素，其实就是删除index=0处的节点，并返回该值
 * @return
 */
public Type deQueue(){
    Type front = list.remove(0);
    return front;
}

• 调用front()函数，获得队头元素。本质就是访问链表的头结点。

/**
 * 获得队头元素，也就是访问队头元素，本质就是访问链表的头结点
 * @return
 */
public Type front(){
    return list.get(0);
}

• 调用clear()函数，清空队列。本质就是清空队列所依赖的双向链表。

/**
 * 清空队列，因为队列就是双向链表，所以本质上就是清空双向链表
 */
public void clear(){
    list.clear();
}

下面我们来测试一下队列的入队和出队情况。

public class Main {
    public static void main(String[] args) {

        Queue<Integer> queue = new Queue<>();

		//先依次入队，11先入，最后44再入
        queue.enQueue(11);
        queue.enQueue(22);
        queue.enQueue(33);
        queue.enQueue(44);

		//不断地出队，并打印出队元素
        while (!queue.isEmpty()){
            System.out.println(queue.deQueue());
        }

    }
}

可以看出，先入的11，先出了。至此队列设计完成。

用栈实现队列的接口设计

栈（Stack）是后进先出，队列（Queue）则是先进先出。怎么用栈来实现队列的接口设计呢？？

准备两个栈：inStack和outStacK

• 入队时，push元素到inStack
• 出队时，有两种情况需要判断：如果outStack为空，那就将inStack里的所有元素逐一弹出，push到outStack。然后从outStack中弹出栈顶元素完成此次的出队；如果outStack不为空，说明刚才inStack已经弹完元素到outStack，并且outStack的栈顶元素永远都是当前队列的队头。

我们来模拟一下这个过程：

1、11 22 33依次入栈（在调用者眼里就是依次入队）

2、此刻我要出队，那么应该先出11才对。但是只依靠inStack恐怕只能出队33，所以借助outStack，把inStack的元素依次弹出到outStack。如下所示，这时outStack就符合队列的要求了

3、此刻，我们弹出outStack的栈顶元素（就相当于完成出队的操作，因为出队的是11，符合队列特性）

这只是第一种情况，当outStack为空时的情况。当outStack不为空呢？

4、就如下图所示，现在outStack不为空，我还要出队。那就不用把inStack里的元素依次弹到outStack了。因为outStack都不为空了，我就继续出队就行了。

假设有如下操作：11入队，22入队，出队，33入队，出队

1、（11入队，22入队）入队的时候只将元素压入到inStack中

2、要出队了，判断outStack是否为空，如果为空，就把inStack逐一弹到outStack。显然现在outStack为空

3、11出队完成，符合队列性质

4、现在33要入队了，那就无脑push到inStack中就行了。

5、现在我要出队，怎么做？出队其做判断，如果outStack不为空，就直接弹出outStack的栈顶元素就行。

4、 我现在又要出队。出队前判断，如果为空，就把inStack逐一弹到outStack。显然现在outStack为空。然后把33弹到outStack后，再弹出。就完成了模拟队列的过程

总结用栈设计队列的过程：入栈（入队）不用做任何判断，无脑入inStack即可。出队（出栈）要做判断，判断当前outStack是否为空，如果为空就逐一把inStack元素弹到outStack中，然后outStack弹出栈顶完成出队；如果不为空，直接从outStack弹出栈顶完成出队。

接下来设计代码：

几个关键的地方需要注意。

• 需要声明两个栈，一个inStack，一个outStack

public  Stack<Type> inStack = new Stack<>();
private Stack<Type> outStack = new Stack<>();

• 判断队列是否为空，需要两个栈同时判断，都不为空才不为空，一个为空队列就为空

/**
 * 判断队列是否为空
 * @return
 */
public boolean isEmpty() {
    return inStack.isEmpty() && outStack.isEmpty();
}

• 求队列的size，需要把两个栈的size加起来

/**
 * 返回队列的长度
 * @return
 */
public int size(){
    return inStack.size() + outStack.size();
}

• 入队只需要管inStack即可

/**
 * 入队，只能从队尾入队，其实就是向队尾添加元素
 * @param element
 */
public void enQueue(Type element){
    inStack.push(element);
}

• 最重要的来了！！出队：需要判断outStack是否为空，然后最后弹出outStack的栈顶元素（也就相当于是出队队头元素）

/**
 * 出队，只能从队头弹出元素，其实就是删除index=0处的节点，并返回该值
 * @return
 */
public Type deQueue(){

    if(!outStack.isEmpty()){
        return outStack.pop();
    }else {
        while (!inStack.isEmpty()){
            outStack.push(inStack.pop());
        }
        return outStack.pop();
    }

}

• 清空，那就需要把两个栈都清空

/**
 * 清空队列，
 */
public void clear(){
    inStack.clear();
    outStack.clear();
}

• 获取队头元素跟出队一样，只不过最终返回的是队头元素且不需要出队

/**
 * 获得队头元素，
 * @return
 */
public Type front(){
    if(!outStack.isEmpty()){
        return outStack.top();
    }else {
        while (!inStack.isEmpty()){
            outStack.push(inStack.pop());
        }
        return outStack.top();
    }
}

整个利用栈实现队列的程序如下：

public class QueueForStack<Type> {

    public  Stack<Type> inStack = new Stack<>();
    private Stack<Type> outStack = new Stack<>();

    /**
     * 返回队列的长度
     * @return
     */
    public int size(){
        return inStack.size() + outStack.size();
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    /**
     * 入队，只能从队尾入队，其实就是向队尾添加元素
     * @param element
     */
    public void enQueue(Type element){
        inStack.push(element);
    }

    /**
     * 出队，只能从队头弹出元素，其实就是删除index=0处的节点，并返回该值
     * @return
     */
    public Type deQueue(){

        if(!outStack.isEmpty()){
            return outStack.pop();
        }else {
            while (!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
            return outStack.pop();
        }

    }

    /**
     * 获得队头元素，
     * @return
     */
    public Type front(){
        if(!outStack.isEmpty()){
            return outStack.top();
        }else {
            while (!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
            return outStack.top();
        }
    }

    /**
     * 清空队列，
     */
    public void clear(){
        inStack.clear();
        outStack.clear();
    }

}

下面我们进行测试：

public class Main {
    public static void main(String[] args) {

        QueueForStack<Integer> queue = new QueueForStack<>();

        queue.enQueue(11);
        queue.enQueue(22);
        queue.enQueue(33);
        queue.enQueue(44);


        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());

    }
}

可以看出，完全实现了队列的先入先出。

双端队列（Deque）

双端队列（Deque） 是能在头尾两端添加、删除的队列！（普通队列智能在队尾添加元素，队头删除元素）

相比较于普通队列，双端队列（Deque）可以从队尾入队，也可以从队头入队；可以从队头出队，也可以从队尾出队。因此，接口就多了几个而已！

原理还是用双向链表实现。只不过从队尾入队就是list.append(element)，从队头入队就是list.add(0, element)而已。从队头出队list.remove(0)，那从队尾出队就是list.remove(size-1)呗。获取队头元素就是list.get(0)，那获取队尾元素就是list.get(szie-1)呗。

这里就不一一实现了。

循环队列（Circle Queue）

其实队列不仅可以使用双向链表、栈实现，还可以使用动态数组实现。并且各项接口也可以优化到O(1)复杂度。

本节介绍的就是用动态数组实现的队列，叫做：循环队列。下面介绍一下循环队列到底是怎么回事。

循环队列用动态数组实现，所以本质就是一个数组。只不过呢，这个数组有一个特性：有一个队头指针（front）一直记录着当前队头的下标索引。

当我删除队头元素时，队头指针要挪到下一个队头处。（不像动态数组，我删除数组头元素，后面的元素还要向前移动）。循环队列只需要确定谁是队头元素就可以。

然后我不断地向队尾添加元素，一直添加到数组尾部（77）。按照动态数组的惯例，再次添加就需要动态扩容了。但是我输循环队列，我要查看当前数组容量是不是满了，如果不满，我就把（88）添加到索引为0的地方，形成一种循环的感觉。

接下来我们实现一下循环队列的接口：

• 首先，循环队列依靠数组，并且有一个front记录队头的位置，还要有队列的size。既然有数组，那就得为数组分配存储空间，还有要初始空间的大小。因此，循环队列所需要的成员如下：

public class CircleQueue<Type> {

    private int size;
    private int front;
    private Type elements[];
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 默认数组长度为10
     */
    @SuppressWarnings("unchecked")
    public CircleQueue() {
        elements = (Type[]) new Object[DEFAULT_CAPACITY];
    }
}

• size()和isEmpty()跟数组一样就行

/**
 * 返回队列的长度，并不是数组的容量，而是存储在数组中队列的长度
 * @return
 */
public int size(){
    return size;
}

/**
 * 判断队列是否为空
 * @return
 */
public boolean isEmpty() {
    return size == 0;
}

• 入队！也就是向目前队列的队尾添加元素，也就是向数组的某一个索引处添加元素。怎么确定这个索引呢？

例如上图：如果向4、5、6处添加元素，似乎只需要front + size就能确定对应的数组索引。因为front一直记录着队头的索引，size是队列的长度，也就是现在数组中元素的个数。入了三个元素（55,66,77），如下所示：

此时，我还要入队，按照循环队列的分析，应该转过头来，入在数组的index=0处。那么，front + size是否还可以确定这个索引呢？front + size = 2 + 5 = 7，显然数组下标越界。但是又想回到数组index=0处，这时只需要模上数组长度就行了

也就是说，队尾的位置通过(front + size) % elements.length就可以唯一确定！！！下面时入队的接口设计：

/**
 * 入队，只能从队尾入队，其实就是向队尾添加元素
 * 由于是循环队列，因此当入队到了数组的末尾时还要入队，front + size这个索引就不准确了，此时必须模上数组的长度，回到数组头
 * 因此：(front + size) % elements.length这个索引才是可以应对循环队列的
 * @param element
 */
public void enQueue(Type element){
    elements[(front + size) % elements.length] = element;
    size++;
}

• 出队！那就是删除队头元素。因为front不断地记录队头在数组中的位置，因此出队之后，front要++，同时size要--。但是！front还存在另一种情况：

如下图所示，（目前队列有两个元素，队头是55，队尾是66）此时，还要出队。55就没了，front++？front直接变成7了，数组越界了就。所以还要转过头来，将front移动到66处。所以front的下一步不能只是front+1，还要模上数组长度，也就是(front + 1) % elements.length。

所以，出队的实现如下：

/**
 * 出队，只能从队头弹出元素，并返回该值
 * 由于在数组中使用一个索引记录着队头，因此这个队头要实时移动
 * 当移动到数组尾部时，这个队头还要循环回来，移动到数组头部，因此这块也需要模上数组长度
 * @return
 */
public Type deQueue(){
    Type front_element = elements[front];
    elements[front] = null;
    front = (front + 1) % elements.length;
    size--;
    return front_element;
}

• 获取队头元素，那就取出队头索引处的数组值即可。

/**
 * 获得队头元素，也就是访问队头元素，那就是直接访问front处的数组内容
 * @return
 */
public Type front(){
    return elements[front];
}

至此，一个不需要扩容版的循环队列就设计好了。嗯？我为什么要这么说话？那是因为在刚才入队的时候，还可能会发生下面的情况

当我入队完99之后，我还想入队。数组此时满了，无论如何，我都没法入队了，否则就覆盖掉原先的值了。这时候怎么办？难道循环队列的长度要受到数组长度的限制？答案当然是不可以！！！！

因此，我们要在此基础上，为数组赋予动态扩容的功能。如下图所示：假设，我们的数组容量是3，此时入队满了，所以要申请一块更大的存储空间。问题的关键是：如何将原数组内的元素移动到新数组中？

回忆数组的动态扩容：将原数组元素按照对应索引一个一个移动到新数组。但是，本质上我们是队列，而不是数组。因此，按照索引一个一个移动到新数组，队头和队尾就变了。所以我们要按照队列的索引，一个一个移动的新数组。如下图所示：

将队列按照从头到尾的顺序移动到新数组，并将front置位0。相对于以前来说，我们放到新数组的索引跟以前一样，从0开始一直到元素个数；但是，原数组的索引必须要遵循循环队列的性质了。也就是说，新数组的index=i处要放原数组index=？。

新数组的i对应的是原数组的i+front，比如新数组的0处，对应放原数组的front处；新数组的1处，对应放原数组的front+1。

所以，新数组的i处对应放原数组的i+front。但是循环队列，要模上数组容量，这里不多说。所以，放在新数组index=i处的元素，对应原数组index= (i + front) % elements.length处。最大的改动就是这，如下所示：

for (int i = 0;i < size; i++){
    //把原来数组的队列，按照队列的顺序放到新的存储空间
    // newArrayPointer[i] = elements[i];//之前动态数组的移动法
    newArrayPointer[i] = elements[(i + front) % elements.length];
}

强调：index= (i + front) % elements.length其实就是队列中的元素，在数组中的真实索引！！！！！！

并且，把队列按照队头到队尾放在新数组时，队头就是从0开始了。所以，新数组中的新队列，front要置位0。整体代码如下：

/**
 * 保证扩容之后的容量要够用
 * @param capacity 想要保证的最小容量
 */
@SuppressWarnings("unchecked")
private void ensureCapacity(int capacity){
    int oldCapacity = elements.length; //返回数组的容量，length就是内存中的大小了，而不是真实的元素个数
    if (oldCapacity >= capacity) return; //如果数组的容量大于目前我想要的最小容量，说明不需要扩容

    int newCapacity = oldCapacity + (oldCapacity >> 1); //扩充1.5倍，为什么不直接乘1.5？因为浮点数运算更慢，>>1表示一个数除以2，这种效率更高

    Type[] newArrayPointer = (Type[]) new Object[newCapacity]; //新申请一块更大的存储空间，用于存放数组元素
    for (int i = 0;i < size; i++){
        //把原来数组的队列，按照队列的顺序放到新的存储空间
        newArrayPointer[i] = elements[(i + front) % elements.length];
    }
    elements = newArrayPointer;
    System.out.println("扩容："+"oldCapacity:"+oldCapacity+" -> newCapacity:"+newCapacity);
    front = 0;
}

因此，入队的代码就添加上这一句即可：保证有每次入队前，数组都有size+1的容量。

public void enQueue(Type element){
    ensureCapacity(size + 1);
    elements[(front + size) % elements.length] = element;
    size++;
}

下面我们测试一下循环队列的实现：

CircleQueue<Integer> Cqueue = new CircleQueue<>();

//入队10个
for (int i = 0; i < 10 ; i++) {
    Cqueue.enQueue(i);
}
//再入队5个
for (int i = 10; i < 15 ; i++) {
    Cqueue.enQueue(i);
}
//全部出队
while (!Cqueue.isEmpty()){
    System.out.println(Cqueue.deQueue());
}

可以看到，出队的队头元素完全符合队列的先入先出原则，并且动态数组也成功扩容。

不知道有没有发现，循环队列最大最大的一个特点就是索引的处理。我们为什么要这么写索引呢：(front + size) % elements.length，是因为我们想根据数组的索引找到真实的循环队列的索引。这个过程就是数组索引到循环队列真实索引的一个映射过程！因此，我们可以封装一下：

private int index(int Arrayindex){
    return (Arrayindex + front) % elements.length;
}

最值得我们注意的一点就是：循环队列的索引映射过程！需要根据数组的真实索引，算出队列的真实索引。

循环双端队列（Ciecle Deque）

循环队列的入队和出队跟队列一样，只能从队头出队，只能从队尾入队。循环双端队列，顾名思义，可以从队头或者队尾入队出队。也就是在循环队列的基础上，增加一个双端操作的功能。

具体怎么实现呢？如果队头出队，队尾入队的话不需要任何变化。如果队头入队，只需要把放新元素的索引改为(front -1) % elements.length即可。但是要考虑一种情况，当队头就在数组的0处，还要入队，新索引就变成了-1，这是不允许的。

因此，我们要把新索引加上数组的长度，让其转到数组尾端。所以，索引映射需要更改：

private int index(int Arrayindex){
	if(Arrayindex < 0){
		return (Arrayindex + front) % elements.length + elements.length;
	}
    return (Arrayindex + front) % elements.length;
}

所以，对于循环双端队列来说，在队头入队时，需要额外注意边界情况。并且最后需要更新front

public void enQueue(Type element){
    ensureCapacity(size + 1);
    elements[index(-1)] = element;
    size++;
    front = index(-1);
}

如果是队尾出队，只需要找到size-1处的真实索引，然后置位null，并且size–即可。

/**
 * 出队，只能从队头弹出元素，并返回该值
 * 由于在数组中使用一个索引记录着队头，因此这个队头要实时移动
 * @return
 */
public Type deQueue(){
    Type rear_element = elements[index(size-1)];
    elements[index(size-1)] = null;
    size--;
    return rear_element ;
}