【数据结构】队列（链表实现 + 力扣 + 详解 + 数组实现循环队列 ）

Hi~！这里是奋斗的明志，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
🌱🌱个人主页：奋斗的明志
🌱🌱所属专栏：数据结构

📚本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

一、队列(Queue)

1.概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头 （Head/Front）

2.队列的使用

在Java中， Queue是个接口，底层是通过链表实现的。

代码如下（示例）：

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); //从队尾入队列 System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列 ，并将删除的元素返回if (q.isEmpty()) {System.out.println("队列空");} else {System.out.println(q.size());}
}

二、队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。

思考下： 队列的实现使用顺序结构还是链式结构好？

1.用双链表实现队列

进队：

出队：

代码如下（示例）：

package queuedemo;public class MyQueue {//用双链表实现队列//结点类static class ListNode {public int val;public ListNode next;public ListNode prev;//提供构造方法public ListNode(int val) {this.val = val;}}public ListNode head;//头结点public ListNode last;//尾结点/*** 1.尾插法* 相当于入队*/public void offer(int val) {ListNode node = new ListNode(val);if (head == null) {head = last = node;} else {last.next = node;node.prev = last;last = last.next;}}/*** 2.头删* 相当于出队*/public int poll() {if (head == null) {return -1;}int val = -1;if (head.next == null) {val = head.val;head = null;last = null;return val;}val = head.val;head = head.next;head.prev = null;return val;}public boolean empty() {return head == null;}public int peek(){if (head == null){return -1;}return head.val;}
}

2.循环队列（利用数组设计）

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。

如何区分空与满？

1. 通过添加 size 属性记录
2. 保留一个位置
3. 使用标记

2.1循环队列图解

2.2代码展示

设计循环队列

package queuedemo;//利用数组设计循环队列
public class MyCircularQueue {public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {//构造方法进行数组初始化this.elem = new int[k];}/*** 入队操作** @param value* @return*/public boolean enQueue(int value) {if (isFull()) {return false;}elem[rear] = value;//例如  (k - 1 + 1) % k = 0rear = (rear + 1) % elem.length;return true;}/*** 出队操作** @return*/public boolean deQueue() {//先判断空不空if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}/*** 得到队头元素，不删除* @return*/public int Front() {//先判断空不空if (isEmpty()) {return -1;}return elem[front];}/*** 得到队尾元素，不删除* @return*/public int Rear() {//先判断空不空if (isEmpty()) {return -1;}int index = (rear == 0) ? elem.length - 1 : rear - 1;return elem[index];}public boolean isEmpty() {return front == rear;}/*** 判断是否满了** @return*/public boolean isFull() {return (rear + 1) % elem.length == front;}
}

三、双端队列 (Deque)

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列， deque 是“double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

• Deque是一个接口，使用时必须创建LinkedList的对象。

• 在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现 
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

四、用队列实现栈（面试题）

用队列实现栈

1.题目

2.解析

• 构造方法 MyStack()：

  初始化两个队列 queue1 和 queue2，这两个队列用来辅助实现栈的操作。

• 压栈操作 push(int x)：

  如果当前栈为空（即两个队列都为空），直接将元素 x 放入 queue1。
  如果其中一个队列不为空，将元素 x 放入非空的队列中（保持一个队列为空，一个队列非空的状态，以便后续操作）。

• 弹出栈顶元素 pop()：

  首先判断栈是否为空，如果为空直接返回 -1。
  如果 queue1 非空，将 queue1 中除了最后一个元素外的所有元素依次转移到 queue2 中，然后弹出 queue1 的最后一个元素作为栈顶元素返回。
  如果 queue2 非空，类似地操作，将 queue2 中除了最后一个元素外的所有元素转移到 queue1 中，然后弹出 queue2 的最后一个元素返回。

• 获取栈顶元素 top()：

