一、起源:两种受限的线性结构

1.1 线性表的自由度过剩

线性表允许在任意位置插入、删除、按下标访问,这种自由度在实现上是"全部能力",在语义上却是"没有承诺"。调用方拿到一个线性表时,无法从类型上判断它会被怎么用,因此必须为每种可能的位置关系分别准备代码:

  • 在头部插入需要考虑下标整体后移,在尾部插入则不必
  • 删除任意位置需要先定位,删除两端只需操作边界
  • 遍历顺序与插入顺序是否一致,依赖于使用者的约定而非结构的保证

自由度带来的第二个后果是实现代价的不可预期。同一次 add 调用,落在尾部是均摊 O(1),落在中间是 O(n),差别由调用点的下标决定。读代码时无法从方法名判断开销量级,只能回到实现处确认。

1.2 限制操作换来什么

把可操作的位置从"任意"收敛到固定的一到两处,立即得到三个结果。

语义确定。只有两处可操作时,"取出一个元素"的位置就不再需要参数,返回的元素身份由结构本身的规则决定,调用方不必说明"取哪一个"。

实现简单。下标维护集中在少数几个字段上,不需要处理任意位置的搬移逻辑,也不需要为随机访问准备寻址方式。顺序存储下,栈只需要一个栈顶指针,队列只需要队头与队尾两个指针。

代价可预期。每个操作的开销由结构决定而不是由调用点的参数决定。同样的调用,无论在第几次执行,时间复杂度都相同(均摊意义下)。

这三条对应到抽象数据类型(ADT)的视角,就是"接口收窄换取实现自由":对外只承诺少数几个操作,对内可以在顺序存储与链式存储之间选择而不影响调用方。栈与队列的 ADT 定义、与线性表的层次关系见 抽象数据类型(ADT)。

1.3 后进先出对应的现实问题

后进先出(LIFO,Last In First Out) 描述的是这样一类问题:最近发生的事情最需要被优先处理。

  • 回退。编辑器的撤销、浏览器的后退、路径的取消,处理的顺序与发生顺序相反。最后做出的动作最先被撤销,否则状态无法回到上一步。
  • 嵌套与配对。括号、标签、函数调用、表达式的括号层级,都具有包含关系。内层结构必须先于外层结束,因此需要一个"记住最近打开的内层"的结构。
  • 回溯。深度优先搜索、迷宫求解、语法分析的试探过程,都需要在走不通时回到上一个分叉点,而"上一个"就是最近一次做出的选择。
  • 依赖展开。递归调用、目录树遍历、表达式求值,外层的计算依赖内层先返回结果,调用关系本身构成嵌套。

这些场景的共同结构是嵌套:处理过程不是一条直线,而是有进有出、且进出顺序相反。

1.4 先进先出对应的现实问题

先进先出(FIFO,First In First Out) 描述的是另一类问题:先到达的事情先被处理,即处理顺序等于到达顺序。

  • 排队与公平。打印机任务、窗口服务、订单处理,先提交的先得到服务,结构本身承担了公平性保证。
  • 按层展开。宽度优先搜索、按距离扩散、按层级遍历,处理的自然顺序是"发现顺序"。
  • 缓冲与削峰。生产速率与消费速率不一致时,先到的数据先被消费,队列长度反映积压量。
  • 流水线。数据在中转环节之间传递,每一环按到达顺序取走,顺序不能被后来的数据插队。

与栈的嵌套结构相对,队列对应的是平铺的先后关系:没有回退需求,只有顺序需求。

1.5 两种结构的共同点

栈与队列都属于线性逻辑结构,都只对线性表的操作位置加以限制,因此常被合称受限线性表 ADT。它们的差异只有一处:限制的可操作端是一端还是两端,以及两端的分工是"同一端进出"还是"一端进另一端出"。

结构 可操作端 进出分工 语义
线性表 任意位置 任意 无顺序承诺
栈 一端(栈顶) 同一端进出 后进先出
队列 两端(队头、队尾) 一端进、另一端出 先进先出
双端队列 两端 两端均可进出 栈与队列的超集

二、原理

2.1 栈

2.1.1 定义与操作集

栈是限定仅在表的一端进行插入和删除的线性表,允许操作的一端称为栈顶(top),另一端称为栈底(bottom)。

操作 语义 通常复杂度
push(e) 元素入栈,成为新的栈顶 O(1)(顺序存储含均摊扩容代价)
pop() 弹出并返回栈顶元素 O(1)
peek() / top() 读取栈顶元素但不弹出 O(1)
isEmpty() 判断栈是否为空 O(1)
size() 返回元素个数 O(1)

栈的操作全部发生在同一端,因此不需要"位置"参数,也不需要移动除栈顶之外的任何元素。这是它在实现上比线性表简单得多的根本原因。

2.1.2 数组实现与链表实现

顺序栈(数组实现):用一段连续空间存放元素,额外维护一个栈顶指针(或下标)标记当前栈顶位置。

优势是元素连续存放,访问栈顶是常数时间,且符合 CPU 缓存局部性;代价是容量有限,超出时需要扩容并整体复制。

链式栈(链表实现):用链表节点存放元素,链表的头部作为栈顶。

优势是不需要预先确定容量,也没有扩容复制;代价是每个元素多一个节点对象的开销,且节点在堆中分散分布,访问栈顶之外的元素(本就不提供该操作)与扩容时的内存局部性都更差。

两种实现都提供相同的操作集,选择依据是容量是否可预估、对单元素内存开销的敏感程度,以及是否要求严格的常数时间上界(链表实现的每次 push 都是严格 O(1),数组实现在扩容那一次是 O(n))。

2.1.3 栈顶指针的两种约定

顺序栈的边界条件是实现中最容易出错的部分,原因在于栈顶指针可以有两种约定,两者的初始值、判空条件与判满条件各不相同。

约定 top 含义 初始值 栈空 栈满 入栈 出栈
约定一 指向栈顶元素本身 −1 top == -1 top == capacity - 1 data[++top] = e e = data[top--]
约定二 指向栈顶元素的下一个空位 0 top == 0 top == capacity data[top++] = e e = data[--top]

两种约定等价,但对 ++ 与 -- 的位置要求相反:约定一先移动指针再写数据,约定二先写数据再移动指针。混用两种约定会造成"入栈写错位置"或"出栈少弹一个元素",且在栈中元素个数不为边界值时往往不立即报错,只在栈空或栈满附近暴露。

用约定一实现顺序栈:

class ArrayStack:
    def __init__(self, capacity):
        self.__data = [None] * capacity
        self.__top = -1                 # 约定一:top 指向栈顶元素

    def push(self, e):
        if self.is_full():
            raise OverflowError("stack overflow")
        self.__top += 1
        self.__data[self.__top] = e

    def pop(self):
        if self.is_empty():
            raise IndexError("stack underflow")
        e = self.__data[self.__top]
        self.__data[self.__top] = None  # 释放引用
        self.__top -= 1
        return e

    def peek(self):
        if self.is_empty():
            raise IndexError("stack is empty")
        return self.__data[self.__top]

    def is_empty(self):
        return self.__top == -1

    def is_full(self):
        return self.__top == len(self.__data) - 1

2.1.4 栈溢出与下溢

上溢(overflow):栈已满时继续入栈。顺序栈的容量在创建时确定,若无扩容机制,上溢必须被显式处理,否则会写入越界位置。

下溢(underflow):栈已空时继续出栈。这是更常见的缺陷来源,因为空栈弹出在多数实现中返回 null 或抛异常,而调用方往往只处理了正常返回值,把 null 当作有效元素继续使用。

需要区分两个层次的"栈溢出":

