《数据结构》队列及其经典面试题
前言
上一篇讲了栈和栈的经典面试题，链接如下：
栈与栈的经典面试题
其实栈和队列是一码事，都是对只能再线性表的一端进行插入和删除。
因此，其实栈和队列可以互相转换！
一、队列的特点
先进先出的数据结构，元素从“队尾”添加到队列中，元素从“队首”出队列 （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();
}
}
总结
以上就是队列及其经典面试题的全部内容了，有帮助的话麻烦各位给个三连~~感谢！！！