数据结构之队列（Queue）

一、引言

前面我们说了栈（Stack），这次我们来说说和Stack比较相似的队列（Queue），先声明Queue同样是比LinkedList和ArrayList要简单许多这一篇博客将从概念和使用来讲解，并且会讲解用队列实现栈和用栈实现队列。

二、概念

队列与栈不同，栈是先进后出，而队列是先进先出，并且只能从队尾进来就像去景区排队一样先排队的可以先进去，后来的也必须排到队尾。也就是进行删除的一头是队头，进行插入操作的是队尾。在Java里Queue是一个接口，底层的通过链表实现的，因此我们想创建一个队列的时候是不能直接对Queue实例化的。具体如何使用我会在下面一一解释。

三、模拟实现

关于模拟实现队列有两种方法，分别为用链表、双向链表来实现，这里说一下这两种。

首先是链表

class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // 链表实现队列 class MyQueue { // 队头、队尾指针 private ListNode front; private ListNode rear; // 初始化：空队列 public MyQueue() { front = null; rear = null; } // 入队：加到尾部 public void enqueue(int val) { ListNode newNode = new ListNode(val); if (isEmpty()) { // 空队列时，头和尾都指向新节点 front = newNode; rear = newNode; } else { // 尾插法 rear.next = newNode; rear = newNode; } } // 出队：从头部删 public Integer dequeue() { if (isEmpty()) { System.out.println("队列为空，无法出队"); return null; } int val = front.val; front = front.next; // 如果删完变空了，rear 也要置空 if (front == null) { rear = null; } return val; } // 查看队头 public Integer peek() { if (isEmpty()) return null; return front.val; } // 判断空 public boolean isEmpty() { return front == null; } }

要用链表来实现的话我们要定义两个指针，分别指向队头和队尾，入队的时候队列为空就让两个指针指向同一个，不然就尾插法，出队就先存一下队头的值，之后之让队头指向当前队头的下一个，最后再返回存的值查看队头就很简单了，看一眼就知道怎么回事了。

然后是双向链表

// 双向链表节点 class ListNode { int val; ListNode prev; ListNode next; ListNode(int val) { this.val = val; } } // 双向链表实现队列 class MyQueue { private ListNode front; // 队头 private ListNode rear; // 队尾 // 初始化空队列 public MyQueue() { front = null; rear = null; } // 入队：加到队尾 public void enqueue(int val) { ListNode node = new ListNode(val); if (isEmpty()) { front = node; rear = node; } else { rear.next = node; node.prev = rear; rear = node; } } // 出队：从队头删 public Integer dequeue() { if (isEmpty()) { System.out.println("队列空了"); return null; } int val = front.val; // 只有一个节点 if (front == rear) { front = null; rear = null; } else { front = front.next; front.prev = null; } return val; } // 查看队头 public Integer peek() { return isEmpty() ? null : front.val; } // 判断是否为空 public boolean isEmpty() { return front == null; } }

双向链表和单向链表思路上是十分相似的，只不过要注意一下prev就可以了。

下面简单演示一下Queue的使用