名称 所在层次 触发条件 处置方向
数据结构栈上溢 数据结构 满栈入栈 扩容、拒绝写入或返回错误
StackOverflowError JVM 运行时 线程的虚拟机栈深度超限(递归过深、调用链过长) 改为迭代、收敛递归深度、调整 -Xss

两者名称相近但成因不同:前者是自定义结构中的容量判断问题,后者是线程栈帧总数超限,其详细机制与线程栈的内存归属见 JVM 内存结构与垃圾回收 中虚拟机栈一节的说明。

2.1.5 调用栈与函数调用过程

函数调用是栈在运行时层面最普遍的应用。每次调用发生时,JVM 在当前线程的虚拟机栈上压入一个栈帧,保存该次调用必需的信息:

线程的虚拟机栈(向低地址方向增长)
┌────────────────────────────┐
│  栈帧:main                 │  ← 栈底
│    局部变量表 / 操作数栈     │
│    动态链接 / 返回地址       │
├────────────────────────────┤
│  栈帧:f                    │
│    (f 调用 g 时的现场)     │
├────────────────────────────┤
│  栈帧:g                    │  ← 当前栈顶
└────────────────────────────┘

调用与返回的过程本身就是压栈与弹栈:调用时压入新帧,被调用方法执行结束(或抛出异常沿调用链传播)时弹出该帧,控制权回到返回地址处继续执行。

由此可以解释几个现象:

  1. 递归深度受线程栈容量限制。每次递归调用压入一帧,帧的累计大小超过 -Xss 指定容量时抛 StackOverflowError。同样的递归逻辑,局部变量越多、参数越大,单帧越大,能承受的深度越浅。
  2. 异常栈信息与调用栈同构。打印出的异常堆栈就是当时的栈帧序列,从上到下对应由内到外的调用关系,因此栈顶(最上面的帧)即抛出点。
  3. 尾调用在 JVM 上不自动优化。Java 不保证尾递归消除,形如 return f(...) 的递归写法依然会累积栈帧。
  4. 线程数增加与单线程栈深度是一对权衡。栈容量由 -Xss 决定,调大单线程可递归的深度会增加每个线程的内存占用;高并发下线程数多时,栈总量的挤压可能表现为无法再创建线程。

递归与栈的这层对应关系是后文"深度优先遍历用栈实现"的基础:显式栈不过是用堆上的数组手工模拟了调用栈的结构。

2.2 栈的应用

2.2.1 括号匹配与合法性校验

判断一个只含括号的字符串是否合法,条件是三条:任意前缀中左括号数量不少于右括号;左右括号数量相等;同一类型的括号按正确顺序闭合。

栈的解法是:左括号入栈,遇到右括号时与栈顶比较,类型一致则弹出,不一致或不匹配则失败,扫描结束后栈为空才算合法。

PAIRS = {')': '(', ']': '[', '}': '{'}

def is_valid(s: str) -> bool:
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack          # 扫描结束仍有剩余左括号,说明未闭合

时间为 O(n),空间为 O(n)(最坏情况下全部为左括号)。第三个条件的校验不能省略:只比较数量会放过 ([)] 这类交叉嵌套。

同一思路可推广到标签闭合检查(HTML、XML 的开闭标签匹配)、模板语法的嵌套校验、路径表达式的括号补全。

2.2.2 表达式求值

表达式的三种形式由运算符相对操作数的位置区分:

形式 示例 特点
中缀 3 * (4 + 5) 人类可读,需要括号与优先级规则
后缀(逆波兰) 3 4 5 + * 无括号、无优先级,求值只需一个栈
前缀(波兰) * 3 + 4 5 同后缀,顺序改为从右向左扫描

后缀求值的过程:从左向右扫描,遇到操作数就入栈,遇到运算符就弹出两个操作数,先弹出的为右操作数、后弹出的为左操作数,运算结果再入栈,扫描结束时栈顶即结果。整个过程只需要一个操作数栈,且不需要判断优先级。

中缀转后缀使用调度场算法(shunting-yard):输出序列与运算符栈分开维护,操作数直接输出;运算符入栈前,把栈顶所有优先级不低于当前运算符的运算符弹出并输出;左括号直接入栈,遇到右括号时弹出直到左括号;扫描结束后清空运算符栈。

优先级与括号的配合是关键:左括号在栈中被视为优先级最低的"墙",阻止栈内运算符越过它弹出,从而保证括号内的运算在括号外之前完成。完整实现见第三部分。

2.2.3 进制转换

把十进制整数转换为任意 base 进制,方法是反复取余:n % base 得到最低位,n / base 继续处理高位。余数的产生顺序是从低位到高位,而输出的书写顺序是从高位到低位,因此余数需要逆序输出,这正是栈的适用场景。

def to_base(n: int, base: int) -> str:
    digits = "0123456789ABCDEF"
    if n == 0:
        return "0"
    stack = []
    while n:
        stack.append(digits[n % base])
        n //= base
    return "".join(stack[::-1])

同样的"逆序输出"模式出现在其他场景中:把链表逆序打印、把数字位的处理结果反向拼接、把路径从叶子回溯到根。

2.2.4 撤销与回退

编辑器的撤销栈保存操作记录,每次执行可撤销操作时压入一条记录,撤销时弹出最近一条并执行其反向操作。重做栈保存被撤销的记录,撤销时把记录从撤销栈移入重做栈,重做时反向移动。

两个栈的组合给出了清晰的语义边界:

动作 撤销栈 重做栈
执行新操作 压入 清空(新分支产生后原重做路径失效)
撤销 弹出并执行反向操作 压入该操作
重做 压入该操作 弹出并执行

浏览器前进后退使用的是同一模型,见第三部分工程应用一节。

2.2.5 深度优先遍历的非递归实现

递归形式的深度优先遍历依赖系统调用栈保存"返回位置",改写成迭代时,需要把这些信息显式地放进一个栈里。

以前序遍历为例,递归形式先访问当前节点,再依次递归左右子树;迭代形式用一个栈保存待访问节点,访问当前节点后把子节点压栈,压栈顺序与访问顺序相反(先压右子节点,再压左子节点,弹栈时才先处理左子节点)。

这一改写带来两点实际收益:递归深度不再受线程栈容量限制,栈空间转移到堆上,可容纳的深度由堆大小决定;以及可以在迭代过程中插入中断、暂停、恢复等控制逻辑,而递归形式难以在帧之间保存中间状态。

代价是显式栈保存的是"待访问节点",与递归时的"栈帧"不完全等价。递归可以在返回后继续使用局部变量,而简单的显式栈实现丢掉了这一上下文,因此在需要后序处理(子树处理完再处理根)时,往往需要额外记录状态或使用访问标记。

2.2.6 单调栈

单调栈指栈内元素保持单调性的栈。它不是一种新的存储结构,而是规定了出栈条件的使用方式:新元素入栈前,把破坏单调性的栈顶元素全部弹出。

以"下一个更大元素"为例:对数组中每个位置,求其右侧第一个比它大的值。维护一个从栈底到栈顶递减的栈,遍历到 nums[i] 时,所有栈顶元素对应值小于 nums[i] 的位置,其下一个更大元素就是 nums[i],弹出并记录,然后把 i 入栈。

public static int[] nextGreater(int[] nums) {
    int[] res = new int[nums.length];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();     // 存下标,对应值自栈底向栈顶递减
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            res[stack.pop()] = nums[i];            // 栈顶位置的下一个更大元素确定
        }
        stack.push(i);
    }
    return res;
}

复杂度是 O(n):每个下标恰好入栈一次、出栈一次,内层 while 的累计执行次数不超过 n,因此总代价是线性的,而不是嵌套循环表面上的 O(n²)。

