前言

上一篇讲了栈和栈的经典面试题，链接如下：

栈与栈的经典面试题

其实栈和队列是一码事，都是对只能再线性表的一端进行插入和删除。

因此，其实栈和队列可以互相转换！

一、队列的特点

先进先出的数据结构，元素从“队尾”添加到队列中，元素从“队首”出队列（FIFO）

二、队列的实现

1.基于链表实现队列

现实生活中，有各式各样的“排队”操作。

同样的，队列也有基于数组实现的队列和基于链表实现的队列。

由于出队操作只能在队列的头部进行，若采用数组的方案，每次出队一个元素就得搬移剩下的所有元素向前移动一个单位。

此时采用链表的方案更加适合队列的结构。

2.核心操作

E poll() : 出队
offer(E e) : 入队

三、双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。

那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque -> Queue的子接口：

小技巧：

大家以后无论使用的是栈还是队列，统一使用双端队列接口！
不推荐使用Stack这个类，这个类已经是时代的弃子，效率很低，都是同步操作。
双端队列的一个常用子类就是LinkedList。

四、循环队列

1.应用场景

操作系统的生产消费者模型
MySQL数据库的InnoDB存储引擎中的redo日志。

2.实现

基本都是使用长度固定的数组实现，数组在实现队列时，若从数组头部删除元素需要频繁的移动后面的元素，带来的效率比较低。
出队和入队操作，使用两个引用，一个head，一个tail，添加元素在数组尾部添加，删除元素只需要移动head引用指向的地址即可（逻辑删除）。

循环队列就是使用长度固定的数组来实现，数组头部就是队首（head），数组的尾部就时队尾（tail）。数组[head…tail]是循环队列的有效元素。

例如：

head永远指向循环队列的第一个元素
tail永远指向循环队列有效元素的后一个位置

循环队列在删除元素时，不需要进行数据的搬移，当有新的元素在添加时就会覆盖掉之前的元素。

所谓的循环队列指的是当head或者tail引用走到数组末尾时，下一次再继续向后移动，其实是返回数组的头部继续操作。

3.判空和判满

由于tail指向的是有效数组后一个位置，所以当tail走到如图所示的head == tail 情况时：

此时我们没法区分当前循环队列到底是空还是满！！！

所以在循环队列中，需要浪费一个空间来判断队列是否已满，如下图所示：

结论：

此时当 (tail+1)%n == head 时，认为此时循环队列已满。
head和tail的移动不能简单的+1，而要使用取模操作，取数组长度。
当head == tail 时，认为此时循环队列为空。

4.最后一个元素的索引

除了tail这个引用指向0这个位置以外，其他情况的最后一个索引 = tail – 1
当 tail = 0 时，最后一个元素就在数组的末尾，索引 = data.length – 1

代码如下：

int lastIndex = tail == 0 ? data.length -1 : tail - 1

五、队列的常见问题

1.用队列实现栈

链接如下：225.用队列实现栈

解题思路：

思路1：（双队列思路）

这个问题的本质和双栈实现最小栈是相同的思路，一定要保证其中一个队列就是进行实际元素存储的，另一个队列就是作为辅助操作。

q1永远是存储元素的队列，新元素添加到q2中，将此时q1中的所有元素出队再入队q2恰好就能实现添加顺序和出队顺序相反的操作。

新元素永远入q2
将老元素q1依次出队再入q2 （这样就交换了元素的先后顺序）
q1和q2交换引用

其中一个队列q1永远都是存储元素的队列，栈的pop就是s1的poll，栈的peek就是s1的peek，栈的push就是s1的offer。（所以整个题的核心操作就是push()）
以保证s1和栈的操作一一对应。
另外一个队列就是作为辅助操作。

代码如下：

class MyStack {
    Deque<Integer> temp;
    Deque<Integer> q1;
    Deque<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
        q2.offer(x);
        while(!q1.isEmpty()){
            q2.offer(q1.poll());
        }
        temp = q1;
        q1 = q2 ;
        q2 = temp;
    }
    
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}

思路2：（单队列思路）

先记录下当前队列中的元素个数n
将新元素直接入队
为了让新元素变成队首元素，连续出队n次（新元素的之前的所有元素都出队列，此时新元素变成了队首元素），再依次入队n次即可。

代码如下：

class MyStack {
    private Deque<Integer> queque;
    private int length=0;//1.先记录一下栈此时的元素个数
    public MyStack() {
        queque=new LinkedList<>();
    }

    public void push(int x) {
        queque.offer(x);//2.新元素直接入队
        //3.把新元素之前的元素挨个出队再入队，此时最新的元素就是队头元素
        for (int i=0;i<length;i++){
            queque.offer(queque.poll());
        }
        length++;

    }

    public int pop() {
        length--;
        return queque.poll();

    }

    public int top() {
        return queque.peek();
    }

    public boolean empty() {
        return queque.isEmpty();
    }
}

2.用栈实现队列

链接如下：用栈实现队列

解题思路：

思路1：(入队 – 时间复杂度为O(n)，出队 – O(1))

定义s1永远是保存元素的栈

先将s1中的现有元素依次弹出放入s2
将新元素入s1 => 此时这个新元素就变成了s1的栈底（队尾元素）
将s2中的元素再依次弹回来（先进先出）

代码如下：

class MyQueue {
    Deque<Integer> s1;
    Deque<Integer> s2;
    public MyQueue() {
        s1 = new LinkedList<>();
        s2 = new LinkedList<>();
    }
    
    public void push(int x) {
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        s1.push(x);
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }
    }
    
    public int pop() {
        return s1.pop();
    }
    
    public int peek() {
        return s1.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty();
    }
}

思路2：(入队 – 时间复杂度为O(1)，出队-摊还复杂度O(1))

push是正常push的，核心操作在pop里面
push进s1的元素依次出栈再入s2栈的时候，出入顺序就会颠倒
根据上述特性，把s2的栈顶当作队首就行了，因为队列都是队首出队的。
每次pop先判断当前s2是否为空，若为空，则把s1中的元素全部出栈并且压进s2里面，此时s2的栈顶就是队首元素（先进先出）。若不为空，证明上一轮push进来的元素还没pop完，继续pop当前s2的栈顶就行。

class MyQueue {
    Deque<Integer> s1 ;
    Deque<Integer> s2 ;
    public MyQueue() {
        s1 = new LinkedList<>();
        s2 = new LinkedList<>();
    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    public int peek() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}