数据结构入门：队列概念、实现与实战应用（Java 版）

3.2 循环队列（解决'假溢出'问题）

基础顺序队列频繁出队后，数组头部会留下空位置（假溢出），循环队列通过'首尾相连'的指针设计，实现空间复用，也是 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 内置队列（实战推荐）

实际开发中无需手写队列，Java 集合框架提供了丰富的内置队列实现，按需选择即可：

4.1 常用内置队列使用示例

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());
    }
}

五、队列的典型应用场景

1. 多线程任务调度：线程池（ThreadPoolExecutor）通过 BlockingQueue 存储待执行任务，实现任务排队；
2. 消息队列：ActiveMQ、RabbitMQ 等中间件底层基于队列实现，处理系统间异步通信；
3. 算法题解：广度优先搜索（BFS）、二叉树层序遍历、迷宫最短路径等必须用队列实现；
4. 业务场景：电商订单排队、客服咨询排队、打印机任务排队等。

六、力扣队列相关中低难度热门题型

掌握队列的核心原理后，通过经典算法题巩固知识点是最佳方式。以下精选 4 道力扣中低难度热门题，覆盖'栈与队列互转''循环队列设计''队列实战应用'三大核心场景。

6.1 题型 1：剑指 Offer 09. 用两个栈实现队列（简单）

题目描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解题思路

队列是'先进先出'，栈是'先进后出'，利用两个栈的'倒腾'实现队列特性：

1. 准备两个栈：inStack（负责入队）、outStack（负责出队）；
2. 入队（appendTail）：直接将元素压入 inStack；
3. 出队（deleteHead）：
   • 若 outStack 为空，将 inStack 所有元素弹出并压入 outStack；
   • 若 outStack 仍为空，返回 -1；否则弹出 outStack 栈顶元素。

Java 代码实现

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());
    }
}

代码解释

• 两个栈的分工明确，避免每次入队都倒腾元素，仅在出队且出队栈为空时倒腾，时间复杂度均摊为 O(1)；
• 核心逻辑是利用栈的倒序特性，将两个栈组合成先进先出的队列。

6.2 题型 2：225. 用队列实现栈（简单）

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop、empty）。

解题思路

队列是'先进先出'，要实现栈的'后进先出'，核心是每次入队后，将队列中除新元素外的所有元素重新入队，让新元素始终在队首（对应栈顶）：

1. 准备一个主队列 queue（核心存储）；
2. 入栈（push）：将元素入队后，把队列中前面的所有元素依次出队再入队，让新元素到队首；
3. 出栈（pop）：直接出队队首元素（即栈顶）；
4. 查看栈顶（top）：直接取队首元素。

Java 代码实现（单队列版）

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());
    }
}

6.3 题型 3：933. 最近的请求次数（简单）

题目描述

写一个 RecentCounter 类来计算特定时间范围内最近的请求。请你实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。

解题思路

这是队列的典型'滑动窗口'应用，核心逻辑：

1. 用队列存储所有请求的时间；
2. 每次 ping 时，先将当前时间 t 入队；
3. 移除队列中所有小于 t-3000 的时间（不在窗口内的请求）；
4. 队列的长度即为当前窗口内的请求数。

Java 代码实现

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));
    }
}

6.4 题型 4：622. 设计循环队列（中等）

题目描述

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为'环形缓冲器'。你的实现应该支持以下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• Front(): 从队首获取元素。如果队列为空，返回 -1 。
• Rear(): 获取队尾元素。如果队列为空，返回 -1 。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

解题思路

与前文手写的循环队列逻辑一致，核心是用数组 + 双指针（front/rear）实现，注意：

1. 队首指针 front 指向队首元素，队尾指针 rear 指向队尾下一个位置；
2. 用 (rear + 1) % capacity == front 判断队列满（预留一个空位避免'满'和'空'的判断冲突）；
3. 用 front == rear 判断队列为空。

Java 代码实现

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());
    }
}

总结

1. 队列核心特性是先进先出（FIFO），Java 中优先使用 offer/poll/peek 等非阻塞方法避免异常；
2. 基础顺序队列存在'假溢出'问题，循环队列通过指针取模实现空间复用，入队 / 出队效率更高；
3. 实战中优先使用 Java 内置队列：单线程用 LinkedList，多线程用 ArrayBlockingQueue/ConcurrentLinkedQueue；
4. 队列核心题型集中在栈与队列互转、滑动窗口应用、循环队列设计三大类，建议新手从简单题入手，逐步挑战设计题。