"下一个更小元素" 只需把比较方向反过来,改维护递增栈。柱状图最大矩形是单调栈最经典的应用:对每根柱子,以其高度为高的最大矩形,宽度由左右两侧第一个更矮的柱子界定,而这两个边界恰好可以用一次递增栈扫描同时求出。实现见第三部分。

2.3 队列

2.3.1 定义与操作集

队列是只允许在一端插入、在另一端删除的线性表,允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)。

操作 语义 通常复杂度
offer(e) / enqueue(e) 元素入队,成为新的队尾 O(1)(顺序存储含扩容代价)
poll() / dequeue() 删除并返回队头元素 顺序队列 O(n) 或循环队列 O(1);链式队列 O(1)
peek() 读取队头元素但不删除 O(1)
isEmpty() 判断队列是否为空 O(1)

队列与栈的唯一差别在操作端的分工上,但这一差别导致了实现上的不对称:栈只有一端需要维护,队列需要同时维护两端,因此对存储结构提出了额外要求——顺序存储下必须解决"队头出队后留下的空位如何复用"的问题。

2.3.2 顺序队列的假溢出与循环队列

用普通数组实现队列时,队头与队尾都用递增的下标表示:入队时 rear++,出队时 front++。问题很快出现:出队只移动 front,并不搬移数据,被删除元素占用的位置永久闲置。经过若干次入队出队后,rear 到达数组末尾,而 front 之前还有大量空位,此时既不能入队(数组已满)也不是真的存满,这种现象称为假溢出。

解决方式是让下标在到达数组末尾后回到 0,把数组在逻辑上首尾相接,即循环队列(环形队列)。下标的推进由取模完成:

front = (front + 1) % capacity
rear  = (rear + 1)  % capacity

取模的结果是 front 与 rear 都可能回绕,于是"队空"与"队满"不再能用 front >= rear 这类单调比较判断。而在不加辅助信息的情况下,front == rear 既可能是空队列,也可能是装满一圈后的队列,二者无法区分。

解决这一歧义有三种做法,工程实现的选择集中在前两种:

做法 判空 判满 可容纳元素数 代价
牺牲一个槽位 front == rear (rear + 1) % capacity == front capacity - 1 少用一个存储单元,无需额外字段
维护计数或标记位 size == 0 size == capacity capacity 多维护一个整型字段,入队出队各需同步更新
维护 tag 标志 front == rear 且 tag == 0 front == rear 且 tag == 1 capacity 逻辑分支更多,实际使用较少

第一种做法的元素个数为 (rear - front + capacity) % capacity,第二种直接读 size。计数法的优势除了容量不浪费之外,还在于把"个数"这个高频查询从取模运算变成了字段读取,并让判空判满的代码与实际语义一致,不易写错。

2.3.3 链式队列

链式队列用链表实现,队头对应链表头部,队尾对应链表尾部,同时持有两个引用。

  • 出队是删除链表头节点,入队是在尾节点后追加,两者都是 O(1)。
  • 需要同时维护头尾指针,且入队时要处理"队列原本为空"的边界(此时新节点既是头也是尾)。
  • 不存在假溢出与容量上限问题,也不需要取模运算,代价是每个元素一个节点对象的开销。

在需要严格 O(1) 上界且长度波动很大的场景下,链式队列比顺序队列更合适;但若实现语言的标准库已提供基于环形数组的双端队列(如 Java 的 ArrayDeque),其综合性能通常优于手写链表队列。

2.3.4 双端队列

双端队列(deque,double-ended queue) 允许在两端插入和删除,是栈与队列的超集:

使用限制 等价结构
只允许一端插入、同一端删除 栈
只允许一端插入、另一端删除 队列
两端都可以插入和删除 双端队列本身

因此双端队列常被实现为标准库中唯一的"受限线性结构"基础设施——Java 的 ArrayDeque 既可当栈用(push / pop / peek),也可当队列用(offer / poll / peek),还可以在两端操作(offerFirst / pollLast)。

ArrayDeque 的实现是环形数组:容量取 2 的幂,用 head 表示队首元素下标、tail 表示队尾元素的下一个下标,下标推进用位与代替取模((tail + 1) & (length - 1))。空队列用 head == tail 判定,因此数组实际可容纳的元素数比长度少一个;入队后 tail 追上 head 时触发容量翻倍。

双端队列的两个使用约束值得注意:多数实现不允许插入 null(因为 poll 返回 null 需要表示空队列,无法与元素值区分),且 ArrayDeque 不支持按下标随机访问。

2.3.5 阻塞队列与生产者消费者模型

生产者消费者模型描述的是速率不匹配的两方通过一个共享缓冲区解耦:生产者放入数据,消费者取出数据,双方不需要知道对方的身份与处理速度。

队列是这个模型的载体,而模型的正确性依赖两个条件:

  1. 队列满时生产者等待,队列空时消费者等待。等待必须释放锁并在条件满足时被唤醒,否则生产者会占着锁自旋,消费者永远拿不到锁。
  2. 条件判断必须放在循环中。线程被唤醒后条件未必已经成立(虚假唤醒,或被其他线程抢先消费),因此必须重新检查而不是直接继续。
public class BoundedBuffer<E> {
    private final Queue<E> queue = new ArrayDeque<>();
    private final int capacity;

    public BoundedBuffer(int capacity) {
        this.capacity = capacity;
    }

    public synchronized void put(E e) throws InterruptedException {
        while (queue.size() == capacity) {
            wait();                       // 队列满:等待消费者腾出空间
        }
        queue.offer(e);
        notifyAll();
    }

    public synchronized E take() throws InterruptedException {
        while (queue.isEmpty()) {
            wait();                       // 队列空:等待生产者放入数据
        }
        E e = queue.poll();
        notifyAll();
        return e;
    }
}

有界队列在此模型中有额外意义:它构成背压。队列满时生产者被阻塞,意味着上游的处理速率被下游的实际消费速率限制住,系统不会在前端持续接收而在内存中无限堆积。无界队列放弃了这条约束,生产速率长期高于消费速率时,积压表现为堆内存持续增长,最终以 OutOfMemoryError 结束。

标准库通常把上述同步逻辑封装为阻塞队列,直接提供 put(满时阻塞)与 take(空时阻塞),以及不阻塞的 offer / poll(可带超时参数)。基于锁与条件变量的具体实现、无界队列的风险与线程池的配合方式见 Java 并发编程 中线程池与工作队列一节。

2.4 队列的变体

2.4.1 优先队列与堆

普通队列按到达顺序出队,优先队列按元素优先级出队:每次取出的是当前优先级最高(或最低)的元素,与入队顺序无关。

优先队列的常见实现是二叉堆。堆是一棵完全二叉树,用数组存储,父子下标关系由算术式给出(下标 i 的子节点为 2i+1 与 2i+2,父节点为 (i-1)/2),并满足堆序性质:每个节点的值不大于(小顶堆)或不小于(大顶堆)其子节点。

操作 复杂度 说明
peek() O(1) 堆顶即最优元素
offer(e) O(log n) 追加到数组末尾后向上调整(上浮)
poll() O(log n) 取走堆顶后把末尾元素移到堆顶并向下调整(下沉)
contains(e) / 任意删除 O(n) 堆只保证堆序,不保证可查找

两个容易误用的性质必须明确:

  • 优先队列不是完全有序的。堆只保证堆顶是最值,其余元素的相对顺序没有任何承诺。迭代优先队列得到的顺序通常不是出队顺序,需要有序序列时必须连续 poll。
  • 相等优先级的顺序不确定。堆调整不维护同优先级元素的到达顺序,需要稳定语义时必须在比较器中引入额外的次序键。

