队列基础：用栈实现队列与循环队列设计

摘要

本篇覆盖两道队列设计题：LeetCode 232（Implement Queue using Stacks，用栈实现队列）和 LeetCode 622（Design Circular Queue，循环队列）。LeetCode 232 的核心是”双栈模拟 FIFO”的摊还分析——push 操作 $O (1)$ ，pop/peek 操作摊还 $O (1)$ ，理解其中的懒惰搬移（lazy transfer）思想对后续理解 Kafka 的 Producer 缓冲区、JVM 分代 GC 的晋升策略等工程场景有直接帮助；LeetCode 622 则是环形缓冲区（Ring Buffer）的最简实现，是理解 Linux epoll、Kafka 日志存储、Netty ByteBuf 等高性能 I/O 场景的重要基础。

第 1 章 LeetCode 232：用栈实现队列

1.1 题目

LeetCode 232 - Implement Queue using Stacks（简单）

使用两个栈实现先进先出队列。队列应当支持普通队列支持的所有操作：push、pop（移除并返回队头元素）、peek（返回队头元素）和 empty。

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop();  // 返回 1
queue.empty();// 返回 false

约束：只能使用标准栈操作，push to top、peek/pop from top、size、isEmpty。

1.2 问题分析

栈（LIFO）存储 [1, 2, 3] 时，弹出顺序是 3 → 2 → 1。
队列（FIFO）需要的弹出顺序是 1 → 2 → 3。

直觉：把栈中的元素倒转一次，就变成了队列的顺序。“倒转一个栈”的方法是：用另一个栈做中转——把 stack1 全部弹出压入 stack2，stack2 的弹出顺序就是原来的正序。

1.3 双栈队列：两种搬移时机

关键设计决策：何时将元素从 inStack（输入栈）搬到 outStack（输出栈）？

方案 A：每次 pop/peek 时全量搬移（如果 outStack 为空的话）

push：直接压入 inStack（ $O (1)$ ）
pop/peek：若 outStack 为空，将 inStack 全部倒入 outStack；再从 outStack 操作（摊还 $O (1)$ ）

这个方案的核心是懒惰搬移（Lazy Transfer）：不是每次 push 都搬，而是等到 outStack 彻底空了再批量搬。这样每个元素最多被搬移一次（从 inStack 到 outStack），总摊还代价是 $O (1)$ 。

方案 B：每次 push 时搬移（push $O (n)$ ，pop $O (1)$ ）

与 02 栈的设计题：最小栈与用队列模拟栈中的队列模拟栈思路类似，但通常方案 A 更优。

1.4 代码实现

class MyQueue {
    private Deque<Integer> inStack;  // 接收新元素
    private Deque<Integer> outStack; // 提供出队元素
    
    public MyQueue() {
        inStack = new ArrayDeque<>();
        outStack = new ArrayDeque<>();
    }
    
    /** 将元素压入队尾 */
    public void push(int x) {
        inStack.push(x); // 直接压入 inStack，O(1)
    }
    
    /** 移除并返回队头元素 */
    public int pop() {
        transfer(); // 懒惰搬移
        return outStack.pop();
    }
    
    /** 查看队头元素 */
    public int peek() {
        transfer(); // 懒惰搬移
        return outStack.peek();
    }
    
    /** 队列是否为空 */
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
    
