Javajava算法
数据结构入门：队列概念、实现与实战应用（Java 版）
本文详解 Java 队列数据结构，涵盖 FIFO 原理、基础顺序队列与循环队列的手写实现，以及 LinkedList 等内置队列的使用场景。文章还通过剑指 Offer 用两个栈实现队列、用队列实现栈、最近请求次数及设计循环队列等 LeetCode 经典题目，解析滑动窗口与双指针技巧，帮助开发者掌握队列在实际开发与算法面试中的应用。
本文详解 Java 队列数据结构，涵盖 FIFO 原理、基础顺序队列与循环队列的手写实现，以及 LinkedList 等内置队列的使用场景。文章还通过剑指 Offer 用两个栈实现队列、用队列实现栈、最近请求次数及设计循环队列等 LeetCode 经典题目，解析滑动窗口与双指针技巧，帮助开发者掌握队列在实际开发与算法面试中的应用。
队列作为编程核心数据结构之一，在 Java 开发、算法题解中应用广泛。本文从零基础视角，结合 Java 语法特性，带你吃透队列的核心概念、手写实现和实战用法，所有代码均可直接编译运行。
生活中的'排队'场景（食堂打饭、银行办业务）完美契合队列的核心逻辑：先来先服务。对应数据结构中，队列（Queue）是遵循 先进先出（FIFO, First In First Out） 原则的线性表：
结合 Java 的接口设计，队列核心操作分为两类（推荐使用非阻塞方法）：
| 操作 | 阻塞 / 抛异常方法 | 非阻塞 / 返回值方法 | 说明 |
|---|---|---|---|
| 入队 | add(E e) | offer(E e) | 队尾添加元素，满时前者抛异常、后者返回 false |
| 出队 | remove() | poll() | 移除并返回队首，空时前者抛异常、后者返回 null |
| 查看队首 | element() | peek() | 查看队首（不删除），空时前者抛异常、后者返回 null |
| 判断是否为空 | isEmpty() | - | 返回 boolean 值 |
| 获取长度 | size() | - | 返回队列元素个数 |
我们先实现基础顺序队列，再解决'假溢出'问题的循环队列，理解底层原理后，再讲 Java 内置队列的使用。
import java.util.ArrayList;
import java.util.NoSuchElementException;
/**
* 基于 ArrayList 实现的基础顺序队列（泛型版，适配任意数据类型）
* 优点：实现简单；缺点：出队时删除队首元素，后续元素需移动，时间复杂度 O(n)
*/
public class ArrayQueue<E> {
// 存储队列元素的容器
private final ArrayList<E> items;
// 构造方法：初始化空队列
public ArrayQueue() {
items = new ArrayList<>();
}
/**
* 判断队列是否为空
*/
public boolean isEmpty() {
return items.isEmpty();
}
/**
* 入队：队尾添加元素（非阻塞）
*/
public boolean offer(E item) {
items.add(item);
return true;
}
/**
* 出队：移除并返回队首元素（非阻塞，空时返回 null）
*/
public E poll() {
if (isEmpty()) {
return null;
}
return items.remove(0);
}
/**
* 出队：移除并返回队首元素（阻塞版，空时抛异常）
*/
public E remove() {
if (isEmpty()) {
throw new NoSuchElementException("队列已空，无法执行出队操作");
}
return items.remove(0);
}
/**
* 查看队首元素（非阻塞，空时返回 null）
*/
public E peek() {
if (isEmpty()) {
return null;
}
return items.get(0);
}
/**
* 查看队首元素（阻塞版，空时抛异常）
*/
public E element() {
if (isEmpty()) {
throw new NoSuchElementException("队列为空，无队首元素");
}
return items.get(0);
}
/**
* 获取队列长度
*/
public int size() {
return items.size();
}
// 测试基础队列
public static void main(String[] args) {
ArrayQueue<String> queue = new ArrayQueue<>();
queue.offer("任务 1");
queue.offer("任务 2");
queue.offer("任务 3");
System.out.println("队列是否为空：" + queue.isEmpty());
System.out.println("队列长度：" + queue.size());
System.out.println("队首元素：" + queue.peek());
System.out.println("出队元素：" + queue.poll());
System.out.println("出队后队首：" + queue.peek());
System.out.println("出队后队列长度：" + queue.size());
}
}
基础顺序队列频繁出队后，数组头部会留下空位置（假溢出），循环队列通过'首尾相连'的指针设计，实现空间复用，也是 Java 内置队列（如 ArrayBlockingQueue）的核心原理。
import java.util.NoSuchElementException;
/**
* 基于数组实现的循环队列（固定容量，泛型版）
* 解决顺序队列'假溢出'问题，入队/出队时间复杂度均为 O(1)
*/
public class CircularQueue<E> {
private final E[] items;
private final int capacity;
private int front;
private int rear;
private int count;
@SuppressWarnings("unchecked")
public CircularQueue(int capacity) {
this.capacity = capacity;
this.items = (E[]) new Object[capacity];
this.front = 0;
this.rear = 0;
this.count = 0;
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == capacity;
}
public boolean offer(E item) {
if (isFull()) {
return false;
}
items[rear] = item;
rear = (rear + 1) % capacity;
count++;
return true;
}
public boolean add(E item) {
if (isFull()) {
throw new IllegalStateException("队列已满，无法入队");
}
return offer(item);
}
public E poll() {
if (isEmpty()) {
return null;
}
E item = items[front];
items[front] = null;
front = (front + 1) % capacity;
count--;
return item;
}
public E remove() {
if (isEmpty()) {
throw new NoSuchElementException("队列已空，无法出队");
}
return poll();
}
public E peek() {
if (isEmpty()) {
return null;
}
return items[front];
}
public E element() {
if (isEmpty()) {
throw new NoSuchElementException("队列为空，无队首元素");
}
return peek();
}
public int size() {
return count;
}
public static void main(String[] args) {
CircularQueue<Integer> cq = new CircularQueue<>(3);
cq.offer(10);
cq.offer(20);
cq.offer(30);
System.out.println("队列是否已满：" + cq.isFull());
System.out.println("入队 40 是否成功：" + cq.offer(40));
System.out.println("出队元素：" + cq.poll());
System.out.println("当前队首：" + cq.peek());
cq.offer(40);
System.out.println("入队 40 后队尾元素：" + cq.items[cq.rear - 1]);
System.out.println("队列长度：" + cq.size());
}
}
实际开发中无需手写队列，Java 集合框架提供了丰富的内置队列实现，按需选择即可：
| 队列类型 | 特点 | 适用场景 |
|---|---|---|
| LinkedList | 实现 Queue 接口，非线程安全，无界队列 | 单线程、无需固定容量场景 |
| ArrayBlockingQueue | 数组实现，线程安全，有界队列 | 多线程、需固定容量场景 |
| LinkedBlockingQueue | 链表实现，线程安全，可选有界 / 无界 | 多线程、高并发场景 |
| ConcurrentLinkedQueue | 链表实现，线程安全，无界队列 | 高并发、无需阻塞场景 |
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
public class JavaBuiltInQueueDemo {
public static void main(String[] args) {
// 1. LinkedList 实现 Queue（单线程推荐）
Queue<String> linkedQueue = new LinkedList<>();
linkedQueue.offer("消息 1");
linkedQueue.offer("消息 2");
System.out.println("LinkedList 队首：" + linkedQueue.peek());
System.out.println("LinkedList 出队：" + linkedQueue.poll());
// 2. ArrayBlockingQueue（多线程推荐，固定容量）
Queue<Integer> blockingQueue = new ArrayBlockingQueue<>(2);
blockingQueue.offer(100);
blockingQueue.offer(200);
System.out.println("ArrayBlockingQueue 是否已满：" + !blockingQueue.offer(300));
System.out.println("ArrayBlockingQueue 出队：" + blockingQueue.poll());
}
}
掌握队列的核心原理后，通过经典算法题巩固知识点是最佳方式。以下精选 4 道力扣中低难度热门题，覆盖'栈与队列互转''循环队列设计''队列实战应用'三大核心场景。
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
队列是'先进先出'，栈是'先进后出'，利用两个栈的'倒腾'实现队列特性：
inStack（负责入队）、outStack（负责出队）；inStack；outStack 为空，将 inStack 所有元素弹出并压入 outStack；outStack 仍为空，返回 -1；否则弹出 outStack 栈顶元素。import java.util.Stack;
class CQueue {
private final Stack<Integer> inStack;
private final Stack<Integer> outStack;
public CQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
public void appendTail(int value) {
inStack.push(value);
}
public int deleteHead() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.isEmpty() ? -1 : outStack.pop();
}
public static void main(String[] args) {
CQueue cQueue = new CQueue();
cQueue.appendTail(3);
System.out.println(cQueue.deleteHead());
System.out.println(cQueue.deleteHead());
cQueue.appendTail(5);
cQueue.appendTail(2);
System.out.println(cQueue.deleteHead());
}
}
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop、empty）。
队列是'先进先出'，要实现栈的'后进先出'，核心是每次入队后，将队列中除新元素外的所有元素重新入队，让新元素始终在队首（对应栈顶）：
queue（核心存储）；import java.util.LinkedList;
import java.util.Queue;
class MyStack {
private final Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
int size = queue.size();
queue.offer(x);
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.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());
}
}
写一个 RecentCounter 类来计算特定时间范围内最近的请求。请你实现 RecentCounter 类：
RecentCounter() 初始化计数器，请求数为 0。int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。这是队列的典型'滑动窗口'应用，核心逻辑：
ping 时，先将当前时间 t 入队；t-3000 的时间（不在窗口内的请求）；import java.util.LinkedList;
import java.util.Queue;
class RecentCounter {
private final Queue<Integer> queue;
public RecentCounter() {
queue = new LinkedList<>();
}
public int ping(int t) {
queue.offer(t);
while (queue.peek() < t - 3000) {
queue.poll();
}
return queue.size();
}
public static void main(String[] args) {
RecentCounter recentCounter = new RecentCounter();
System.out.println(recentCounter.ping(1));
System.out.println(recentCounter.ping(100));
System.out.println(recentCounter.ping(3001));
System.out.println(recentCounter.ping(3002));
}
}
设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为'环形缓冲器'。你的实现应该支持以下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。Front(): 从队首获取元素。如果队列为空，返回 -1 。Rear(): 获取队尾元素。如果队列为空，返回 -1 。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。与前文手写的循环队列逻辑一致，核心是用数组 + 双指针（front/rear）实现，注意：
front 指向队首元素，队尾指针 rear 指向队尾下一个位置；(rear + 1) % capacity == front 判断队列满（预留一个空位避免'满'和'空'的判断冲突）；front == rear 判断队列为空。class MyCircularQueue {
private final int[] items;
private final int capacity;
private int front;
private int rear;
public MyCircularQueue(int k) {
capacity = k + 1;
items = new int[capacity];
front = 0;
rear = 0;
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
items[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
return true;
}
public int Front() {
return isEmpty() ? -1 : items[front];
}
public int Rear() {
if (isEmpty()) {
return -1;
}
return items[(rear - 1 + capacity) % capacity];
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
public static void main(String[] args) {
MyCircularQueue circularQueue = new MyCircularQueue(3);
System.out.println(circularQueue.enQueue(1));
System.out.println(circularQueue.enQueue(2));
System.out.println(circularQueue.enQueue(3));
System.out.println(circularQueue.enQueue(4));
System.out.println(circularQueue.Rear());
System.out.println(circularQueue.isFull());
System.out.println(circularQueue.deQueue());
System.out.println(circularQueue.enQueue(4));
System.out.println(circularQueue.Rear());
}
}
offer/poll/peek 等非阻塞方法避免异常；LinkedList，多线程用 ArrayBlockingQueue/ConcurrentLinkedQueue；
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online