优先队列与堆的完整机制(建堆的线性代价、上浮与下沉的实现、堆排序、与快速选择的对比)见 堆与优先队列,此处只给出与队列语义相关的边界。

2.4.2 单调队列

单调队列是双端队列的一种使用方式:队列内元素保持单调,且队首始终是当前窗口内的最优值。与单调栈的区别在于它额外维护了"过期"逻辑——窗口左边界右移时,越界的队首元素必须被移除。

典型应用是滑动窗口最大值:给定数组与窗口大小 k,求每个窗口内的最大值。

做法是用双端队列保存下标,队列内对应的值自队首向队尾递减:

  1. 新元素入队前,从队尾弹出所有不大于它的元素(它们不可能是后续任何窗口的最大值);
  2. 新元素从队尾入队;
  3. 若队首下标已滑出窗口左边界,从队首弹出;
  4. 窗口形成后,队首下标对应的值即当前窗口最大值。

每个下标最多入队一次、出队一次,整体时间 O(n),空复 O(k)。实现见第三部分。

与优先队列相比,单调队列的优势在于它利用了"窗口滑动"这个额外信息:元素的过期顺序与入队顺序一致,因此可以用一个双端队列同时完成维护最值与淘汰过期,而不需要堆的 O(log n) 更新。

2.4.3 延迟队列与时间轮

延迟队列要求元素在指定时间到达之前不可被取出,到期后才按时间顺序出队。它把"顺序"从入队顺序改为到期时间顺序,因此实现上通常复用优先队列:以到期时间戳为键的小顶堆,队首即最早到期的任务。

带延迟的对象不可取出时,通常用条件变量的 awaitNanos 或 poll(timeout) 阻塞到最早到期时间,避免空轮询。

当延迟任务的数量很大且到期时间分散时,基于堆的实现每次入队出队都要 O(log n) 调整,会成为瓶颈。时间轮(timing wheel) 用另一种结构分摊这一代价:

  • 一个固定长度的环形数组,每个槽位代表一个时间刻度,槽位内挂一个任务链表(或小堆)
  • 插入任务时按到期时间计算出对应的槽位,直接挂入,复杂度 O(1)
  • 一个指针按固定 tick 周期推进,走到某个槽位时执行该槽内的到期任务

时间轮的代价有两处:精度受 tick 长度限制,到期时间不是 tick 整数倍的任务需要向上取整;长延时的任务需要跨多圈或多层时间轮(分级时间轮)来表达,否则单圈无法覆盖。相反,堆实现的精度不受限制,代价是每次操作的 O(log n)。多级时间轮的层级设计、堆与时间轮在工程中的取舍与观测方式见 工程中的数据结构。

工程中的延迟队列还有一类实现落在外部存储上,例如用 Redis 有序集合以到期时间为 score,由轮询脚本取出到期成员。这类实现可以跨进程共享、任务不随进程重启丢失,但没有确认与重试语义;两种实现方式的选择依据见 Redis 缓存实践 中延时队列与轻量任务调度一节。

2.4.4 消息队列与数据结构队列的层次差异

"消息队列"与数据结构中的队列共享 FIFO 的基本思想,但两者不在同一层次上。

维度 数据结构队列 消息队列(中间件)
所在层次 进程内的内存结构 跨进程、跨主机的独立服务
生命周期 随持有它的对象一起消失 独立于生产者和消费者进程,可持久化
元素语义 内存中的对象引用或值 序列化后的消息,含消息头元数据
队列满 阻塞生产者或拒绝写入 存储水位上限,超出后反压或拒绝
消费进度 队列自身即进度,出队即消失 确认删除或位点推进,与消息存储分离
重放能力 无,元素出队即不可恢复 日志型模型下位点可回退并重放
附加机制 无 投递语义、确认、重试、死信、分区、消费者组

因此两者的关注点不同:数据结构队列关心的是内存布局、边界条件与并发同步;消息队列关心的是投递语义(最多一次、至少一次、恰好一次)、顺序性的粒度、积压与位点、以及跨系统的最终一致。后端服务中的"队列"通常是两者的组合——中间件承担跨进程传输与持久化,消费者进程内部再用一个阻塞队列把消息交给工作线程。消息队列的模型分层(点对点与发布订阅、中心化模型与日志型模型、分区与位点)见 消息队列基础与模型。

2.5 经典变换

栈与队列可以相互模拟,这类题目的意义不在于"用不上就替换掉",而在于它们把两种结构的操作集映射关系完整暴露出来:栈能提供的只有一端操作,队列需要的是一端进、另一端出的能力,两者的差距必须由额外的搬移来弥补。

2.5.1 两个栈实现队列

设栈 in 负责入队、栈 out 负责出队:

  • offer(e):把 e 压入 in
  • poll():若 out 非空,弹出 out 栈顶;若 out 为空,把 in 的全部元素依次弹出并压入 out,然后弹出 out 栈顶

关键在于元素只在 out 为空时整体搬运一次。每个元素在整个生命周期内最多被搬运一次(从 in 到 out),因此 n 次入队与 n 次出队的累计代价是 O(n),单次操作均摊 O(1)。若每次出队都搬运,单次代价会退化到 O(n)。

public class QueueByTwoStacks<E> {
    private final Deque<E> in = new ArrayDeque<>();
    private final Deque<E> out = new ArrayDeque<>();

    public void offer(E e) {
        in.push(e);
    }

    public E poll() {
        shift();
        return out.poll();
    }

    public E peek() {
        shift();
        return out.peek();
    }

    public boolean isEmpty() {
        return in.isEmpty() && out.isEmpty();
    }

    private void shift() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());       // 逆序倒入,队头来到 out 栈顶
            }
        }
    }
}

2.5.2 两个队列实现栈

反过来,用两个队列模拟栈有两种等价思路,代价都不可避免:

  • 入栈代价 O(n):元素入队到一个空队列后,把另一个队列中的全部元素依次搬到当前队列的尾部,使新元素位于队头。出栈直接从队头取,O(1)。
  • 出栈代价 O(n):元素直接入队,出栈时把当前队列的前 n-1 个元素搬到另一个队列,剩下的队头即栈顶。

两种方案的单次最坏代价都是 O(n),无法均摊到 O(1),原因是队列的先进先出语义与栈的后进先出正好相反,每一次顺序反转都必须显式搬移。这也说明:用两个栈实现队列可行且高效(借助一次逆序即可对齐语义),而用队列实现栈只能靠反复搬移。

一个变体是用一个队列实现栈:入栈时把新元素入队,再把该元素之前的所有元素重新出队并入队,效果等同于把新元素移到队头,单次入栈 O(n)。

2.5.3 常数时间取最小值的栈

要求栈的 push、pop、min 都是 O(1)。做法是用一个辅助栈同步记录"截至当前栈顶的最小值":

  • 主栈保存数据,辅助栈保存当前最小值
  • push(x):主栈压入 x;辅助栈压入 min(x, 辅助栈栈顶)(辅助栈为空时直接压入 x)
  • pop():两栈同步弹出
  • min():返回辅助栈栈顶
public class MinStack {
    private final Deque<Integer> data = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();   // 栈顶为当前最小值

    public void push(int x) {
        data.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(mins.peek(), x));
    }

    public void pop() {
        data.pop();
        mins.pop();
    }

    public int top() {
        return data.peek();
    }

    public int min() {
        return mins.peek();
    }
}