    /** 懒惰搬移：只有 outStack 为空时才搬 */
    private void transfer() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

1.5 摊还分析

摊还分析（Amortized Analysis） 不看单次操作的最坏情况，而是看 $n$ 次操作的总代价然后除以 $n$ ，得到每次操作的平均代价。

对 pop 的摊还分析：

设想一次最坏情况的 pop：inStack 有 $k$ 个元素，需要全部搬移到 outStack，这次 pop 代价是 $O (k)$ 。

但是，这 $k$ 个元素各自经历了什么？

每个元素在 push 时被压入 inStack：1 次操作
每个元素在搬移时被弹出 inStack 并压入 outStack：2 次操作
每个元素在最终被 pop 时从 outStack 弹出：1 次操作

每个元素的总操作次数是 4 次（常数），无论调用了多少次 push/pop，每个元素最多被搬移一次。因此， $n$ 次 push + $m$ 次 pop 的总代价是 $O (n + m)$ ，单次摊还代价是 $O (1)$ 。

这和 Java ArrayList 的动态扩容分析思路完全相同——虽然偶尔有一次 $O (n)$ 的搬移，但摊还到每个元素上是 $O (1)$ 。

1.6 手动验证

push(1): inStack=[1], outStack=[]
push(2): inStack=[2,1]（2在顶）, outStack=[]  
push(3): inStack=[3,2,1], outStack=[]

peek():
  outStack为空，搬移: 弹出3→outStack, 弹出2→outStack, 弹出1→outStack
  inStack=[], outStack=[1,2,3]（1在顶）
  return outStack.peek() = 1 ✓

pop():
  outStack非空，直接弹
  return outStack.pop() = 1
  inStack=[], outStack=[2,3]

push(4):
  inStack=[4], outStack=[2,3]

pop():
  outStack非空，直接弹
  return 2 ✓（队列中还有 [3, 4]，3 是最先入的）

第 2 章 LeetCode 622：设计循环队列

2.1 题目

LeetCode 622 - Design Circular Queue（中等）

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO 原则，并且队尾被连接在队首之后以形成一个循环。它也被称为”环形缓冲器”。

循环队列的好处是可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

实现 MyCircularQueue：

MyCircularQueue(k)：构造器，设置队列长度为 k
enQueue(value)：向循环队列插入一个元素，插入成功返回 true
deQueue()：从循环队列中删除一个元素，删除成功返回 true
Front()：从队首获取元素，空队列返回 -1
Rear()：获取队尾元素，空队列返回 -1
isEmpty()、isFull()

2.2 为什么需要循环队列

用普通数组实现队列的问题：

初始: [_, _, _, _]  head=0, tail=0（tail 指向下一个写入位置）
enQueue(1): [1, _, _, _]  head=0, tail=1
enQueue(2): [1, 2, _, _]  head=0, tail=2
deQueue():  [_, 2, _, _]  head=1, tail=2（head 向右移动）
enQueue(3): [_, 2, 3, _]  head=1, tail=3
enQueue(4): [_, 2, 3, 4]  head=1, tail=4
enQueue(5): tail=4，到末尾了，isFull()? 不！head=1，还有一个空位 [0]！

但是如果不循环，我们没法利用 index=0 的空间。

循环队列的解决方案：用取模运算让下标”循环”，tail = (tail + 1) % capacity，使 tail 绕回到 index=0：

enQueue(5): tail=(4+1)%5=0，写入 index=0 → [5, 2, 3, 4]  head=1, tail=0... 但如何判满？

2.3 判满的经典技巧：牺牲一个槽位

循环队列最棘手的问题是区分”满”和”空”——因为满状态和空状态下，head == tail 都可能成立！

常用方案：保留一个槽位不使用，使得：

空条件：head == tail
满条件：(tail + 1) % capacity == head

所以，如果容量是 k，数组大小需要是 k + 1。

capacity = k+1（数组大小），始终保留一个空槽位
空: head == tail
满: (tail + 1) % capacity == head

另一种方案：用计数器 size（更直观，下面代码采用这种）：

class MyCircularQueue {
    private int[] data;
    private int head;   // 队头下标
    private int tail;   // 下一个写入位置的下标
    private int size;   // 当前元素个数
    private int capacity;
    
    public MyCircularQueue(int k) {
        capacity = k;
        data = new int[k];
        head = 0;
        tail = 0;
        size = 0;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) return false;
        data[tail] = value;
        tail = (tail + 1) % capacity; // 取模实现循环
        size++;
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % capacity; // 取模实现循环
        size--;
        return true;
    }
    
    public int Front() {
        if (isEmpty()) return -1;
        return data[head];
    }
    
