跳到主要内容Java 队列:原理、实现与高频实战 | 极客日志Javajava算法
Java 队列:原理、实现与高频实战
Java 队列数据结构,涵盖先进先出(FIFO)原理、数组循环队列与链表链式队列的手动实现、Java 官方类库(LinkedList、ArrayDeque、PriorityQueue)的使用及避坑指南。重点解析 BFS 层序遍历、滑动窗口最大值等高频算法题,并提供完整代码示例,帮助开发者掌握队列核心知识与面试考点。
不知所云3 浏览 队列(Queue)是与栈并列的核心线性数据结构,二者均为「操作受限的线性表」,但核心规则截然不同——栈遵循「先进后出(LIFO)」,而队列遵循「先进先出(FIFO, First In First Out)」。
队列就像生活中的排队:先排队的人先办事,后排队的人只能依次等候,无法插队。它广泛应用于工程开发(如消息队列、线程池)和算法刷题(如广度优先搜索 BFS),是面试中高频考察的基础数据结构。今天,我们从底层原理、手动实现,到官方用法、算法实战,全方位拆解队列,帮你彻底掌握。
一、队列的核心概念与特性
1.1 核心定义
队列是一种限制操作位置的线性表,只允许在表的一端(称为「队尾(Rear/Tail)」)进行插入操作(入队),在表的另一端(称为「队头(Front/Head)」)进行删除操作(出队),中间元素无法直接访问或操作。
1.2 核心特性
- 先进先出(FIFO):最核心规则,最先入队的元素,最先出队(与栈完全相反)。
- 操作受限:仅能在队头删除、队尾插入,无法随机访问中间元素(区别于数组、链表)。
- 两种分类:按容量分为「静态队列」(数组实现,固定容量)和「动态队列」(链表实现,容量可扩容);按功能分为「普通队列」和「双端队列(Deque)」(两端均可插入/删除)。
1.3 核心操作(必记,时间复杂度均为 O(1))
队列的操作接口与栈类似,核心只有 5 个,重点区分「队头」和「队尾」的操作边界:
| 操作名称 | 说明 | 注意事项 |
|---|
| offer(E e) | 入队:将元素插入队尾 | 队列满时返回 false(推荐使用,避免抛异常) |
| poll() | 出队:移除并返回队头元素 | 队列为空时返回 null(推荐使用) |
| peek() | 查看队头:返回队头元素但不移除 | 队列为空时返回 null |
| isEmpty() | 判空:判断队列是否为空 | 无 |
| size() | 大小:返回队列中元素个数 | 无 |
补充:Java 中还有 add()(入队,满队抛异常)和 remove()(出队,空队抛异常)方法,开发中不推荐使用,避免未处理异常导致程序崩溃。
1.4 生活中的队列实例
- 银行柜台排队:先到的人先办理业务,后到的人依次排队。
- 打印机打印队列:先发送的打印任务,先被执行打印。
- 消息队列(MQ):先发送的消息,先被消费者接收处理。
- BFS 算法:遍历节点时,先访问的节点,其邻接节点先入队,依次处理。
二、队列的两种实现方式(Java 手动实现)
队列的底层实现主要有两种:「数组实现(循环队列)」和「链表实现(链式队列)」。其中数组实现需解决「假溢出」问题,通常设计为「循环队列」;链表实现无溢出问题,更灵活。
2.1 数组实现:循环队列(推荐,效率高)
为什么不用普通数组,而用循环队列?
普通数组实现队列时,队头出队后,前面的空间无法复用,继续入队会导致「假溢出」(数组实际有空闲空间,但提示队列已满)。循环队列通过「取模运算」,让数组首尾相连,复用空闲空间,解决假溢出问题。
实现思路(核心)
- 用
Object[] 存储队列元素,支持泛型;
- 用两个指针(索引)标记队头(front)和队尾(rear),初始值均为 0;
- 入队:
rear = (rear + 1) % capacity,再赋值(避免 rear 越界);
- 出队:
front = (front + 1) % capacity,再取元素(避免 front 越界);
- 判满/判空:用「浪费一个数组空间」的方式(简化判断)—— 判空:
front == rear;判满:(rear + 1) % capacity == front;
- 扩容:队列满时,扩容为原容量的 2 倍,拷贝原元素到新数组。
Java 代码实现(泛型、动态扩容)
import java.util.Arrays;
public class ArrayQueue<E> {
private Object[] elementData;
private int front;
private int rear;
private int capacity;
private static final int DEFAULT_CAPACITY = 10;
public ArrayQueue() {
this.capacity = DEFAULT_CAPACITY;
this.elementData = new Object[capacity];
this.front = 0;
this.rear = 0;
}
public ArrayQueue(int initialCapacity) {
if (initialCapacity < 2) {
throw new IllegalArgumentException("初始容量不能小于 2:" + initialCapacity);
}
this.capacity = initialCapacity;
this.elementData = new Object[capacity];
this.front = 0;
this.rear = 0;
}
public boolean offer(E e) {
if (isFull()) {
resize(capacity * 2);
}
rear = (rear + 1) % capacity;
elementData[rear] = e;
return true;
}
@SuppressWarnings("unchecked")
public E poll() {
if (isEmpty()) {
return null;
}
front = (front + 1) % capacity;
E head = (E) elementData[front];
elementData[front] = null;
return head;
}
@SuppressWarnings("unchecked")
public E peek() {
if (isEmpty()) {
return null;
}
return (E) elementData[(front + 1) % capacity];
}
public boolean isEmpty() {
return front == rear;
}
private boolean isFull() {
return (rear + 1) % capacity == front;
}
public int size() {
return (rear - front + capacity) % capacity;
}
private void resize(int newCapacity) {
Object[] newArray = new Object[newCapacity];
int index = 0;
for (int i = (front + 1) % capacity; i != (rear + 1) % capacity; i = (i + 1) % capacity) {
newArray[index++] = elementData[i];
}
this.elementData = newArray;
this.capacity = newCapacity;
this.front = 0;
this.rear = index;
}
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<>();
for (int i = 1; i <= 10; i++) {
queue.offer(i);
}
System.out.println("队列大小:" + queue.size());
System.out.println("队头元素:" + queue.peek());
System.out.println("出队元素:" + queue.poll());
System.out.println("出队后队头:" + queue.peek());
queue.offer(11);
System.out.println("扩容后队列大小:" + queue.size());
while (!queue.isEmpty()) {
queue.poll();
}
System.out.println("清空后队列是否为空:" + queue.isEmpty());
}
}
2.2 链表实现:链式队列(灵活,无溢出)
链式队列用单链表实现,以「头节点」作为队头,「尾节点」作为队尾,入队操作队尾,出队操作队头,无需考虑扩容和假溢出问题,适合元素个数波动极大的场景。
实现思路
- 定义链表节点
Node,包含数据域和指针域;
- 用
head 指向队头节点,tail 指向队尾节点,初始均为 null;
- 入队:若队列为空(head=null),则 head 和 tail 同时指向新节点;否则,tail.next 指向新节点,tail 更新为新节点;
- 出队:若队列为空,返回 null;否则,取出 head 的数据,head 更新为 head.next,若出队后队列为空,tail 也置为 null。
Java 代码实现(泛型)
public class LinkedQueue<E> {
private static class Node<E> {
E item;
Node<E> next;
Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
}
private Node<E> head;
private Node<E> tail;
private int size;
public LinkedQueue() {
this.head = null;
this.tail = null;
this.size = 0;
}
public boolean offer(E e) {
Node<E> newNode = new Node<>(e, null);
if (isEmpty()) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
size++;
return true;
}
public E poll() {
if (isEmpty()) {
return null;
}
E headItem = head.item;
head = head.next;
size--;
if (isEmpty()) {
tail = null;
}
return headItem;
}
public E peek() {
if (isEmpty()) {
return null;
}
return head.item;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public static void main(String[] args) {
LinkedQueue<String> queue = new LinkedQueue<>();
queue.offer("Java");
queue.offer("算法");
queue.offer("队列");
System.out.println("队列大小:" + queue.size());
System.out.println("队头元素:" + queue.peek());
System.out.println("出队元素:" + queue.poll());
System.out.println("剩余队头:" + queue.peek());
queue.poll();
queue.poll();
System.out.println("清空后队列是否为空:" + queue.isEmpty());
}
}
2.3 两种实现方式对比
| 实现方式 | 优点 | 缺点 | 适用场景 |
|---|
| 循环队列(数组) | 操作效率高,无指针开销,内存连续 | 需处理扩容、循环逻辑,初始容量难确定 | 元素个数相对固定,追求高性能 |
| 链式队列(链表) | 无需扩容,内存利用率高,实现简单 | 每个节点有指针开销,操作略慢于数组 | 元素个数波动大,无需预设容量 |
三、Java 官方队列的使用(开发必学,避坑指南)
Java 集合框架中,队列的核心接口是 java.util.Queue,该接口继承自 Collection,提供了队列的标准操作。开发中无需手动实现队列,直接使用官方实现类即可,重点掌握 3 个常用类。
3.1 核心接口:Queue
Queue 接口定义了队列的核心操作,分为两类(推荐使用第一类,避免异常):
- 安全操作(推荐):
offer()、poll()、peek(),操作失败返回 false/null,不抛异常;
- 不安全操作:
add()、remove()、element(),操作失败抛异常(如 IllegalStateException)。
3.2 常用实现类(3 个,重点掌握)
(1)LinkedList:最常用,链式队列
LinkedList 实现了 Queue 接口,底层是双向链表,同时可作为栈(Deque)、队列使用,是开发中队列的首选实现类,支持动态扩容,无容量限制。
import java.util.LinkedList;
import java.util.Queue;
public class LinkedListQueueDemo {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(10);
queue.offer(20);
queue.offer(30);
System.out.println("队头元素:" + queue.peek());
while (!queue.isEmpty()) {
System.out.println("出队元素:" + queue.poll());
}
System.out.println("空队 peek:" + queue.peek());
System.out.println("空队 poll:" + queue.poll());
}
}
(2)ArrayDeque:高效循环队列,性能最优
ArrayDeque 实现了 Deque(双端队列)接口,底层是动态扩容的循环数组,既可以作为队列使用,也可以作为栈使用。其性能优于 LinkedList(无指针开销),是追求高性能时的首选。
注意:ArrayDeque 不允许存储 null 元素(会抛 NullPointerException),而 LinkedList 允许。
(3)PriorityQueue:优先级队列(特殊队列)
PriorityQueue 是「优先级队列」,不遵循先进先出,而是根据元素的优先级(默认自然排序,可自定义比较器)排序,优先级最高的元素最先出队。
应用场景:任务调度(优先级高的任务先执行)、TopK 问题等,示例:
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueDemo {
public static void main(String[] args) {
Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(3);
priorityQueue.offer(1);
priorityQueue.offer(2);
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
}
}
3.3 避坑提醒
- 避免使用
Stack 类实现栈,但可以用 LinkedList 或 ArrayDeque 实现栈(Deque 接口的 push()/pop() 方法);
ArrayDeque 性能优于 LinkedList,开发中优先使用 ArrayDeque(除非需要存储 null 元素);
PriorityQueue 不是普通队列,不遵循 FIFO,使用时需注意场景;
- 队列是线程不安全的,若在多线程环境下使用,需用
ConcurrentLinkedQueue(无界线程安全队列)或 ArrayBlockingQueue(有界线程安全队列)。
四、队列高频面试题(Java 实战,面试必刷)
队列的高频算法题,核心围绕「队列特性(FIFO)」「队列与栈的转换」「BFS 算法」展开,以下 4 道题覆盖 90% 的考点,附详细思路和代码。
例题 1:用队列实现栈(LeetCode 225,简单,结构转换)
题目描述
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
解题思路
核心:用两个队列(queue1、queue2),始终保持一个队列为空,一个队列存储元素。入栈时插入非空队列;出栈时,将非空队列的前 n-1 个元素转移到空队列,剩余 1 个元素即为栈顶元素(出栈)。
Java 代码实现
import java.util.LinkedList;
import java.util.Queue;
public class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
if (!queue1.isEmpty()) {
queue1.offer(x);
} else {
queue2.offer(x);
}
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空,无法出栈");
}
Queue<Integer> nonEmpty = queue1.isEmpty() ? queue2 : queue1;
Queue<Integer> empty = queue1.isEmpty() ? queue1 : queue2;
while (nonEmpty.size() > 1) {
empty.offer(nonEmpty.poll());
}
return nonEmpty.poll();
}
public int top() {
int top = pop();
push(top);
return top;
}
public boolean empty() {
return queue1.isEmpty() && queue2.isEmpty();
}
public static void main(String[] args) {
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
System.out.println(myStack.top());
System.out.println(myStack.pop());
System.out.println(myStack.empty());
}
}
例题 2:用栈实现队列(LeetCode 232,简单,结构转换)
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty)。
解题思路
核心:用两个栈(inStack、outStack),inStack 负责入队,outStack 负责出队。入队时直接压入 inStack;出队时,若 outStack 为空,将 inStack 的所有元素弹出并压入 outStack(反转顺序,实现 FIFO),再从 outStack 弹出元素。
Java 代码实现
import java.util.Deque;
import java.util.LinkedList;
public class MyQueue {
private Deque<Integer> inStack;
private Deque<Integer> outStack;
public MyQueue() {
inStack = new LinkedList<>();
outStack = new LinkedList<>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("队列为空,无法出队");
}
transfer();
return outStack.pop();
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("队列为空,无队头元素");
}
transfer();
return outStack.peek();
}
public boolean isEmpty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void transfer() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
public static void main(String[] args) {
MyQueue myQueue = new MyQueue();
myQueue.push(1);
myQueue.push(2);
System.out.println(myQueue.peek());
System.out.println(myQueue.pop());
System.out.println(myQueue.isEmpty());
}
}
例题 3:二叉树的层序遍历(LeetCode 102,中等,BFS 核心应用)
题目描述
给你二叉树的根节点 root,返回其节点值的层序遍历(即逐层地,从左到右访问所有节点)。
解题思路
层序遍历是队列的核心应用(BFS 算法),核心逻辑:
- 初始化队列,将根节点入队;
- 循环:获取当前队列大小(即当前层的节点数),遍历当前层的所有节点;
- 每个节点出队,将其值加入结果集,同时将其左、右子节点(非 null)入队;
- 循环结束,返回结果集。
Java 代码实现
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class LevelOrder {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> levelList = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode curr = queue.poll();
levelList.add(curr.val);
if (curr.left != null) {
queue.offer(curr.left);
}
if (curr.right != null) {
queue.offer(curr.right);
}
}
result.add(levelList);
}
return result;
}
public static void main(String[] args) {
LevelOrder solution = new LevelOrder();
TreeNode root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
List<List<Integer>> res = solution.levelOrder(root);
System.out.println(res);
}
}
例题 4:滑动窗口最大值(LeetCode 239,困难,单调队列应用)
题目描述
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
解题思路
核心:用「单调队列(双端队列 Deque)」维护滑动窗口的最大值,保证队列内元素单调递减(队头是当前窗口的最大值):
- 遍历数组,对于每个元素,移除队列中比当前元素小的所有元素(保证队列单调递减);
- 将当前元素入队;
- 判断队头元素是否超出当前窗口范围(索引差 >=k),若是则出队;
- 当遍历到索引 >=k-1 时,队头元素即为当前窗口的最大值,加入结果集。
Java 代码实现
import java.util.Deque;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;
public class MaxSlidingWindow {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
List<Integer> result = new ArrayList<>();
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (!deque.isEmpty() && i - deque.peekFirst() >= k) {
deque.pollFirst();
}
if (i >= k - 1) {
result.add(nums[deque.peekFirst()]);
}
}
int[] resArr = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
resArr[i] = result.get(i);
}
return resArr;
}
public static void main(String[] args) {
MaxSlidingWindow solution = new MaxSlidingWindow();
int[] nums = {1,3,-1,-3,5,3,6,7};
int k = 3;
int[] res = solution.maxSlidingWindow(nums, k);
for (int num : res) {
System.out.print(num + " ");
}
}
}
五、队列常见误区与避坑技巧
5.1 常见误区
- 混淆队列与栈的规则:面试中常考「队列与栈的转换」,记错 FIFO 和 LIFO 规则,导致逻辑错误;
- 数组实现队列未处理假溢出:用普通数组而非循环队列,导致空间浪费和假溢出;
- 误用官方实现类:如用
PriorityQueue 当作普通队列使用,忽略其优先级排序特性;
- 多线程环境使用非线程安全队列:如用
LinkedList 在多线程中操作,导致数据安全问题。
5.2 避坑技巧
- 牢记核心规则:队列 FIFO、栈 LIFO,转换类题目先明确两个结构的操作差异;
- 开发优先用官方类:无需手动实现队列,优先用
ArrayDeque(高性能)或 LinkedList(灵活);
- 单调队列是进阶重点:滑动窗口、TopK 等难题,优先考虑单调队列(维护队列单调性);
- 多线程场景选对实现类:多线程用
ConcurrentLinkedQueue(无界)或 ArrayBlockingQueue(有界)。
六、队列的应用场景(工程 + 算法)
6.1 工程开发场景
- 消息队列(MQ):如 RabbitMQ、Kafka,用于系统间解耦,异步通信(生产者入队,消费者出队);
- 线程池:线程池中的任务队列,提交的任务先入队,线程空闲时从队列中取任务执行;
- 缓冲队列:如打印机缓冲、网络请求缓冲,缓解上下游处理速度不一致的问题;
- 广度优先搜索(BFS):图、二叉树的层序遍历,核心依赖队列。
6.2 算法刷题场景
- BFS 算法:二叉树层序遍历、图的最短路径、岛屿数量等;
- 结构转换:用队列实现栈、用栈实现队列;
- 滑动窗口问题:滑动窗口最大值、滑动窗口平均值等(单调队列);
- 任务调度:优先级队列实现 TopK、任务排序等。
七、总结
队列的核心是「先进先出(FIFO)」,与栈的「先进后出」形成互补,二者均为操作受限的线性表,是数据结构的基础。掌握队列的关键的是:
- 理解两种底层实现(循环队列、链式队列)的逻辑,尤其是循环队列解决假溢出的思路;
- 熟练使用 Java 官方实现类(
LinkedList、ArrayDeque、PriorityQueue),避开使用误区;
- 掌握队列的高频算法题,尤其是 BFS、单调队列、结构转换类题目。
队列的难度低于栈的进阶用法(单调栈),但应用场景更广泛,无论是开发还是面试,都是必备知识点。建议结合本文的例题动手实现,重点练习 BFS 和单调队列,就能彻底吃透队列结构。
微信扫一扫,关注极客日志
微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具
- Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
- Escape 与 Native 编解码
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
- JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
- JavaScript 压缩与混淆
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online