空间代价是 O(n)(辅助栈与主栈等长)。可以优化为辅助栈只在最小值发生变化时压入,弹出时判断是否与辅助栈栈顶相等——代价是相等元素的处理需要额外判断,且 pop 时需要比较而非无条件弹出。另一种思路是差值法,用主栈保存"当前值与当时最小值的差",把最小值本身放在一个单独字段中,代价是需要处理整数溢出。

2.5.4 循环队列的容量设计

容量设计围绕"判空与判满如何区分"展开,三种做法的取舍已列在 2.3.2 节。实现层面的两个具体选择:

  1. 牺牲一个槽位的做法:数组长度即申请容量,实际可存 capacity - 1 个元素。对外暴露的"容量"如果按数组长度声明,会造成"队列未满却拒绝入队"的困惑,因此对外语义应明确为"最多可存元素数",并按此计算数组长度(即数组长度取 maxSize + 1)。
  2. 计数法的做法:数组长度即最大元素数,另用 size 字段表示当前个数,判满为 size == capacity,时间复杂度与取模方案相同,但省去了"少用一个槽位"的语义负担。

Java 的 ArrayBlockingQueue 使用计数法:内部是定长 Object[]、一个 count 字段、一个 putIndex 与一个 takeIndex,下标推进用 (++i == items.length) ? 0 : i 完成回绕,用一个锁与两个条件(notEmpty、notFull)配合,而不是取模运算。计数法的另一好处是 size() 可以 O(1) 返回精确值。

2.6 与遍历的关系

图的深度优先遍历与广度优先遍历分别使用栈与队列,这不是实现者的随意选择,而是由两种遍历的定义直接决定的。

2.6.1 深度优先用栈

深度优先的策略是"沿一条路径走到底,走不通再回退"。回退的目标永远是最近一次做出的选择,即最后被展开的节点——这正是一个后进先出的顺序。

  • 递归实现时,回退能力由系统调用栈提供:每进入一个节点压入一个栈帧,返回时弹出,返回点即上一个分叉节点。
  • 迭代实现时,把待展开节点放入显式栈:弹出栈顶节点展开,把它的未访问邻居压入,下一轮弹出的就是最近压入的邻居,遍历由此沿这条路径继续深入。

用非栈的容器实现深度优先,需要在每次选择时额外记录"回到哪个节点继续",等价于手工重建了栈的功能。

2.6.2 广度优先用队列

广度优先的策略是"先访问所有距离为 1 的节点,再访问距离为 2 的节点"。展开顺序必须等于发现顺序:先被发现的节点,其邻居应当先于后发现的节点的邻居被访问——这正是一个先进先出的顺序。

void bfs(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();          // 先发现的先展开
        visit(node);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

队列在此不仅是"待访问集合",还隐含了层次信息:同一层的节点在队列中是连续的一段。需要按层处理(如求最大深度、按层输出、找最短路径长度)时,可以在每轮循环开始时记录当前队列长度,作为本层的节点数。

遍历方式 容器 取出顺序 隐含信息 典型用途
深度优先 栈(或递归调用栈) 最近压入的先出 当前路径与分叉点 连通性判断、拓扑排序、回溯求解
广度优先 队列 最早入队的先出 层次与距离 无权图最短路径、按层遍历、扩散模拟

三、实现

3.1 栈实现要点

3.1.1 数组扩容与均摊代价

顺序栈在满栈时的处理有三种选择:抛异常、拒绝入栈(返回失败)、扩容。前两种把容量约束暴露给调用方,适用于容量边界本身就是语义一部分的场景(如固定大小的解析栈);第三种对调用方透明,是通用容器的默认行为。

扩容通常按倍数增长(翻倍或 1.5 倍)。以翻倍为例,容量从 c 增长到 2c 时,需要分配新数组并把 c 个元素复制过去。从空栈连续入栈 n 次,发生的复制总量为:

1 + 2 + 4 + ... + n/2 < n

即总复制量小于最终元素数,因此每次入栈的均摊代价为 O(1),而不是每次 O(n)。

扩容的代价不只在时间上。扩容瞬间,旧数组(容量 c)与新数组(容量 2c)同时存在,结构本身的内存占用达到新容量的 1.5 倍。对于元素数量上百万的栈,这个峰值可能直接触发 GC 甚至内存不足,与集合扩容时的峰值问题同源,容量预设的理由与估算方式见 Java 集合框架实现原理。

3.1.2 链表实现的内存开销

链式栈不需要扩容,但每个元素都要一个节点对象。在 64 位 JVM 开启压缩指针的条件下,一个含数据引用与 next 引用的节点约占 24 字节(对象头 12 字节 + 两个引用各 4 字节,按 8 字节对齐),而数组实现中一个元素只占数组里的一个引用位(4 字节)。

即同样数量的元素,链式实现的结构开销约为数组实现的数倍。这还未计入节点分散分配带来的缓存局部性损失:数组中的相邻元素位于同一缓存行附近,节点则可能分布在堆的任意位置,遍历时几乎每次都缓存未命中。

结论是:只有在容量确实无法预估、或需要对单次操作给出严格常数上界时,链式栈才有明显优势;否则优先使用基于数组的实现。LinkedList 与 ArrayList 的单元素开销对照见 Java 集合框架实现原理。

3.1.3 线程安全的实现思路与代价

栈本身不包含并发语义,多线程共享同一个栈时,push 与 pop 内部的"读指针—改指针—写数据"三步必须整体受保护。可行方案按代价递增排列:

方案 实现要点 代价
方法级同步 所有公开方法加 synchronized 全表锁,读写串行;锁粒度最大
显式锁 内部持有一个 ReentrantLock,临界区只包住指针更新与数据写入 与同步方法相近,但可加超时、可中断、可分条件
无锁链表栈 用 CAS 更新栈顶引用(Treiber 栈) 无阻塞,但存在 ABA 问题(需带版本号的引用);size() 无法 O(1) 精确统计
线程私有 每个线程持有自己的栈,不共享 无同步开销,但跨线程的结果汇总需要额外处理

两点值得注意:

  1. 锁保护的是不变式而不是操作。"栈顶指针始终指向有效元素"这个不变式在指针更新与数据写入之间会短暂不成立,因此锁的范围必须覆盖这两步,只保护指针赋值是不够的。
  2. 可见性与原子性是两个问题。即使把指针声明为 volatile,push 仍然是不安全的——两个线程可能读到同一个栈顶,都把自己的元素挂上去,造成其中一个元素的丢失。相关机制见 Java 并发编程 中内存可见性与 JMM 一节。

需要阻塞语义的队列另有专门的实现(阻塞队列),它把"等待条件成立"作为一等能力,而不是要求调用方自行轮询。

3.2 循环队列实现要点

三点实现细节决定了循环队列是否可靠。

第一,容量与元素个数的表示方式要一致。 使用 size 字段时,数组长度就是最大元素数;使用"牺牲一个槽位"时,数组长度比最大元素数多 1。两者混用会造成"队列明明还有空位却拒绝入队"或"入队覆盖未出队元素"。

第二,判满与判空必须由同一套信息推导。 若判空用 size、判满用 head == tail,两个判断的依据不同源,在所有元素出队后 head 与 tail 必然相等,随后入队时若又按 size 判断,逻辑上不会出错但代码的意图已经混乱,维护时极易被误改。

第三,下标推进必须取模,且模数要与数组长度一致。 用 capacity - 1 作掩码(位与运算)时,数组长度必须是 2 的幂,否则下标会落在错误位置。

public class CircularQueue<E> {
    private final Object[] items;
    private int head;      // 队头元素下标
    private int tail;      // 队尾元素的下一个下标
    private int size;      // 当前元素个数(判空判满的唯一依据)

    public CircularQueue(int capacity) {
        this.items = new Object[Math.max(1, capacity)];
    }

    public boolean offer(E e) {
        if (size == items.length) {
            return false;                          // 判满:size 达到数组长度
        }
        items[tail] = e;
        tail = (tail + 1) % items.length;
        size++;
        return true;
    }

    @SuppressWarnings("unchecked")
    public E poll() {
        if (size == 0) {
            return null;                           // 判空:size 为 0
        }
        E e = (E) items[head];
        items[head] = null;                        // 置空,避免元素被长期持有
        head = (head + 1) % items.length;
        size--;
        return e;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == items.length;
    }
}

扩容处理:计数法下扩容的判据是 size == items.length。扩容时不能简单地把旧数组复制到新数组的开头,因为队列的逻辑顺序可能跨越了数组末尾。正确做法是按逻辑顺序逐个搬运:

private void grow() {
    Object[] bigger = new Object[items.length * 2];
    for (int i = 0; i < size; i++) {
        bigger[i] = items[(head + i) % items.length];   // 按逻辑顺序摆放
    }
    items = bigger;
    head = 0;
    tail = size;
}

出队时置空引用这一步容易被省略。数组中的槽位会长期持有出队元素的引用,若元素是大对象,会造成内存无法回收,表现为堆占用随出队次数不下降——这类泄漏只与数组长度同级(最多 capacity 个引用),但对大对象仍值得处理。

3.3 常用场景代码

3.3.1 表达式求值

完整实现分为两步:中缀转后缀与后缀求值。

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public final class ExpressionEvaluator {

    private static final Map<Character, Integer> PRECEDENCE =
            Map.of('+', 1, '-', 1, '*', 2, '/', 2);

    /** 中缀表达式转后缀表达式(调度场算法)。操作数与运算符之间以空格分隔。 */
    public static String toPostfix(String infix) {
        StringBuilder out = new StringBuilder();
        Deque<Character> ops = new ArrayDeque<>();
        for (int i = 0; i < infix.length(); i++) {
            char c = infix.charAt(i);
            if (Character.isWhitespace(c)) {
                continue;
            }
            if (Character.isDigit(c)) {
                while (i < infix.length() && Character.isDigit(infix.charAt(i))) {
                    out.append(infix.charAt(i++));         // 多位数字整体输出
                }
                out.append(' ');
                i--;
            } else if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (!ops.isEmpty() && ops.peek() != '(') {
                    out.append(ops.pop()).append(' ');
                }
                ops.pop();                                 // 丢弃左括号
            } else {                                       // 运算符 + - * /
                while (!ops.isEmpty() && ops.peek() != '('
                        && PRECEDENCE.get(ops.peek()) >= PRECEDENCE.get(c)) {
                    out.append(ops.pop()).append(' ');     // 优先级不低于当前运算符的先输出
                }
                ops.push(c);
            }
        }
        while (!ops.isEmpty()) {
            out.append(ops.pop()).append(' ');
        }
        return out.toString().trim();
    }

    /** 后缀表达式求值。操作数栈中每次弹出两个值,先弹出者为右操作数。 */
    public static long evaluatePostfix(String postfix) {
        Deque<Long> values = new ArrayDeque<>();
        for (String token : postfix.split("\\s+")) {
            switch (token) {
                case "+" -> values.push(values.pop() + values.pop());
                case "*" -> values.push(values.pop() * values.pop());
                case "-" -> {
                    long right = values.pop();
                    long left = values.pop();
                    values.push(left - right);             // 减法与除法不满足交换律,顺序不可颠倒
                }
                case "/" -> {
                    long right = values.pop();
                    long left = values.pop();
                    values.push(left / right);
                }
                default -> values.push(Long.parseLong(token));
            }
        }
        return values.pop();
    }
}