    public int Rear() {
        if (isEmpty()) return -1;
        // tail 指向下一个写入位置，所以队尾元素在 (tail - 1 + capacity) % capacity
        return data[(tail - 1 + capacity) % capacity];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
}

为什么 Rear 要 (tail - 1 + capacity) % capacity？

tail 指向下一个写入位置（空槽位），最后写入的元素在 tail - 1。当 tail = 0 时，tail - 1 = -1，Java 中 -1 % capacity = -1（而不是 capacity - 1）。加上 capacity 再取模，保证结果非负：(-1 + capacity) % capacity = capacity - 1，正确。

2.4 完整验证

MyCircularQueue(3)：capacity=3, data=[_,_,_], head=0, tail=0, size=0

enQueue(1): data=[1,_,_], tail=1, size=1 → true
enQueue(2): data=[1,2,_], tail=2, size=2 → true
enQueue(3): data=[1,2,3], tail=0（循环！）, size=3 → true
enQueue(4): isFull()=true → false

Rear(): (0-1+3)%3 = 2, data[2]=3 → 3 ✓
Front(): data[0]=1 → 1 ✓

deQueue(): head=(0+1)%3=1, size=2 → true
enQueue(4): data[0]=4（tail=0），tail=1, size=3 → true
   data=[4,2,3]，head=1

Front(): data[1]=2 → 2 ✓
Rear(): (1-1+3)%3=0, data[0]=4 → 4 ✓

2.5 循环队列的工程应用

循环队列（环形缓冲区，Ring Buffer）是高性能系统中极为常见的数据结构：

Linux 内核的 kfifo：Linux 内核中的 kfifo 是一个单读者单写者的无锁环形缓冲区，生产者用 in 指针写入，消费者用 out 指针读取，两者互不阻塞。kfifo 的大小强制为 2 的幂次，这样取模可以用位与运算（index & (size - 1)）代替，性能更高。

Netty 的 ByteBuf：Netty 的 ByteBuf 维护 readerIndex 和 writerIndex，本质上是一个线性缓冲区（非循环），但 CompositeByteBuf 通过组合多个 buffer 实现了逻辑上的循环特性。

Kafka 的 ProducerBatch：Kafka Producer 的 RecordAccumulator 内部维护一个 BufferPool，每个内存块（batch buffer）用 ByteBuffer 实现，本质上也是固定大小的环形缓冲区逻辑——写满后触发 Flush。

LMAX Disruptor：LMAX 的 Disruptor 框架完全基于环形缓冲区（Ring Buffer）构建，通过无锁设计和 CPU 缓存行填充，实现了极高的单机吞吐量，是金融交易系统的常用选择。

环形缓冲区的核心优势

相比链表实现的队列，数组环形缓冲区的优势在于：

内存连续：CPU 缓存命中率高（对比链表节点的随机内存分布）

无 GC 压力：不产生中间对象（对 Java 应用尤其重要）

预分配：固定大小，内存使用可预测，不会因为动态扩容导致延迟抖动

第 3 章队列基础总结

3.1 Java 中的队列 API

// LinkedList 实现 Queue 接口
Queue<Integer> q = new LinkedList<>();
q.offer(1);      // 入队（返回 boolean）
q.poll();        // 出队（队空返回 null）
q.peek();        // 查看队头（队空返回 null）
 
// ArrayDeque 同时实现 Queue 和 Deque
Queue<Integer> q = new ArrayDeque<>();
// 相同的 offer/poll/peek 操作
 
// PriorityQueue（优先队列，不是 FIFO，按优先级出队）
Queue<Integer> pq = new PriorityQueue<>();

推荐使用 ArrayDeque 而不是 LinkedList：同样的原因——ArrayDeque 的内存布局更紧凑，无链接指针开销，性能更好。

3.2 双栈队列 vs 循环队列的对比

特性	双栈队列（LeetCode 232）	循环队列（LeetCode 622）
底层结构	两个动态栈	固定大小数组
容量限制	无（动态增长）	有（固定 k）
内存使用	动态（按需）	固定（预分配）
push 时间	$O (1)$ 摊还	$O (1)$
pop 时间	$O (1)$ 摊还	$O (1)$
工程场景	通用消息队列	高性能 I/O 缓冲区

下一篇预告

04 单调栈入门：每日温度与下一个更大元素进入本专栏最重要的技术——单调栈。LeetCode 739（每日温度）是单调栈的入门标准题：用一个从底到顶单调递减的栈， $O (n)$ 求出每个温度需要等多少天才能看到更高温度。LeetCode 496 和 503（下一个更大元素 I/II）是 739 的变体，分别考察”两个数组中的映射”和”循环数组的处理”。掌握这三道题，等于掌握了单调栈的 80% 使用场景。

汀的知识碎片

文章导航

03 队列基础：用栈实现队列与循环队列设计

队列基础：用栈实现队列与循环队列设计

摘要

第 1 章 LeetCode 232：用栈实现队列

1.1 题目

1.2 问题分析

1.3 双栈队列：两种搬移时机

1.4 代码实现

1.5 摊还分析

1.6 手动验证

第 2 章 LeetCode 622：设计循环队列

2.1 题目

2.2 为什么需要循环队列

2.3 判满的经典技巧：牺牲一个槽位

2.4 完整验证

2.5 循环队列的工程应用

第 3 章队列基础总结

3.1 Java 中的队列 API

3.2 双栈队列 vs 循环队列的对比

下一篇预告

On this page

Backlinks

汀的知识碎片

文章导航

03 队列基础：用栈实现队列与循环队列设计

队列基础：用栈实现队列与循环队列设计

摘要

第 1 章 LeetCode 232：用栈实现队列

1.1 题目

1.2 问题分析

1.3 双栈队列：两种搬移时机

1.4 代码实现

1.5 摊还分析

1.6 手动验证

第 2 章 LeetCode 622：设计循环队列

2.1 题目

2.2 为什么需要循环队列

2.3 判满的经典技巧：牺牲一个槽位

2.4 完整验证

2.5 循环队列的工程应用

第 3 章 队列基础总结

3.1 Java 中的队列 API

3.2 双栈队列 vs 循环队列的对比

下一篇预告

On this page

Backlinks

第 3 章队列基础总结