  同样先判断栈是否为空，为空则返回 -1。
  如果 queue1 非空，将 queue1 中的所有元素依次转移到 queue2 中，并记录最后一个转移的元素作为栈顶元素返回。
  如果 queue2 非空，类似地操作，将 queue2 中的所有元素依次转移到 queue1 中，并记录最后一个转移的元素返回。

• 判断栈是否为空 empty()：

  如果 queue1 和 queue2 都为空，则栈为空，返回 true；否则返回 false。

这种使用两个队列来模拟栈的实现方式是经典的算法题目，可以有效地实现栈的各种操作。

3.代码展示

class MyStack {//利用队列实现栈//不能使用双端队列public Queue<Integer> queue1;public Queue<Integer> queue2;public MyStack() {//在构造方法里面实例化this.queue1 = new LinkedList<>();this.queue2 = new LinkedList<>();}/*** 压栈操作* @param x*/public void push(int x) {if (empty()){queue1.offer(x);return;}if (!queue1.isEmpty()){queue1.offer(x);}else {queue2.offer(x);}}/*** 弹出栈顶元素* @return*/public int pop() {if (empty()){//说明模拟的栈是空的return -1;}//找到不为空的元素，出size - 1 个元素if (!queue1.isEmpty()){int size = queue1.size();for (int i = 0; i < size - 1; i++) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size = queue2.size();for (int i = 0; i < size - 1; i++) {queue1.offer(queue2.poll());}return queue2.poll();}}public int top() {if (empty()){//说明模拟的栈是空的return -1;}//找到不为空的元素，出size - 1 个元素if (!queue1.isEmpty()){int size = queue1.size();int tmp = -1;for (int i = 0; i < size; i++) {tmp = queue1.poll();queue2.offer(tmp);}return tmp;}else {int size = queue2.size();int tmp = -1;for (int i = 0; i < size; i++) {tmp = queue2.poll();queue1.offer(tmp);}return tmp;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

五、用栈实现队列（面试题）

1.题目

用栈实现队列

2.解析

• stack1 和 stack2：这两个栈用来实现队列的操作。

• stack1 用于存储入队的元素。

• stack2 在需要出队或查看队头元素时用来辅助操作。

• 入队方法 push(int x):

  直接将元素 x 压入 stack1 中，即将元素添加到队列的末尾。

• 出队方法 pop():

  首先检查队列是否为空，如果为空则返回 -1。
  如果 stack2 为空（即队列中的元素都在 stack1 中），则将 stack1 中的所有元素逐个弹出并压入 stack2，然后从 stack2 弹出栈顶元素作为出队元素返回。
  如果 stack2 非空，则直接从 stack2 弹出栈顶元素作为出队元素返回。

• 查看队头元素方法 peek():

  首先检查队列是否为空，如果为空则返回 -1。
  如果 stack2 为空，则将 stack1 中的所有元素逐个弹出并压入 stack2，然后返回 stack2 的栈顶元素作为队头元素，但不移除它。
  如果 stack2 非空，则直接返回 stack2 的栈顶元素。

• 判断队列是否为空方法 empty():

  如果 stack1 和 stack2 都为空，则队列为空，返回 true；否则返回 false。

总结

这段代码通过两个栈 stack1 和 stack2 实现了队列的基本功能，其中 stack1 用于入队操作，而 stack2 在需要出队或查看队头元素时扮演辅助作用。这种实现方式保证了入队操作的时间复杂度为 O(1)，出队和查看队头元素的平均时间复杂度为 O(1)，空间复杂度为 O(n)，其中 n 是队列中的元素个数。

3.代码展示

package queuedemo;import java.util.Stack;public class MyQueue1 {//用栈实现队列//两个栈public Stack<Integer> stack1;public Stack<Integer> stack2;public MyQueue1() {this.stack1 = new Stack<>();this.stack2 = new Stack<>();}/*** 入队列** @param x*/public void push(int x) {stack1.push(x);}/*** 出队列** @return*/public int pop() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}return stack2.pop();}return stack2.pop();}/*** 队头元素** @return*/public int peek() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}return stack2.peek();}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

总结

数组下标循环的小技巧

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length