以 3 * (4 + 5) 为例:转后缀得到 3 4 5 + *;求值时 3、4、5 依次入栈,遇 + 弹出 5 与 4 计算得 9 入栈,遇 * 弹出 9 与 3 计算得 27。时间与空间复杂度均为 O(n),n 为表达式长度。

扩展方向:加入单目负号、幂运算(右结合,弹出条件需由 >= 改为 >)、浮点数与函数名(函数名按标识符解析、遇 ( 入栈)。这些扩展不改变整体框架,只改变运算符表的比较规则与词法切分方式。

3.3.2 滑动窗口最大值(单调队列)

public static int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0 || k <= 0) {
        return new int[0];
    }
    int[] result = new int[nums.length - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();       // 存下标,对应值自队首向队尾递减
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();                        // 队尾比新元素小的不可能再成为最大值
        }
        deque.offerLast(i);
        if (deque.peekFirst() <= i - k) {
            deque.pollFirst();                       // 队首已滑出窗口左边界
        }
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

复杂度:每个下标至多入队一次、出队一次,时间 O(n);队列长度不超过 k,空间 O(k)。相比之下,对每个窗口重新扫描的暴力解法是 O(nk),用优先队列维护窗口最大值的做法是 O(n log n)(并在元素滑出时产生延迟删除的额外判断)。若窗口长度不固定或需要任意区间的聚合,则超出单调队列的能力范围,应改用支持区间查询的结构,见 线段树与并查集 中区间问题的分类一节。

3.3.3 柱状图最大矩形(单调栈)

对每根柱子,以它的高度为高的最大矩形,宽度由左右两侧第一个高度更小的柱子决定。用一次从左到右的扫描维护递增栈,即可在弹出时同时确定左右边界:

public static int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Deque<Integer> stack = new ArrayDeque<>();       // 存下标,对应高度自栈底向栈顶严格递增
    int max = 0;
    for (int i = 0; i <= n; i++) {
        int current = (i == n) ? 0 : heights[i];     // 末尾追加高度 0 作为哨兵,强制清空栈
        while (!stack.isEmpty() && heights[stack.peek()] > current) {
            int height = heights[stack.pop()];
            int leftBoundary = stack.isEmpty() ? -1 : stack.peek();
            max = Math.max(max, height * (i - leftBoundary - 1));
        }
        stack.push(i);
    }
    return max;
}

边界推导:被弹出下标 p 的高度是 height,右边界是当前的 i(第一个高度更小的柱子),左边界是弹出后栈顶的下标(栈内元素高度递增,故栈顶是 p 左侧第一个高度更小的柱子),矩形宽度为 i - leftBoundary - 1。哨兵 0 的作用是让扫描结束时栈内所有元素都被弹出并完成计算,省去单独的收尾循环。

复杂度:时间 O(n)(每个下标入栈出栈各一次),空间 O(n)(栈最多保存 n 个下标)。

3.4 工程应用

3.4.1 函数调用与递归展开

函数调用本身即栈结构,其运行时层面的组织见 2.1.5 节。工程上的处理集中在两个方向:

控制递归深度。递归深度等于调用栈的帧数,受单线程栈容量约束。可行的做法包括:把递归改写为显式栈的迭代(栈空间从线程栈转移到堆,容量上限由 -Xss 变为 -Xmx,数量级显著提高);在递归入口检查当前深度并超限即返回错误;降低单帧大小(减少局部变量与参数);调整 -Xss(代价是每线程内存占用增加,高并发时可能引发无法创建线程)。

// 递归形式:深度等于树高,深树会耗尽线程栈
int sumRecursive(Node node) {
    if (node == null) {
        return 0;
    }
    return node.value + sumRecursive(node.left) + sumRecursive(node.right);
}

// 显式栈形式:栈空间由堆承担
int sumIterative(Node root) {
    if (root == null) {
        return 0;
    }
    int total = 0;
    Deque<Node> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        total += node.value;
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    return total;
}