import java.util.LinkedList; import java.util.Queue; public class QueueExample { public static void main(String[] args) { // 创建队列 Queue<String> queue = new LinkedList<>(); // 入队操作 queue.add("Apple"); queue.add("Banana"); queue.offer("Cherry"); // 与add()类似，但更推荐用于队列 // 查看队首元素（不删除） System.out.println("队首元素: " + queue.peek()); // 出队操作 String removedItem = queue.poll(); System.out.println("出队元素: " + removedItem); // 遍历队列 System.out.println("当前队列内容:"); for (String item : queue) { System.out.println(item); } } }

四、循环队列

前面用链表实现的队列无需提前指定容量，无空间浪费，但用数组实现普通队列会出现“假溢出”——即rear到达数组末尾时，数组前部因出队空出的空间无法利用。循环队列将数组首尾相连，解决假溢出问题，核心难点是区分队列空和满，常见有三种实现方式，重点掌握第一种。

4.1 循环队列实现方式一：牺牲一个位置（最常用、教科书标准）

核心思路：故意空出一个数组位置，用于区分空和满，数组容量比实际可存元素数多1。

4.1.1 核心原理与判断条件

定义两个指针：front（指向队头，初始0）、rear（指向队尾下一个位置，初始0）；

• 队列空：front == rear；

• 队列满：(rear + 1) % 数组长度 == front；

• 取模运算：实现指针循环移动，避免超出数组范围。

4.1.2 完整代码实现

// 数组实现循环队列（牺牲一个位置版） class MyCircularQueue { private int[] elem; // 存储元素的数组 private int front; // 队头指针（指向队头元素） private int rear; // 队尾指针（指向队尾下一个位置） // 构造方法：参数为实际容量，数组长度=实际容量+1（牺牲一个位置） public MyCircularQueue(int capacity) { elem = new int[capacity + 1]; front = 0; rear = 0; } // 入队：添加到队尾，满则返回false public boolean enQueue(int value) { if (isFull()) { System.out.println("队列已满，无法入队！"); return false; } elem[rear] = value; rear = (rear + 1) % elem.length; // 循环移动 return true; } // 出队：移除队头，空则返回false public boolean deQueue() { if (isEmpty()) { System.out.println("队列为空，无法出队！"); return false; } front = (front + 1) % elem.length; // 覆盖式删除 return true; } // 获取队头元素（不删除） public int Front() { if (isEmpty()) { System.out.println("队列为空，无队头元素！"); return -1; } return elem[front]; } // 获取队尾元素（不删除） public int Rear() { if (isEmpty()) { System.out.println("队列为空，无队尾元素！"); return -1; } // 避免rear为0时出现负下标 int index = (rear - 1 + elem.length) % elem.length; return elem[index]; } // 判断空 public boolean isEmpty() { return front == rear; } // 判断满 public boolean isFull() { return (rear + 1) % elem.length == front; } }

4.1.3 优缺点分析

优点：实现简单、逻辑清晰，无需额外变量，性能高效，是实际开发首选；

缺点：牺牲1个空间，容量较小时浪费比例略高，多数场景可忽略。

4.2 循环队列实现方式二：使用计数器count（最直观）

核心思路：不牺牲空间，增加count变量记录元素个数，直接通过count判断空和满，逻辑直观。

4.2.1 核心原理与判断条件

• 队列空：count == 0；

• 队列满：count == 数组长度；

• 指针移动同第一种方式，入队count++，出队count--。

4.2.2 完整代码实现

// 数组实现循环队列（计数器版） class MyCircularQueue2 { private int[] elem; // 存储元素的数组 private int front; // 队头指针 private int rear; // 队尾指针 private int count; // 记录元素个数 // 构造方法：数组长度=实际容量 public MyCircularQueue2(int capacity) { elem = new int[capacity]; front = 0; rear = 0; count = 0; } // 入队 public boolean enQueue(int value) { if (isFull()) { System.out.println("队列已满，无法入队！"); return false; } elem[rear] = value; rear = (rear + 1) % elem.length; count++; return true; } // 出队 public boolean deQueue() { if (isEmpty()) { System.out.println("队列为空，无法出队！"); return false; } front = (front + 1) % elem.length; count--; return true; } // 获取队头、队尾元素（同第一种方式） public int Front() { if (isEmpty()) { System.out.println("队列为空，无队头元素！"); return -1; } return elem[front]; } public int Rear() { if (isEmpty()) { System.out.println("队列为空，无队尾元素！"); return -1; } int index = (rear - 1 + elem.length) % elem.length; return elem[index]; } public boolean isEmpty() { return count == 0; } public boolean isFull() { return count == elem.length; } }

4.2.3 优缺点分析

• 优点：不浪费空间，逻辑直观，适合初学者；

• 缺点：需额外维护count变量，多一步更新操作。

4.3 循环队列实现方式三：使用标记位flag（考试常考）

核心思路：不牺牲空间、不使用计数器，用boolean类型flag标记最后一次操作（入队/出队），区分空和满，面试高频考点。

4.3.1 核心原理与判断条件

flag = false：最后一次是出队或初始空队列；

flag = true：最后一次是入队；

队列空：front == rear && flag == false；

队列满：front == rear && flag == true。

4.3.2 完整代码实现

// 数组实现循环队列（标记位版） class MyCircularQueue3 { private int[] elem; // 存储元素的数组 private int front; // 队头指针 private int rear; // 队尾指针 private boolean flag; // 标记位：true=入队，false=出队/初始 public MyCircularQueue3(int capacity) { elem = new int[capacity]; front = 0; rear = 0; flag = false; // 初始空队列 } // 入队，成功后标记为true public boolean enQueue(int value) { if (isFull()) { System.out.println("队列已满，无法入队！"); return false; } elem[rear] = value; rear = (rear + 1) % elem.length; flag = true; return true; } // 出队，成功后标记为false public boolean deQueue() { if (isEmpty()) { System.out.println("队列为空，无法出队！"); return false; } front = (front + 1) % elem.length; flag = false; return true; } // 获取队头、队尾元素（同前） public int Front() { if (isEmpty()) { System.out.println("队列为空，无队头元素！"); return -1; } return elem[front]; } public int Rear() { if (isEmpty()) { System.out.println("队列为空，无队尾元素！"); return -1; } int index = (rear - 1 + elem.length) % elem.length; return elem[index]; } public boolean isEmpty() { return front == rear && !flag; } public boolean isFull() { return front == rear && flag; } }

4.3.3 优缺点分析

优点：不牺牲空间、无需计数器，仅用一个标记位；

缺点：逻辑稍复杂，每次操作需更新标记位，易出错。

总结：三种方式核心都是解决“空满区分”，实际开发优先选第一种（牺牲一个位置），笔试重点掌握第三种（标记位），第二种（计数器）适合初学者理解。

五、双端队列（Deque）

双端队列（Double Ended Queue）是队列的扩展，允许在队头和队尾同时进行入队、出队操作，兼具队列和栈的特性。

核心特点：无固定进出规则，队头、队尾均可插入和删除，底层可通过双向链表或数组实现。 Java中Deque是接口，常用实现类有LinkedList、ArrayDeque，核心方法：addFirst()、addLast()、removeFirst()、removeLast()，可灵活实现队列或栈的功能。以下便是双端队列的演示。

import java.util.Deque; import java.util.LinkedList; public class DequeDemo { public static void main(String[] args) { // 1. 创建Deque实例（LinkedList实现） Deque<Integer> deque = new LinkedList<>(); // 2. 队头/队尾入队 deque.addFirst(1); // 队头入队：[1] deque.addLast(2); // 队尾入队：[1, 2] deque.addLast(3); // 队尾入队：[1, 2, 3] // 3. 队头/队尾出队 deque.removeFirst(); // 队头出队：[2, 3] deque.removeLast(); // 队尾出队：[2] // 4. 查看队头/队尾（不删除） System.out.println(deque.getFirst()); // 输出2 System.out.println(deque.getLast()); // 输出2 } }

六、栈实现队列

栈是先进后出（LIFO），队列是先进先出（FIFO），我们可以通过两个栈的配合，模拟实现队列的功能，核心思路是利用两个栈的“倒腾”，将栈的先进后出转化为队列的先进先出。

6.1 核心原理

定义两个栈stack1和stack2，分工明确：

stack1：作为“入队栈”，专门负责接收新元素（push操作）；

stack2：作为“出队栈”，专门负责弹出元素（pop、peek操作）；

核心逻辑：当stack2为空时，将stack1中的所有元素依次弹出并压入stack2，此时stack2的栈顶就是队列的队头，实现先进先出。

6.2 完整代码实现

class MyQueue { Stack<Integer> stack1; // 入队栈：负责接收新元素 Stack<Integer> stack2; // 出队栈：负责弹出元素 // 初始化：创建两个空栈 public MyQueue() { stack1 = new Stack<>(); stack2 = new Stack<>(); } // 入队：将元素压入stack1（入队栈） public void push(int x) { stack1.push(x); } // 出队：弹出队头元素（先进先出） public int pop() { // 队列空（两个栈都空），返回-1 if(empty()){ return -1; } // 出队栈为空时，将入队栈所有元素倒腾到出队栈 else if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); // stack1弹出，stack2压入，反转顺序 } } // 出队栈栈顶就是队头，弹出即可 return stack2.pop(); } // 查看队头元素（不弹出） public int peek() { // 队列空，返回-1 if(empty()){ return -1; } // 出队栈为空时，先倒腾元素 else if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } // 出队栈栈顶就是队头，直接查看 return stack2.peek(); } // 判断队列是否为空：两个栈都为空，队列才为空 public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } }

6.3 核心说明

1. 入队操作：直接压入stack1，时间复杂度O(1)；

2. 出队、查看队头：仅当stack2为空时，才倒腾stack1的元素，整体平均时间复杂度O(1)；

3. 空判断：必须两个栈都为空，才说明队列为空，避免遗漏元素。

七、队列实现栈

与“栈实现队列”思路类似，队列是先进先出（FIFO），栈是先进后出（LIFO），我们可以通过两个队列的配合，将队列的先进先出转化为栈的先进后出，核心是利用一个队列存储元素，另一个队列辅助“倒腾”元素，找到栈顶（队列的队尾）。

7.1 核心原理

定义两个队列qu1和qu2，分工协作，核心是“始终保持一个队列有元素，另一个队列为空”：

qu1、qu2：交替作为“存储队列”（存放当前所有元素）和“辅助队列”（临时转移元素）；

入队（push）：将元素加入当前非空的队列（若均为空，默认加入qu1）；

出队（pop）、查看栈顶（top）：将存储队列中除最后一个元素外的所有元素，转移到辅助队列，剩余的最后一个元素就是栈顶，完成操作后，辅助队列变为新的存储队列。

7.2 完整代码实现

class MyStack { public Queue<Integer> qu1; // 队列1：交替作为存储队列/辅助队列 public Queue<Integer> qu2; // 队列2：交替作为辅助队列/存储队列 // 初始化：创建两个空队列 public MyStack() { qu1 = new LinkedList<>(); qu2 = new LinkedList<>(); } // 入栈：将元素加入当前非空的队列（均空则加入qu1） public void push(int x) { if(!qu1.isEmpty()){ qu1.offer(x); // qu1非空，加入qu1 }else if(!qu2.isEmpty()){ qu2.offer(x); // qu2非空，加入qu2 }else{ qu1.offer(x); // 均为空，默认加入qu1 } } // 出栈：弹出栈顶元素（先进后出） public int pop() { if(empty()){ // 两个队列都空，栈为空，返回-1 return -1; } // qu1非空，将qu1中除最后一个元素外，全部转移到qu2 if(!qu1.isEmpty()){ int size=qu1.size(); for(int i=0;i<size-1;i++){ qu2.offer(qu1.poll()); } return qu1.poll(); // 剩余的最后一个元素就是栈顶，弹出 }else { // qu2非空，同理，将qu2元素转移到qu1 int size=qu2.size(); for(int i=0;i<size-1;i++){ qu1.offer(qu2.poll()); } return qu2.poll(); } } // 查看栈顶元素（不弹出） public int top() { if(empty()){ // 栈为空，返回-1 return -1; } // qu1非空，转移所有元素到qu2，记录最后一个元素（栈顶） if(!qu1.isEmpty()){ int size=qu1.size(); int val=-1; for(int i=0;i<size;i++){ val=qu1.poll(); qu2.offer(val); } return val; // 返回记录的栈顶元素 }else { // qu2非空，同理，转移所有元素到qu1，记录栈顶 int size=qu2.size(); int val=-1; for(int i=0;i<size;i++){ val=qu2.poll(); qu1.offer(val); } return val; } } // 判断栈是否为空：两个队列都为空，栈才为空 public boolean empty() { return qu1.isEmpty() && qu2.isEmpty(); } }

7.3 核心说明

1. 入栈操作：直接加入非空队列，时间复杂度O(1)；

2. 出栈、查看栈顶：需转移除最后一个元素外的所有元素，时间复杂度O(n)；

3. 空判断：两个队列均为空时，栈才为空，确保不遗漏任何元素；

4. 核心技巧：通过两个队列交替作为存储和辅助队列，巧妙将队列的“先进先出”转化为栈的“先进后出”。

八、总结

总而言之栈和队列是十分相似的，我们在记忆的时候可以把两个放在一起记忆，但也千万不能忘记了，Queue是一个接口要用LikedList来实现，这也是新手常犯的错误。接口就是个“空架子”，自己不能直接new出来用，就像你不能拿着“手机”的概念直接打电话一样，得有具体的实现类才行。咱们写代码的时候，最常用的就是LinkedList，用LinkedList去实现Queue，才能正常用它的入队、出队功能，很多新手一上来就写new Queue()，直接报错，血的教训，一定要记牢！

总的来说，栈和队列都是基础款数据结构，不用搞太复杂，把它们的特性、实现方式和易错点记牢，再稍微练两遍，日常开发、笔试面试都能轻松应对，主打一个“学会就够用”，再也不用为这俩货头疼啦。

另外小提一下Stack类 Java 官方已不推荐，最好提一句实际开发用Deque代替栈会比较好一点。