跨帧保存状态。递归调用之间的局部状态只存在于栈帧中,因此"执行到一半后中断、稍后继续"这类需求必须把状态提取出来。常用手段是把节点与阶段号一起压入栈(例如"已展开子节点 / 未展开子节点"两态),在弹栈时根据阶段决定是继续展开还是执行后序处理;或者改用访问标记集合,记录已处理过的节点。

3.4.2 浏览器前进与后退

浏览历史用一个当前指针加两个栈(或一个双向列表加指针)表示:后退栈保存当前页之前的页面,前进栈保存当前页之后的页面。

  • 访问新页面:当前页压入后退栈、清空前进栈、新页成为当前页(历史分支被替换)
  • 后退:当前页压入前进栈,从后退栈弹出页面作为当前页
  • 前进:当前页压入后退栈,从前进栈弹出页面作为当前页

这一模型与编辑器的撤销重做完全同构,"执行新操作即清空被撤销的分支"是两者的共同语义,也是历史记录不能进行树状分支的原因。

3.4.3 解析与语法分析中的符号栈

编译与解析过程中,栈承担"暂存尚未确定归属的中间结果"的职责,几种典型用法:

场景 栈的作用 出栈时机
括号与标签匹配 保存未闭合的左括号或开标签 遇到对应的右括号或闭标签
表达式解析(调度场算法) 保存暂缓输出的运算符 遇到优先级不高于它的运算符,或右括号
算符优先分析 保存已归约的部分与待比较的运算符 归约条件满足时
语法树构建 保存尚未挂接完成的父节点 子树解析完成时
缩进敏感解析(Python、YAML) 保存当前的缩进层级 缩进回退到更浅层级时

这类场景的共同点是延迟决策:读到某个记号时无法立即确定它的归属,需要先记住它,等后续记号到达后再决定。栈的顺序正好对应"嵌套深度"——越晚打开的嵌套越早关闭。

3.4.4 任务队列与线程池的工作队列

线程池用一个队列把"任务提交"与"任务执行"解耦:提交方把任务放入队列,工作线程从队列取出执行。队列类型直接决定了线程池的行为。

队列类型 特性 影响
有界队列 容量固定,满时触发后续策略 提供背压,队列满后创建新线程或执行拒绝策略
无界队列 容量近似无上限 maximumPoolSize 实际上失效(队列几乎不会满),任务堆积只会体现在内存增长上
不存储队列 入队必须立即被取走,否则阻塞 任务多时不断创建线程,适合短任务

这一点是线程池配置中最常见的误用来源:使用无界队列时,核心线程数已足够处理的任务会全部进入队列,最大线程数与拒绝策略都不会生效,积压持续累积直到内存不足。各类工作队列的对比、拒绝策略的行为以及各工厂方法的风险见 Java 并发编程 中线程池一节。

需要区分的还有任务队列的两层语义:外层是线程池的工作队列(同进程、内存中、有界或阻塞),内层是业务上的待处理任务集合(通常持久化在数据库或消息队列中,带重试与状态)。仅依赖内存队列保存任务时,进程重启即丢失未处理任务。

3.4.5 流量整形中的队列

流量整形的目标是把不规则的请求速率转换为可接受的输出速率,队列在其中承担"暂存超额请求"的角色,常见两种形态:

  • 漏桶:以固定速率取出请求,超出桶容量的请求被拒绝或排队等待。输出速率恒定,不放大突发,代价是排队引入额外延迟。
  • 令牌桶:按固定速率向桶中补充令牌,请求取到令牌才被放行。允许在桶容量范围内突发,更贴近多数业务对"平均速率受限但允许短时峰值"的预期。

两种形态在实现上都依赖一个计数器与时间戳,分布在多实例部署时通常落在集中式存储上,例如 Redis 中的固定窗口计数、滑动窗口有序集合、Lua 脚本实现的令牌桶。相关实现细节、原子性保证与依赖不可用时的降级方向见 Redis 缓存实践 中限流的常见实现一节。

队列思路也可用于主机侧的缓冲观测:内核为每个网络接口维护发送与接收队列,队列长度持续增长通常对应"上层发送速率超过链路或对端接收能力",是网络类问题排查的常见切入点。

3.4.6 操作系统中的队列

队列是操作系统中最常见的组织方式,几处与本文主题直接对应:

  • 就绪队列。调度器从就绪队列中选出下一个占用 CPU 的进程或线程,队列的组织方式(单队列、每 CPU 队列、多级反馈队列)直接影响调度行为,见 Linux 进程管理 中进程状态与调度一节。
  • 进程间通信的消息队列。内核维护的结构化消息队列支持多生产者多消费者,可按类型或优先级存取,与用户态的消息队列在模型上同源,差别在于消息由内核持久到进程生命周期之外。
  • 内存回收中的链表。页回收使用活跃链表与不活跃链表组织页面,回收从链表尾部开始,并在页面被再次访问时向链表头部晋升,本质上是一条按访问时间排序的淘汰队列,见 Linux 内存管理 中回收机制一节。
  • 块设备的请求队列。输入输出调度器把块设备的读写请求排队并按策略排序合并,队列深度直接影响吞吐与延迟。

3.5 常见问题与排查

现象 可能原因 验证与处置
循环队列中未出队的元素被覆盖,数据丢失 判满条件与实际容量不一致(如数组长度为 n 仍用 size == n - 1 判满,或误用 head == tail 判满) 打印 head、tail、size 三者的变化序列;统一以 size == capacity 判满并按 capacity 申请数组(或明确改为牺牲一个槽位)
队列容量尚未用满却拒绝入队 "牺牲一个槽位"实现中对外声明的容量按数组长度计算,实际可用容量为长度减一 对外暴露的容量语义应与实现一致:数组长度取最大元素数加一,或改用计数法
栈弹出 null 后继续参与运算,出现空指针或结果错误 未区分"空栈"与"元素值恰好为 null" 空栈弹出抛出明确异常,或在结构上禁止存入 null(多数双端队列实现本身也不接受 null)
递归调用抛 StackOverflowError,异常栈中同一个方法反复出现 递归缺少终止条件、终止条件在边界数据下不成立,或递归深度与数据规模同阶(如链式结构的深度递归) 检查递归出口与边界输入;把递归改写为显式栈迭代;必要时调整 -Xss,但优先消灭深度随数据量线性增长的设计
线程池任务持续堆积、堆内存单调上涨 工作队列无界,生产速率长期高于消费速率 打印队列长度(如 ThreadPoolExecutor.getQueue().size())随时间的变化;改为有界队列并配置合理的拒绝策略,使压力以可观测的方式反馈到上游
阻塞队列使用后接口响应变慢、线程数上升 put 在队列满时阻塞,线程被长时间挂起;或阻塞操作占用了本应快速返回的线程 确认调用路径上是否误用了阻塞方法(需快速失败处应使用 offer 与 poll 的带超时形式);检查队列容量与消费速率是否匹配
并发场景下队列中的元素丢失或重复处理 使用了非线程安全的实现(如 ArrayDeque)跨线程共享;或复合操作(判空后再取)之间存在竞态 换用并发容器或阻塞队列;把"检查—操作"合并为单个原子操作,例如直接 poll 并判断返回值而非先 isEmpty
并发队列的 size() 与预期不符 部分并发队列的 size() 需要遍历(如链表实现),返回的是遍历过程中的近似值 不把 size() 用作控制条件(如"依次取 n 个"),改为按 poll 返回 null 判断结束;容量控制交由队列自身的边界约束
出队后的对象长期不被回收 数组实现的槽位未置空,仍持有已出队元素的引用 出队时显式赋 null;用堆转储确认大对象的引用链是否指向队列内部数组
优先队列的遍历顺序与出队顺序不一致 堆只保证堆顶为最值,不保证整体有序 需要有序序列时连续 poll;比较器中加入次序键以保证相等优先级的稳定性

排查这类问题时,一个通用手段是把结构的内部状态打出来:队列的 head、tail、size 与容量,栈的 top 与容量,线程池的队列长度与活跃线程数。栈与队列的缺陷大多集中在边界上(空与满),而边界错误在正常运行区间不表现症状,只有打印状态并构造边界用例才能稳定复现。

3.6 选型与检查清单

3.6.1 不同语言的内置实现

语言 栈语义 队列语义 优先队列 双端队列
Java Deque(push / pop / peek),实现用 ArrayDeque Queue(offer / poll / peek),实现用 ArrayDeque PriorityQueue(小顶堆,可传比较器) ArrayDeque(环形数组)、LinkedList
Python list(append / pop) collections.deque(append / popleft) heapq(函数式操作列表) collections.deque
C++ std::stack std::queue std::priority_queue(默认大顶堆) std::deque
Go 切片(append / 切片截断) 带缓冲通道(chan)或切片 container/heap(接口实现) 需自行实现或使用容器包列表

几点使用上的差异值得注意:

  • Java 的 Stack 是遗留类(继承自 Vector,方法级同步,全表锁),新代码应使用 ArrayDeque 表达栈语义。Java 中 Deque 同时覆盖栈与队列两种语义,是标准库中唯一的受限线性结构基础设施。
  • Java 的 ArrayDeque 不允许插入 null,因为 poll 与 peek 返回 null 用于表示空队列。需要表达"元素可能为空"时应改用其他容器或包装元素。
  • Python 的 list 用作栈时,append 与 pop 是均摊 O(1);但用作队列时 pop(0) 是 O(n)(需要搬移后续元素),队列场景应使用 collections.deque,其 popleft 是 O(1)。
  • heapq 只提供小顶堆操作,需要大顶堆时存入取负后的值,或存入 (priority, tie_breaker, item) 三元组以避免比较不可比较的元素。
  • Go 的通道自带阻塞与同步语义,有缓冲通道的容量即队列容量,无缓冲通道等价于容量为 0 的同步点。

各实现类的性能特征、扩容策略与内存占用对照见 Java 集合框架实现原理。

3.6.2 按需求维度的选择

选型时按以下顺序逐项确认,前一项的结论会约束后一项的可选项。

第一步:语义。需要后进先出、先进先出、按优先级出队,还是两端操作?优先队列与双端队列都不是普通队列的替代品,语义选错后其余维度无从修正。

第二步:是否需要并发。

并发需求 推荐实现 代价
单线程或已由外部加锁 非并发实现(ArrayDeque、PriorityQueue) 性能最优,无同步开销
多线程生产者消费者,需要阻塞 ArrayBlockingQueue(有界)、LinkedBlockingQueue(可选有界) 线程可能被挂起,需要设计超时与降级路径
多线程,不允许阻塞 ConcurrentLinkedQueue size() 非精确且成本高,无容量上限
多线程,需要延迟出队 DelayQueue 元素必须携带到期时间,队首元素过期前不可取出

第三步:是否需要容量上限。无界队列放弃背压,生产速率长期高于消费速率时表现为内存持续增长。只要消费能力存在不确定性,就应选择有界队列并明确队列满时的行为(阻塞、拒绝、降级)。

第四步:操作的最坏代价是否敏感。数组实现存在扩容时的单次 O(n),链表实现没有扩容但每元素开销更高。对延迟敏感且容量可预设的场景,可在创建时指定容量以避免扩容。

检查清单(用于代码评审与故障复盘):

  • 队列是否有明确的容量上限,以及队列满时的行为是否被显式实现
  • 阻塞调用是否设置了超时,超时后的降级路径是否明确
  • 出队后是否清理了容器对元素的引用(数组实现的队列)
  • 递归的深度是否与输入规模相关,最坏情况下的深度是否被评估过
  • 共享的结构是否使用了并发安全的实现,复合操作是否已合并为原子操作
  • 优先队列的比较器在优先级相等时是否稳定,是否会出现不可比较的元素
  • 循环队列的判空判满依据是否同源,容量语义是否与实现一致

四、总结

栈与队列是线性表在两个方向上的收窄:前者把操作固定在一端,得到后进先出;后者把操作分置两端,得到先进先出。收窄的收益是语义确定、实现简单与代价可预期,代价是必须为"顺序"这一额外要求付出结构上的代价。

原理层面可以归纳为几条主线:

  • 栈对应嵌套,队列对应先后。栈解决的是"最近的选择需要最先回退",因此适用于撤销、括号匹配、表达式求值、深度优先与回溯;队列解决的是"先到的先被处理",因此适用于排队、削峰、按层展开与广度优先。判断一个场景该用哪种结构,只需确认它是嵌套关系还是平铺的先后关系。
  • 限制操作位置带来的实现问题集中在边界。顺序栈的两种栈顶指针约定、栈满与栈空、循环队列的判空与判满,都是"如何用有限的状态唯一区分空与满"这一问题在不同结构上的表现。取模回绕使 head == tail 产生歧义,解法是牺牲一个槽位或引入计数,两者只是空间与字段数量的交换。
  • 递归与栈是同一件事的两种写法。函数调用在运行时压入栈帧,返回时弹出,因此递归的深度等于栈的深度。改写为迭代等价于把调用栈搬到堆上,代价是需要显式保存原本隐含在栈帧中的状态。
  • 栈与队列可以互相模拟,但代价不对称。两个栈实现队列只需一次整体搬运,单次操作均摊 O(1);两个队列实现栈必须反复搬移,单次最坏 O(n)。差异的来源是逆序操作对两种语义的适配程度不同。
  • 变体围绕"顺序依据"扩展。优先队列把出队顺序由入队时间改为优先级(依赖堆);单调队列在窗口滑动的前提下同时维护最值与过期(依赖双端队列);延迟队列把顺序改为到期时间(复用堆或时间轮)。这些变体都保留了队列的"出队"语义,只改变了决定顺序的依据。
  • 消息队列不是数据结构队列的放大版。前者是跨进程的独立服务,关注投递语义、持久化、位点与重放;后者是进程内的内存结构,关注边界条件、并发同步与内存占用。工程中两者常常串联使用,中间件负责跨进程传输,进程内仍以阻塞队列把消息分发给工作线程。

实现层面需要落到位的几点:

  • 顺序实现要先固定边界约定。栈顶指针指向栈顶元素还是下一个空位,循环队列用计数还是牺牲槽位,判空与判满的依据必须同源,否则缺陷只会在边界附近暴露。
  • 容量与背压是队列配置的核心。有界队列把压力转换为上游可观测的阻塞或拒绝,无界队列把压力转换为内存增长,后者的故障形式更难定位。
  • 并发场景不要给普通实现加锁了事。阻塞队列提供了等待条件的语义,并发队列提供了无锁的吞吐,两者的适用面不同;复合操作必须合并为原子操作,可见性与原子性是两个独立的问题。
  • 边界状态要可观测。栈的 top 与容量、队列的 head、tail、size、线程池的队列长度,都是排查边界类缺陷时最先需要的信息;构造空、满、回绕三种用例,比在正常区间反复测试更能发现问题。

栈与队列的价值不在于结构本身的复杂度,而在于它们把"顺序"这一约束用最少的字段固定下来。理解了顺序依据如何决定结构形态,优先队列、单调队列、延迟队列这些变体就都成了同一条思路在不同约束下的展开。