栈与队列

1. 概述与学习目标

1.1 什么是栈与队列

栈（Stack）与队列（Queue）是两种最基础的受限线性表。它们都是线性结构，但对插入与删除操作的位置施加了严格约束：

• 栈遵循 LIFO（Last In First Out，后进先出）原则，所有插入与删除仅在栈顶（top）一端进行；
• 队列遵循 FIFO（First In First Out，先进先出）原则，插入在队尾（rear）进行、删除在队首（front）进行。

栈（LIFO）             队列（FIFO）
push/pop               enqueue        dequeue
   ↓                      ↓              ↑
 ┌───┐                 ┌───┬───┬───┬───┐
 │ 5 │ ← top           │ 7 │ 1 │ 3 │ 5 │
 ├───┤                 └───┴───┴───┴───┘
 │ 3 │                  rear           front
 ├───┤
 │ 1 │
 ├───┤
 │ 7 │ ← bottom
 └───┘

一句话定义：栈 = LIFO 单端操作，队列 = FIFO 双端分工，双端队列 = 双端可操作；三者是受限线性表的代表，操作简单但应用极其广泛，从函数调用栈到操作系统调度都依赖它们。

1.2 学习目标

完成本文档学习后，你将能够：

1. 记忆栈的 LIFO 与队列的 FIFO 形式化定义，复述顺序栈/链式栈/循环队列/链式队列/双端队列在 push/pop/enqueue/dequeue 操作上的时间复杂度差异；
2. 理解 Bauer-Samelson 1955-1957 慕尼黑工大叠加原理与表达式求值、Dijkstra 1960 年代递归调用栈与 ALGOL 60 编译器、Dijkstra 1965 信号量与 P/V 操作、Hoare 1978 CSP 模型与 Go channel 的历史脉络，说明栈与队列为何在受限操作场景下不可替代；
3. 应用顺序栈、链式栈、循环队列、链式队列、双端队列、单调栈、单调队列编写可运行的 Python/C++/Java 代码，解决括号匹配、逆波兰表达式、滑动窗口最值、每日温度、柱状图最大矩形等问题；
4. 分析单调栈与单调队列的均摊时间复杂度 $O(n)$ 论证，证明”每个元素至多入栈出栈一次”的核心不变式；
5. 评估栈与队列相对于数组、链表、堆在”操作受限场景”下的优劣，识别函数调用栈、表达式求值、BFS、任务调度、消息队列、撤销重做中的选型动机；
6. 对比顺序栈、链式栈、循环队列、链式队列、双端队列、单调栈、单调队列在内存开销、缓存友好性、扩容代价、实现复杂度维度的差异；
7. 创造性设计基于栈与队列的开源项目解决方案，如浏览器前进后退、音乐播放器、文本编辑器撤销栈、消息中间件、任务调度器、限流器。

1.3 术语表

1.4 栈与队列 vs 其他线性结构

1.5 适用场景与不适用场景

跨模块引用：栈与队列的链式实现依赖 链表；堆作为优先级队列的底层结构参见 堆与优先队列；BFS 与 DFS 中队列/栈的应用参见 搜索算法；函数调用栈与递归的关系参见 递归与回溯；循环队列作为数组受限应用参见 数组与动态数组。

2. 历史动机与演进

2.1 前栈时代：表达式求值的困境

1950 年代初期，计算机刚刚走出实验室，程序员面对的第一个难题是算术表达式求值。人类习以为常的中缀表达式 3 + 4 * 2 / (1 - 5) ^ 2 对计算机而言并不直观：需要处理运算符优先级、括号嵌套、结合性等复杂规则。

早期的解决方法是两次扫描：第一次扫描构造语法树，第二次遍历语法树求值。但这种方法内存占用高、实现复杂，难以在仅有几 KB 内存的早期计算机上实现。

2.2 Bauer-Samelson 1955-1957：叠加原理与栈的诞生

1955 年，慕尼黑工业大学的 Friedrich L. Bauer 与 Klaus Samelson 在研究 ALGOL 编译器时，提出了叠加原理（Principle of Nesting）：

“延期最后的操作首先执行”（The last postponed operation is the first to be performed）。

这一原理表明：在扫描中缀表达式时，遇到运算符先不计算，而是将其”延期”压入一个数据结构；当遇到更高优先级的运算符或括号结束时，再从该数据结构中取出最近延期的运算符执行。这种”后延期者先执行”的语义天然对应 LIFO 结构。

1957 年，Bauer-Samelson 在 ALGOL 58 编译器中首次实现了栈数据结构（最初称为 Keller，德语”地窖”），用于表达式求值与子程序调用。1960 年，他们在 Communications of the ACM 3(2): 76-83 发表论文《Sequential formula translation》，系统化了栈的概念与运算。Bauer 因此获 2002 年 IEEE Computer Society Pioneer Award。

教学提示：Bauer-Samelson 的”叠加原理”是栈语义的最早形式化表述，比 Dijkstra 1960 年代的递归调用栈更早。德语 Keller（地窖）一词形象地描述了栈的物理意象：从地窖中取物，最后放入的最先被取出。

2.3 Dijkstra 1960 年代：递归调用栈与 ALGOL 60

1960 年，Edsger W. Dijkstra 在荷兰阿姆斯特丹数学中心参与 ALGOL 60 编译器开发时，独立发现了栈在递归子程序调用中的关键作用：

• 每次函数调用时，将返回地址、局部变量、参数压入栈；
• 函数返回时，从栈中弹出这些信息，恢复调用者上下文；
• 递归调用天然形成栈式嵌套，最深层的递归最先返回。

Dijkstra 在 1960 年代的一系列技术报告（EWD 系列）中系统化讨论了”递归调用栈”的实现，使栈成为所有高级编程语言运行时的核心组件。这一贡献使 ALGOL 60 成为首个支持递归过程的语言，奠定了现代编程语言的基础。

常见误区：有传言说 Dijkstra 发明了栈。实际上 Bauer-Samelson 1955 年的工作更早，Dijkstra 是将栈应用于递归调用栈与并发同步的开拓者。

2.4 Dijkstra 1965：信号量与等待队列

1965 年，Dijkstra 在 Technological University Eindhoven 的技术报告 EWD-123《Cooperating sequential processes》中提出信号量（Semaphore）同步原语：

• 信号量 S 是一个整型变量，关联一个等待队列 $Q$；
• P 操作（proberen，测试）：若 $S > 0$，则 $S \leftarrow S - 1$；否则将当前进程加入 $Q$ 阻塞；
• V 操作（verhogen，增加）：若 $Q$ 非空，唤醒 $Q$ 队首进程；否则 $S \leftarrow S + 1$。

信号量的等待队列是队列在操作系统内核中的核心应用，奠定了进程同步与互斥的理论基础。该文 1968 年收入 Genys 编辑的《The Origin of Concurrent Programming》一书，成为并发编程的奠基文献。Dijkstra 因此获 1972 年 ACM Turing Award。

2.5 Knuth 1968：栈与队列的系统化理论

1968 年，Donald E. Knuth 出版《The Art of Computer Programming, Volume 1: Fundamental Algorithms》，在 Section 2.2.1 Stacks, Queues and Deques 系统化栈与队列理论：

• 形式化定义栈（LIFO）、队列（FIFO）、双端队列（deque）；
• 分析顺序存储与链式存储两种实现；
• 提出循环队列的取模索引技巧；
• 讨论栈与队列在表达式求值、模拟、调度中的应用。

TAOCP Vol.1 成为栈与队列教学的金标准，后续教材（CLRS、Sedgewick）均沿用其框架。Knuth 指出：“栈与队列是受限线性表的最简形式，它们的简洁性恰是其力量所在”。

2.6 Hoare 1978：CSP 模型与通道队列

1978 年，牛津大学 C. A. R. Hoare 在 Communications of the ACM 21(8): 666-677 发表论文《Communicating sequential processes》，提出 CSP（Communicating Sequential Processes）模型：

• 进程间通过通道（channel）通信，通道本质上是一个 FIFO 队列；
• 发送方 channel ! message 将消息加入通道；
• 接收方 channel ? message 从通道队首取出消息；
• 若通道为空，接收方阻塞；若通道满，发送方阻塞。

CSP 模型深刻影响了后续并发编程语言设计：

• Occam（1983）：第一个基于 CSP 的语言，用于 Transputer 处理器；
• Erlang（1986）：基于 Actor 模型，但通道思想与 CSP 类似；
• Go（2009）：channel 是 Go 的一等公民，“Don’t communicate by sharing memory; share memory by communicating” 是 Go 并发的核心理念；
• Rust（2010）：通过 std::sync::mpsc 提供 CSP 风格通道。

Hoare 因此获 1980 年 ACM Turing Award。CSP 模型使队列从”操作系统内部数据结构”上升为”编程语言一等公民”。

2.7 Linux kernel 1991：等待队列与工作队列

1991 年 Linus Torvalds 创建 Linux kernel，其中大量使用队列：

• 等待队列（wait_queue）：进程阻塞时挂入等待队列，事件触发时唤醒队首进程；
• 工作队列（workqueue）：内核延迟执行工作的机制，底层是 per-CPU 队列；
• 就绪队列（runqueue）：调度器维护的可运行进程队列，CFS 调度器使用红黑树而非队列；
• 网络协议栈：sk_buff 队列管理网络数据包，如 netif_queue、qdisc 队列；
• 块设备 I/O：请求队列 request_queue 管理块设备的 I/O 请求。

Linux kernel 是队列在工业级系统中的集大成应用，其 list_head 侵入式链表既是队列的底层实现，也是栈的底层实现。

2.8 Go 2012：channel 的工业化实现

2012 年 Go 1.0 发布，channel 作为语言一等公民广泛流行。Go channel 的底层实现 runtime.hchan 结构包含：

• 环形缓冲区（circular buffer）：有缓冲 channel 的底层是循环队列；
• 等待队列：发送方与接收方分别维护 goroutine 等待队列；
• 互斥锁：保护缓冲区与等待队列的并发访问。

Go channel 是 CSP 模型与现代工业级语言结合的典范，使”队列作为通信原语”成为主流并发编程范式。

2.9 演进时间线

timeline
    title 栈与队列演进时间线
    1955 : Bauer-Samelson 慕尼黑工大叠加原理 (栈概念诞生)
    1957 : Bauer-Samelson ALGOL 58 编译器首次实现栈
    1960 : Bauer-Samelson 论文 Sequential formula translation (CACM)
    1960 : Dijkstra ALGOL 60 编译器递归调用栈
    1965 : Dijkstra 信号量与等待队列 (EWD-123)
    1968 : Knuth TAOCP Vol.1 §2.2.1 系统化理论
    1973 : Brinch Hansen 管程 (Monitors) with condition queues
    1978 : Hoare CSP 模型与通道队列 (CACM)
    1983 : Occam 语言 (基于 CSP, Transputer)
    1986 : Erlang 语言 (Actor 模型, mailbox 队列)
    1991 : Linux kernel 大量使用队列 (wait_queue/workqueue)
    1995 : Java 1.0 Stack/Vector (后推荐 Deque)
    2009 : Go 语言 channel (CSP 工业化)
    2014 : Java 8 CompletableFuture (基于 ForkJoinPool 队列)
    2024 : Go 1.22 channel 性能优化 (无锁环形队列)

2.10 关键设计决策

栈与队列演进过程中有七个关键设计决策：

1. LIFO vs FIFO 语义分离：栈与队列的本质区别是操作位置约束，分离两者使 API 更清晰；
2. 顺序存储优先：连续内存布局缓存友好，扩容代价摊还 $O(1)$，是栈与队列的默认实现；
3. 循环队列解决假溢出：取模运算将顺序队列首尾相连，空间利用率达 100%；
4. 双端队列泛化栈与队列：deque 同时支持 LIFO 与 FIFO，是两者的超集；
5. 单调性约束换性能：单调栈/单调队列通过单调性约束，将”下一个更大元素”等问题的 $O(n^2)$ 优化至 $O(n)$；
6. 队列作为同步原语：信号量、管程、channel 的等待队列是并发编程的核心；
7. 混合结构平衡时空：Go channel 的环形缓冲区 + 等待队列是工业级混合结构典范。

3. 形式化定义

3.1 栈的形式化定义

栈是受限线性表，其插入与删除操作仅在表的一端（栈顶）进行。形式化定义：

$\text{Stack} = \langle S, \text{top}, \text{push}, \text{pop}, \text{peek}, \text{isEmpty} \rangle$

其中：

• $S$ 是元素集合，$S = \{s_1, s_2, \ldots, s_n\}$，$n \geq 0$ 为栈长度；
• $\text{top} \in \{0, 1, \ldots, n\}$ 为栈顶指针，$n = 0$ 时空栈；
• $\text{push}(x)$：$S \leftarrow S \cup \{x\}$，$\text{top} \leftarrow \text{top} + 1$，$s_{\text{top}} \leftarrow x$；
• $\text{pop}()$：若 $\text{top} = 0$ 报错；否则 $x \leftarrow s_{\text{top}}$，$S \leftarrow S \setminus \{s_{\text{top}}\}$，$\text{top} \leftarrow \text{top} - 1$，返回 $x$；
• $\text{peek}()$：返回 $s_{\text{top}}$ 不修改栈；
• $\text{isEmpty}()$：返回 $\text{top} = 0$。

LIFO 性质：若元素 $a$ 比 $b$ 晚入栈，则 $a$ 必先于 $b$ 出栈。形式化：

$\forall a, b \in S: \text{pushTime}(a) > \text{pushTime}(b) \Rightarrow \text{popTime}(a) < \text{popTime}(b)$

3.2 队列的形式化定义

队列是受限线性表，其插入在队尾、删除在队首。形式化定义：

$\text{Queue} = \langle Q, \text{front}, \text{rear}, \text{enqueue}, \text{dequeue}, \text{front}, \text{isEmpty} \rangle$

其中：

• $Q$ 是元素集合，$Q = \{q_1, q_2, \ldots, q_n\}$，$q_1$ 为队首、$q_n$ 为队尾；
• $\text{enqueue}(x)$：$Q \leftarrow Q \cup \{x\}$，$q_{n+1} \leftarrow x$；
• $\text{dequeue}()$：若 $Q = \emptyset$ 报错；否则 $x \leftarrow q_1$，$Q \leftarrow Q \setminus \{q_1\}$，返回 $x$；
• $\text{front}()$：返回 $q_1$ 不修改队列；
• $\text{isEmpty}()$：返回 $|Q| = 0$。

FIFO 性质：若元素 $a$ 比 $b$ 早入队，则 $a$ 必先于 $b$ 出队。形式化：

$\forall a, b \in Q: \text{enqueueTime}(a) < \text{enqueueTime}(b) \Rightarrow \text{dequeueTime}(a) < \text{dequeueTime}(b)$

3.3 ADT 定义

ADT Stack {
    数据对象：D = {a_i | a_i ∈ ElemSet, i = 1, 2, ..., n, n ≥ 0}
    数据关系：R = {<a_{i-1}, a_i> | a_{i-1}, a_i ∈ D, i = 2, ..., n}
              约定 a_n 为栈顶，a_1 为栈底
    基本操作：
        InitStack(&S)        : 构造空栈
        DestroyStack(&S)     : 销毁栈
        ClearStack(&S)       : 清空栈
        StackEmpty(S)        : 判空
        StackLength(S)       : 求长度
        GetTop(S, &e)        : 取栈顶元素
        Push(&S, e)          : 入栈
        Pop(&S, &e)          : 出栈
        TraverseStack(S)     : 遍历（非标准，仅调试用）
}

ADT Queue {
    数据对象：D = {a_i | a_i ∈ ElemSet, i = 1, 2, ..., n, n ≥ 0}
    数据关系：R = {<a_{i-1}, a_i> | a_{i-1}, a_i ∈ D, i = 2, ..., n}
              约定 a_1 为队首，a_n 为队尾
    基本操作：
        InitQueue(&Q)        : 构造空队列
        DestroyQueue(&Q)     : 销毁队列
        ClearQueue(&Q)       : 清空队列
        QueueEmpty(Q)        : 判空
        QueueLength(Q)       : 求长度
        GetHead(Q, &e)       : 取队首元素
        EnQueue(&Q, e)       : 入队
        DeQueue(&Q, &e)      : 出队
        TraverseQueue(Q)     : 遍历
}

3.4 复杂度分析

摊还分析：顺序栈/循环队列的 push 操作在容量充足时为 $O(1)$，触发扩容时为 $O(n)$。采用倍增扩容策略后，$n$ 次 push 的总代价为 $O(n)$，摊还每次 $O(1)$。这是聚合分析的经典案例（CLRS §17）。

4. 栈的实现

4.1 顺序栈（基于数组）

顺序栈使用数组存储元素，栈顶指针 top 指向下一个待插入位置。容量不足时倍增扩容。

# Python：顺序栈（基于动态数组）
from typing import Generic, TypeVar, List, Optional

T = TypeVar('T')

class ArrayStack(Generic[T]):
    """顺序栈：基于动态数组实现，支持倍增扩容"""

    __slots__ = ('_data', '_top', '_capacity')

    def __init__(self, initial_capacity: int = 16) -> None:
        """初始化栈，默认容量 16"""
        assert initial_capacity > 0
        self._data: List[Optional[T]] = [None] * initial_capacity
        self._top: int = 0  # 栈顶指针，指向下一个待插入位置
        self._capacity: int = initial_capacity

    def push(self, item: T) -> None:
        """入栈：将 item 压入栈顶。摊还 O(1)"""
        if self._top == self._capacity:
            self._resize(self._capacity * 2)  # 倍增扩容
        self._data[self._top] = item
        self._top += 1

    def pop(self) -> T:
        """出栈：弹出并返回栈顶元素。O(1)"""
        if self.is_empty():
            raise IndexError('pop from empty stack')
        self._top -= 1
        item: T = self._data[self._top]  # type: ignore
        self._data[self._top] = None  # 帮助 GC
        # 缩容：当使用率低于 1/4 时减半容量
        if 0 < self._top < self._capacity // 4:
            self._resize(self._capacity // 2)
        return item

    def peek(self) -> T:
        """查看栈顶元素（不出栈）。O(1)"""
        if self.is_empty():
            raise IndexError('peek from empty stack')
        return self._data[self._top - 1]  # type: ignore

    def is_empty(self) -> bool:
        return self._top == 0

    def size(self) -> int:
        return self._top

    def _resize(self, new_capacity: int) -> None:
        """扩容/缩容：复制到新数组"""
        new_data: List[Optional[T]] = [None] * new_capacity
        for i in range(self._top):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity

// C++：顺序栈（基于 vector 模板）
#include <vector>
#include <stdexcept>
#include <optional>

template <typename T>
class ArrayStack {
private:
    std::vector<T> data;  // 底层使用 vector 自动扩容

public:
    // 入栈：摊还 O(1)
    void push(const T& item) {
        data.push_back(item);
    }

    // 出栈：O(1)
    T pop() {
        if (empty()) throw std::out_of_range("pop from empty stack");
        T item = std::move(data.back());
        data.pop_back();
        return item;
    }

    // 查看栈顶
    std::optional<T> peek() const {
        if (empty()) return std::nullopt;
        return data.back();
    }

    bool empty() const noexcept { return data.empty(); }
    size_t size() const noexcept { return data.size(); }
};

// Java：顺序栈（基于 Object[]，手动扩容）
import java.util.Arrays;

public class ArrayStack<E> {
    private Object[] data;
    private int top;        // 栈顶指针，指向下一个待插入位置
    private int capacity;

    public ArrayStack(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.data = new Object[capacity];
        this.top = 0;
        this.capacity = capacity;
    }

    public ArrayStack() {
        this(16);
    }

    /** 入栈：摊还 O(1) */
    public void push(E element) {
        if (top == capacity) resize(capacity * 2);
        data[top++] = element;
    }

    @SuppressWarnings("unchecked")
    public E pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        E element = (E) data[--top];
        data[top] = null;  // 帮助 GC
        // 缩容：使用率低于 1/4 时减半
        if (top > 0 && top < capacity / 4) resize(capacity / 2);
        return element;
    }

    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return (E) data[top - 1];
    }

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

    private void resize(int newCapacity) {
        data = Arrays.copyOf(data, newCapacity);
        capacity = newCapacity;
    }
}

4.2 链式栈（基于链表）

链式栈使用单链表实现，栈顶为链表头节点。入栈即头插、出栈即头删，均为 $O(1)$，无需扩容。

# Python：链式栈（基于单链表）
from typing import Generic, TypeVar, Optional

T = TypeVar('T')

class LinkedStack(Generic[T]):
    """链式栈：基于单链表实现，栈顶为头节点"""

    class _Node:
        __slots__ = ('value', 'next')
        def __init__(self, value: T, next: Optional['LinkedStack._Node']) -> None:
            self.value = value
            self.next = next

    def __init__(self) -> None:
        self._top: Optional[LinkedStack._Node] = None  # type: ignore
        self._size: int = 0

    def push(self, item: T) -> None:
        """入栈：头插法 O(1)"""
        self._top = self._Node(item, self._top)
        self._size += 1

    def pop(self) -> T:
        """出栈：头删法 O(1)"""
        if self.is_empty():
            raise IndexError('pop from empty stack')
        node = self._top
        self._top = node.next
        self._size -= 1
        return node.value

    def peek(self) -> T:
        if self.is_empty():
            raise IndexError('peek from empty stack')
        return self._top.value  # type: ignore

    def is_empty(self) -> bool:
        return self._top is None

    def size(self) -> int:
        return self._size

// C++：链式栈（基于 forward_list 风格）
#include <memory>
#include <stdexcept>
#include <optional>

template <typename T>
class LinkedStack {
private:
    struct Node {
        T value;
        std::unique_ptr<Node> next;
        Node(T v, std::unique_ptr<Node> n) : value(std::move(v)), next(std::move(n)) {}
    };
    std::unique_ptr<Node> top_node;
    size_t sz = 0;

public:
    void push(const T& item) {
        top_node = std::make_unique<Node>(item, std::move(top_node));
        ++sz;
    }

    T pop() {
        if (empty()) throw std::out_of_range("pop from empty stack");
        T item = std::move(top_node->value);
        top_node = std::move(top_node->next);
        --sz;
        return item;
    }

    std::optional<T> peek() const {
        if (empty()) return std::nullopt;
        return top_node->value;
    }

    bool empty() const noexcept { return sz == 0; }
    size_t size() const noexcept { return sz; }
};

// Java：链式栈
public class LinkedStack<E> {
    private static class Node<E> {
        E value;
        Node<E> next;
        Node(E value, Node<E> next) { this.value = value; this.next = next; }
    }

    private Node<E> top;
    private int size;

    public void push(E element) {
        top = new Node<>(element, top);
        size++;
    }

    public E pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        E element = top.value;
        top = top.next;
        size--;
        return element;
    }

    public E peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return top.value;
    }

    public boolean isEmpty() { return top == null; }
    public int size() { return size; }
}

4.3 两种实现对比

教学提示：实际工程中，顺序栈因缓存友好性通常是首选。Python 的 list、C++ 的 std::vector<T>、Java 的 ArrayList<E> 都可用作顺序栈的底层。链式栈的优势在于无需预分配、避免扩容时的拷贝，适合大规模或不可拷贝对象。

5. 栈的经典应用

5.1 括号匹配

判断由 (、)、[、]、{、} 组成的字符串是否合法：每个左括号必须以相同类型的右括号闭合，且顺序正确。

算法：扫描字符串，遇左括号入栈，遇右括号检查栈顶是否匹配。

# Python：括号匹配（LeetCode 20）
def is_valid_parentheses(s: str) -> bool:
    """括号匹配。O(n) 时间，O(n) 空间"""
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs.values():  # 左括号入栈
            stack.append(ch)
        elif ch in pairs:         # 右括号匹配
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack  # 栈空则全部匹配

// Java：括号匹配
import java.util.*;

public boolean isValid(String s) {
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (pairs.containsValue(c)) {
            stack.push(c);
        } else if (pairs.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
        }
    }
    return stack.isEmpty();
}

5.2 逆波兰表达式求值

逆波兰表达式（后缀表达式）天然适合栈求值：遇操作数入栈，遇运算符弹出两个操作数计算后入栈。

# Python：逆波兰表达式求值（LeetCode 150）
def eval_rpn(tokens: list[str]) -> int:
    """逆波兰表达式求值。O(n) 时间，O(n) 空间"""
    stack: list[int] = []
    for token in tokens:
        if token in '+-*/':
            b = stack.pop()
            a = stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            elif token == '/': stack.append(int(a / b))  # 截断向零
        else:
            stack.append(int(token))
    return stack[0]

5.3 中缀表达式转后缀表达式（调度场算法）

Dijkstra 1961 年提出的调度场算法（Shunting Yard Algorithm）将中缀表达式转换为后缀表达式，是栈的经典应用。

# Python：调度场算法
def infix_to_postfix(expr: str) -> str:
    """中缀转后缀（调度场算法）。仅支持 + - * / 和括号"""
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    output: list[str] = []
    stack: list[str] = []

    i = 0
    while i < len(expr):
        c = expr[i]
        if c.isdigit():
            # 解析多位数
            j = i
            while j < len(expr) and expr[j].isdigit():
                j += 1
            output.append(expr[i:j])
            i = j
            continue
        elif c == '(':
            stack.append(c)
        elif c == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # 弹出 '('
        elif c in precedence:
            while (stack and stack[-1] != '('
                   and precedence.get(stack[-1], 0) >= precedence[c]):
                output.append(stack.pop())
            stack.append(c)
        i += 1

    while stack:
        output.append(stack.pop())

    return ' '.join(output)

# 示例：'3 + 4 * 2 / (1 - 5)' → '3 4 2 * 1 5 - / +'

5.4 单调栈：寻找下一个更大元素

单调栈（Monotonic Stack）是栈的高级变体，要求栈内元素始终保持单调性（递增或递减）。核心思想：当新元素破坏单调性时，反复弹出栈顶直到恢复单调，弹出时即得到该元素的”下一个更大元素”。

经典问题：给定数组 nums，对每个元素找到右侧第一个比它大的元素的距离（LeetCode 739 每日温度）。

# Python：每日温度（LeetCode 739）
def daily_temperatures(temperatures: list[int]) -> list[int]:
    """单调递减栈：存索引。O(n) 时间（每个元素至多入栈出栈各一次）"""
    n = len(temperatures)
    answer = [0] * n
    stack: list[int] = []  # 存索引，对应温度单调递减

    for i in range(n):
        # 当前温度大于栈顶温度时，栈顶元素的"下一个更高温度"就是当前
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev = stack.pop()
            answer[prev] = i - prev
        stack.append(i)
    # 栈中剩余元素没有更高温度，answer 已初始化为 0
    return answer

// Java：每日温度（单调栈）
public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();  // 存索引，单调递减栈
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            answer[prev] = i - prev;
        }
        stack.push(i);
    }
    return answer;
}

复杂度分析：每个元素至多入栈一次、出栈一次，总操作数 $\leq 2n$，故时间复杂度 $O(n)$，空间复杂度 $O(n)$。

5.5 单调栈：柱状图中最大矩形

给定 $n$ 个非负整数表示柱状图中各柱子的高度，求最大矩形面积（LeetCode 84）。

算法：单调递增栈，弹出栈顶时计算以栈顶为最小高度的矩形面积。

# Python：柱状图中最大矩形（LeetCode 84）
def largest_rectangle_area(heights: list[int]) -> int:
    """单调递增栈 + 哨兵。O(n) 时间"""
    stack: list[int] = []  # 存索引，对应高度单调递增
    max_area = 0
    # 末尾加 0 哨兵，确保最后所有元素被弹出
    for i, h in enumerate(heights + [0]):
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            # 弹出后栈空则左边界为 -1，否则为栈顶索引
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

复杂度分析：每个元素至多入栈出栈各一次，哨兵保证栈被清空，总时间 $O(n)$。

6. 队列的实现

6.1 顺序队列的假溢出问题

普通顺序队列使用数组 + 两个指针 front 和 rear：

• 入队：data[rear++] = item
• 出队：item = data[front++]

问题：出队后 front 前方空间无法复用，rear 到达数组末尾时即使前方有空位也无法入队，称为假溢出（false overflow）。

入队 7, 1, 3, 5 后出队 7, 1：
  ┌───┬───┬───┬───┬───┬───┐
  │   │   │ 3 │ 5 │   │   │
  └───┴───┴───┴───┴───┴───┘
              ↑       ↑
            front   rear

继续入队 9, 8：
  ┌───┬───┬───┬───┬───┬───┐
  │   │   │ 3 │ 5 │ 9 │ 8 │
  └───┴───┴───┴───┴───┴───┘
              ↑               ← rear 越界！前方空间无法使用
            front

6.2 循环队列（解决假溢出）

循环队列（Circular Queue）通过取模运算将数组首尾相连：rear = (rear + 1) % capacity，front = (front + 1) % capacity，使出队后空间可复用。

# Python：循环队列（LeetCode 622）
class CircularQueue:
    """循环队列：基于定长数组 + 取模索引"""

    def __init__(self, k: int) -> None:
        self._data: list[int] = [0] * k
        self._front: int = 0
        self._rear: int = 0
        self._size: int = 0
        self._capacity: int = k

    def enqueue(self, value: int) -> bool:
        """入队。O(1)"""
        if self.is_full():
            return False
        self._data[self._rear] = value
        self._rear = (self._rear + 1) % self._capacity
        self._size += 1
        return True

    def dequeue(self) -> bool:
        """出队。O(1)"""
        if self.is_empty():
            return False
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return True

    def front(self) -> int:
        """查看队首。O(1)"""
        return -1 if self.is_empty() else self._data[self._front]

    def rear(self) -> int:
        """查看队尾。O(1)"""
        if self.is_empty():
            return -1
        # rear 指向下一个待插入位置，故队尾在 rear-1（取模）
        return self._data[(self._rear - 1) % self._capacity]

    def is_empty(self) -> bool:
        return self._size == 0

    def is_full(self) -> bool:
        return self._size == self._capacity

// C++：循环队列
#include <vector>
#include <stdexcept>

template <typename T>
class CircularQueue {
private:
    std::vector<T> data;
    int front_idx = 0;
    int rear_idx = 0;
    int sz = 0;
    int cap;

public:
    explicit CircularQueue(int k) : data(k), cap(k) {}

    bool enqueue(const T& value) {
        if (full()) return false;
        data[rear_idx] = value;
        rear_idx = (rear_idx + 1) % cap;
        ++sz;
        return true;
    }

    bool dequeue() {
        if (empty()) return false;
        front_idx = (front_idx + 1) % cap;
        --sz;
        return true;
    }

    T front() const {
        if (empty()) throw std::runtime_error("Queue is empty");
        return data[front_idx];
    }

    T rear() const {
        if (empty()) throw std::runtime_error("Queue is empty");
        return data[(rear_idx - 1 + cap) % cap];
    }

    bool empty() const noexcept { return sz == 0; }
    bool full() const noexcept { return sz == cap; }
    int size() const noexcept { return sz; }
};

// Java：循环队列
public class CircularQueue<E> {
    private Object[] data;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public CircularQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.data = new Object[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
        this.capacity = capacity;
    }

    public boolean enqueue(E element) {
        if (isFull()) return false;
        data[rear] = element;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    @SuppressWarnings("unchecked")
    public E dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        E element = (E) data[front];
        data[front] = null;
        front = (front + 1) % capacity;
        size--;
        return element;
    }

    @SuppressWarnings("unchecked")
    public E front() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        return (E) data[front];
    }

    @SuppressWarnings("unchecked")
    public E rear() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        return (E) data[(rear - 1 + capacity) % capacity];
    }

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

关键细节：循环队列的”判空 vs 判满”有三种常见方案：

1. 维护 size 变量（推荐）：size == 0 判空、size == capacity 判满，直观无歧义；
2. 浪费一个槽位：rear == front 判空、(rear + 1) % capacity == front 判满，容量少 1；
3. 标志位：额外维护 tag 表示最近操作是入队还是出队，结合 front == rear 判断。

6.3 链式队列（基于链表）

链式队列使用单链表 + 头尾指针，入队即尾插、出队即头删，均 $O(1)$。

# Python：链式队列
from typing import Generic, TypeVar, Optional

T = TypeVar('T')

class LinkedQueue(Generic[T]):
    """链式队列：单链表 + 头尾指针"""

    class _Node:
        __slots__ = ('value', 'next')
        def __init__(self, value: T, next: Optional['LinkedQueue._Node']) -> None:
            self.value = value
            self.next = next

    def __init__(self) -> None:
        # 哨兵头节点，简化空队处理
        self._sentinel: LinkedQueue._Node = self._Node(None, None)  # type: ignore
        self._rear: LinkedQueue._Node = self._sentinel  # type: ignore
        self._size: int = 0

    def enqueue(self, item: T) -> None:
        """入队：尾插法 O(1)"""
        new_node = self._Node(item, None)
        self._rear.next = new_node
        self._rear = new_node
        self._size += 1

    def dequeue(self) -> T:
        """出队：头删法 O(1)"""
        if self.is_empty():
            raise IndexError('dequeue from empty queue')
        first = self._sentinel.next  # type: ignore
        self._sentinel.next = first.next
        if self._rear is first:
            self._rear = self._sentinel  # 队列变为空
        self._size -= 1
        return first.value

    def front(self) -> T:
        if self.is_empty():
            raise IndexError('front of empty queue')
        return self._sentinel.next.value  # type: ignore

    def is_empty(self) -> bool:
        return self._size == 0

    def size(self) -> int:
        return self._size

// Java：链式队列
public class LinkedQueue<E> {
    private static class Node<E> {
        E value;
        Node<E> next;
        Node(E value) { this.value = value; }
    }

    private Node<E> front;  // 队首
    private Node<E> rear;   // 队尾
    private int size;

    public void enqueue(E element) {
        Node<E> node = new Node<>(element);
        if (isEmpty()) {
            front = rear = node;
        } else {
            rear.next = node;
            rear = node;
        }
        size++;
    }

    public E dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        E element = front.value;
        front = front.next;
        if (front == null) rear = null;  // 队列变为空
        size--;
        return element;
    }

    public E front() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        return front.value;
    }

    public boolean isEmpty() { return front == null; }
    public int size() { return size; }
}

6.4 两种实现对比

7. 双端队列（Deque）

7.1 双端队列概念

双端队列（Double-Ended Queue，Deque）允许在两端进行插入与删除，是栈与队列的泛化：

• 作为栈使用：push = addFirst、pop = removeFirst
• 作为队列使用：enqueue = addLast、dequeue = removeFirst

左端操作: addFirst / removeFirst / getFirst
右端操作: addLast  / removeLast  / getLast

  ┌───┬───┬───┬───┬───┐
  │ 5 │ 3 │ 1 │ 7 │ 9 │
  └───┴───┴───┴───┴───┘
  ←left              right→

7.2 双端队列的实现

双端队列通常用环形缓冲区（circular buffer）实现，两端索引在数组中循环移动：

# Python：基于环形缓冲区的双端队列
from typing import Generic, TypeVar, Optional, List

T = TypeVar('T')

class ArrayDeque(Generic[T]):
    """双端队列：环形缓冲区 + 倍增扩容"""

    def __init__(self, initial_capacity: int = 16) -> None:
        self._data: List[Optional[T]] = [None] * initial_capacity
        self._head: int = 0  # 指向首元素
        self._tail: int = 0  # 指向下一个待插入位置
        self._size: int = 0
        self._capacity: int = initial_capacity

    def add_first(self, item: T) -> None:
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        self._head = (self._head - 1) % self._capacity
        self._data[self._head] = item
        self._size += 1

    def add_last(self, item: T) -> None:
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        self._data[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1

    def remove_first(self) -> T:
        if self.is_empty():
            raise IndexError('remove_first from empty deque')
        item: T = self._data[self._head]  # type: ignore
        self._data[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return item

    def remove_last(self) -> T:
        if self.is_empty():
            raise IndexError('remove_last from empty deque')
        self._tail = (self._tail - 1) % self._capacity
        item: T = self._data[self._tail]  # type: ignore
        self._data[self._tail] = None
        self._size -= 1
        return item

    def is_empty(self) -> bool:
        return self._size == 0

    def size(self) -> int:
        return self._size

    def _resize(self, new_capacity: int) -> None:
        new_data: List[Optional[T]] = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[(self._head + i) % self._capacity]
        self._data = new_data
        self._head = 0
        self._tail = self._size
        self._capacity = new_capacity

7.3 各语言内置 Deque 使用

# Python：collections.deque（C 实现，O(1) 两端操作）
from collections import deque

dq = deque()
dq.appendleft(1)   # 左端入队 O(1)
dq.append(2)       # 右端入队 O(1)
dq.popleft()       # 左端出队 → 1
dq.pop()           # 右端出队 → 2

# Python list 作为栈（push=append, pop=pop）
stack = [1, 2, 3]
stack.append(4)  # push
stack.pop()      # pop → 4

// C++ STL：std::deque / std::stack / std::queue
#include <deque>
#include <stack>
#include <queue>

// 双端队列
std::deque<int> dq;
dq.push_back(1);     // 尾插
dq.push_front(2);    // 头插
dq.pop_back();       // 尾删
dq.pop_front();      // 头删

// 栈（默认基于 deque）
std::stack<int> s;
s.push(1);
s.top();    // 访问栈顶
s.pop();

// 队列（默认基于 deque）
std::queue<int> q;
q.push(1);
q.front();  // 访问队首
q.back();   // 访问队尾
q.pop();

// Java：推荐使用 ArrayDeque（比 Stack/LinkedList 更高效）
import java.util.*;

// 作为栈
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);    // 等价于 addFirst
stack.pop();      // 等价于 removeFirst

// 作为队列
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);   // 等价于 addLast
queue.poll();     // 等价于 removeFirst

// 双端操作
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
int first = deque.removeFirst();  // 1
int last = deque.removeLast();    // 2

Java 注意事项：java.util.Stack 继承自 Vector，所有方法 synchronized，性能差，官方文档明确推荐使用 Deque<Integer> stack = new ArrayDeque<>();。LinkedList 实现了 Deque 接口但节点离散分配，缓存友好性差于 ArrayDeque。

7.4 单调队列：滑动窗口最大值

单调队列（Monotonic Queue）是双端队列的高级应用，队列内元素保持单调性。核心技巧：队尾弹出破坏单调性的元素，队首弹出超出窗口的元素。

经典问题：给定数组 nums 与窗口大小 k，求每个窗口的最大值（LeetCode 239）。

# Python：滑动窗口最大值（LeetCode 239）
from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """单调递减队列。O(n) 时间，O(k) 空间"""
    dq: deque[int] = deque()  # 存索引，对应值单调递减
    result: list[int] = []

    for i, num in enumerate(nums):
        # 1. 队首超出窗口则弹出
        while dq and dq[0] <= i - k:
            dq.popleft()
        # 2. 队尾弹出所有小于当前值的元素（保持单调递减）
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        # 3. 从第 k-1 个元素开始记录答案
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

复杂度分析：每个元素至多入队一次、出队一次（队首或队尾），总操作数 $\leq 2n$，故时间复杂度 $O(n)$，空间复杂度 $O(k)$（队列最多存 $k$ 个元素）。

8. 栈与队列的相互模拟

8.1 用两个栈实现队列

思路：维护 in_stack 与 out_stack。入队直接压入 in_stack；出队时若 out_stack 为空，将 in_stack 全部弹出压入 out_stack，再从 out_stack 弹出。

# Python：两个栈实现队列（LeetCode 232）
class MyQueue:
    def __init__(self) -> None:
        self._in: list[int] = []
        self._out: list[int] = []

    def push(self, x: int) -> None:
        self._in.append(x)

    def pop(self) -> int:
        self._ensure_out()
        return self._out.pop()

    def peek(self) -> int:
        self._ensure_out()
        return self._out[-1]

    def empty(self) -> bool:
        return not self._in and not self._out

    def _ensure_out(self) -> None:
        """摊还 O(1)：每个元素至多在两栈间移动一次"""
        if not self._out:
            while self._in:
                self._out.append(self._in.pop())

摊还分析：每个元素经历 4 次操作（push 入 in_stack、pop 出 in_stack、push 入 out_stack、pop 出 out_stack），$n$ 次入队 + $n$ 次出队总代价 $4n$，摊还每次 $O(1)$。

8.2 用两个队列实现栈

思路：入栈时压入 q1，将 q2 全部元素依次出队并入队 q1，再交换 q1 与 q2。出栈即从 q2 出队。

# Python：两个队列实现栈（LeetCode 225）
from collections import deque

class MyStack:
    def __init__(self) -> None:
        self._q1: deque[int] = deque()
        self._q2: deque[int] = deque()

    def push(self, x: int) -> None:
        """O(n)：将新元素放到队首"""
        self._q1.append(x)
        while self._q2:
            self._q1.append(self._q2.popleft())
        self._q1, self._q2 = self._q2, self._q1

    def pop(self) -> int:
        return self._q2.popleft()

    def top(self) -> int:
        return self._q2[0]

    def empty(self) -> bool:
        return not self._q2

复杂度：push $O(n)$、pop/top $O(1)$。也可用单队列实现：push 后将前 $n-1$ 个元素依次出队再入队，使新元素成为队首。

9. 栈与队列在搜索算法中的应用

9.1 DFS 与栈

深度优先搜索（DFS）天然递归，递归调用栈即隐式栈。也可用显式栈实现迭代 DFS：

# Python：迭代 DFS（二叉树前序遍历）
def preorder_traversal(root) -> list:
    """显式栈实现 DFS。O(n) 时间，O(h) 空间"""
    if not root:
        return []
    result: list = []
    stack: list = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # 右子树先入栈，左子树后入栈（保证左先访问）
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

9.2 BFS 与队列

广度优先搜索（BFS）天然使用队列：每次从队首取出节点，将其邻居加入队尾。

# Python：BFS（二叉树层序遍历，LeetCode 102）
from collections import deque

def level_order(root) -> list[list]:
    """BFS 层序遍历。O(n) 时间，O(w) 空间（w 为最大宽度）"""
    if not root:
        return []
    result: list[list] = []
    queue: deque = deque([root])
    while queue:
        level_size = len(queue)
        level: list = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

// Java：BFS 层序遍历
import java.util.*;

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> level = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

跨模块引用：BFS 与 DFS 的完整讨论参见 搜索算法；BFS 在最短路径中的应用参见 图算法。

10. 工程实践

10.1 函数调用栈

所有支持递归的编程语言都使用调用栈（call stack）管理函数调用：

• 每次函数调用，将栈帧（stack frame）压入栈，包含：返回地址、参数、局部变量、保存的寄存器；
• 函数返回时，弹出栈帧，恢复调用者上下文；
• 栈深度由操作系统限制（Linux 默认 8MB，Windows 默认 1MB），超出导致栈溢出（stack overflow）。

# Python：栈溢出示例
def infinite_recursion(n: int) -> None:
    infinite_recursion(n + 1)

# infinite_recursion(0) → RecursionError: maximum recursion depth exceeded
# Python 默认递归深度限制 1000（sys.getrecursionlimit()）

教学提示：Python 设定较低的递归深度限制（1000）是为了防止 C 栈溢出导致解释器崩溃。C/C++ 默认栈空间较大但无递归深度限制，需手动控制。Java 通过 -Xss 参数设置线程栈大小。

10.2 浏览器前进后退

浏览器使用双栈实现前进后退功能：

# Python：浏览器前进后退模拟
class Browser:
    def __init__(self, homepage: str) -> None:
        self._back: list[str] = [homepage]  # 后退栈，栈顶为当前页
        self._forward: list[str] = []        # 前进栈

    def visit(self, url: str) -> None:
        """访问新页面：清空前进栈"""
        self._back.append(url)
        self._forward.clear()

    def back(self) -> str:
        """后退：当前页压入前进栈，后退栈弹出"""
        if len(self._back) <= 1:
            raise IndexError('cannot back from homepage')
        self._forward.append(self._back.pop())
        return self._back[-1]

    def forward(self) -> str:
        """前进：前进栈弹出压入后退栈"""
        if not self._forward:
            raise IndexError('cannot forward, no history')
        self._back.append(self._forward.pop())
        return self._back[-1]

    def current(self) -> str:
        return self._back[-1]

10.3 文本编辑器撤销/重做

文本编辑器使用双栈实现撤销（undo）与重做（redo）：

# Python：撤销/重做栈
class TextEditor:
    def __init__(self) -> None:
        self._undo: list[str] = ['']  # 撤销栈，栈顶为当前内容
        self._redo: list[str] = []     # 重做栈

    def type(self, text: str) -> None:
        """输入文本：清空重做栈"""
        current = self._undo[-1] + text
        self._undo.append(current)
        self._redo.clear()

    def undo(self) -> str:
        if len(self._undo) <= 1:
            raise IndexError('nothing to undo')
        self._redo.append(self._undo.pop())
        return self._undo[-1]

    def redo(self) -> str:
        if not self._redo:
            raise IndexError('nothing to redo')
        self._undo.append(self._redo.pop())
        return self._undo[-1]

10.4 操作系统调度队列

操作系统使用多种队列管理进程：

• 就绪队列（ready queue）：等待 CPU 的进程，调度器从队首选取；
• 等待队列（wait queue）：等待 I/O 或事件的进程，事件触发时唤醒；
• 作业队列（job queue）：系统中所有进程；
• 设备队列（device queue）：等待特定 I/O 设备的进程。

轮转调度（Round-Robin）使用循环队列：每个进程分配一个时间片（如 10ms），时间片用完后放回队尾。

# Python：轮转调度模拟
from collections import deque
from typing import NamedTuple

class Process(NamedTuple):
    pid: int
    burst_time: int  # 剩余执行时间

def round_robin(processes: list[Process], time_slice: int = 10) -> list[int]:
    """轮转调度。返回各进程完成顺序的 pid"""
    queue: deque[Process] = deque(processes)
    completion_order: list[int] = []
    while queue:
        p = queue.popleft()
        execute_time = min(time_slice, p.burst_time)
        p = p._replace(burst_time=p.burst_time - execute_time)
        if p.burst_time > 0:
            queue.append(p)  # 重新入队
        else:
            completion_order.append(p.pid)
    return completion_order

10.5 消息队列中间件

工业级消息队列（Kafka、RabbitMQ、Redis Streams）本质是分布式 FIFO 队列：

• Kafka：基于日志结构，每个 partition 是有序队列，消费者按 offset 顺序消费；
• RabbitMQ：基于 AMQP 协议，队列支持多种路由模式（fanout、direct、topic）；
• Redis Streams：基于 radix tree 实现的持久化队列，支持消费者组。

# Python：基于 Redis 的简单消息队列
import redis

class RedisQueue:
    def __init__(self, name: str, host: str = 'localhost') -> None:
        self._r = redis.Redis(host=host)
        self._key = f'queue:{name}'

    def enqueue(self, item: str) -> None:
        self._r.lpush(self._key, item)  # 左端入队

    def dequeue(self, timeout: int = 0) -> str | None:
        # BRPOP 阻塞等待右端元素，超时返回 None
        result = self._r.brpop(self._key, timeout=timeout)
        return result[1].decode() if result else None

10.6 Go channel

Go 语言的 channel 是 CSP 模型的工业化实现，底层是有锁环形队列：

// Go：channel 作为并发安全队列
package main

func producer(ch chan<- int) {
    for i := 0; i < 10; i++ {
        ch <- i  // 入队（若 channel 满则阻塞）
    }
    close(ch)
}

func consumer(ch <-chan int, done chan<- bool) {
    for v := range ch {  // 出队（若 channel 空则阻塞）
        println(v)
    }
    done <- true
}

func main() {
    ch := make(chan int, 5)  // 缓冲区大小 5 的有锁环形队列
    done := make(chan bool)
    go producer(ch)
    go consumer(ch, done)
    <-done
}

教学提示：Go channel 的设计哲学是”Don’t communicate by sharing memory; share memory by communicating”，鼓励通过 channel（队列）而非共享变量实现并发同步，避免锁竞争与数据竞争。

10.7 性能基准对比

以下是 Python 不同栈/队列实现的 push/pop 性能对比（10^6 次操作，单位秒）：

结论：性能敏感场景优先使用语言内置实现（Python list/deque、C++ std::vector/std::deque、Java ArrayDeque），手写实现仅用于学习或特殊需求。

11. 案例研究

11.1 案例 1：LeetCode 20 有效括号

题意：判断由 ()、[]、{} 组成的字符串是否合法。

思路：栈匹配左括号，遇右括号检查栈顶。

def is_valid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack: list[str] = []
    for ch in s:
        if ch in pairs.values():
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

复杂度：$O(n)$ 时间，$O(n)$ 空间。

11.2 案例 2：LeetCode 150 逆波兰表达式求值

题意：求值后缀表达式。

思路：遇操作数入栈，遇运算符弹出两个操作数计算后入栈。

def eval_rpn(tokens: list[str]) -> int:
    stack: list[int] = []
    for token in tokens:
        if token in '+-*/':
            b, a = stack.pop(), stack.pop()
            stack.append({'+': a+b, '-': a-b, '*': a*b, '/': int(a/b)}[token])
        else:
            stack.append(int(token))
    return stack[0]

11.3 案例 3：LeetCode 739 每日温度

题意：对每天温度，求下一个更高温度还需等几天。

思路：单调递减栈，存索引。

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack: list[int] = []
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev = stack.pop()
            answer[prev] = i - prev
        stack.append(i)
    return answer

11.4 案例 4：LeetCode 239 滑动窗口最大值

题意：给定数组与窗口大小 $k$，求每个窗口的最大值。

思路：单调递减队列，存索引，队首为窗口最大值。

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()
    result: list[int] = []
    for i, num in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

11.5 案例 5：LeetCode 84 柱状图中最大矩形

题意：给定 $n$ 个柱子高度，求最大矩形面积。

思路：单调递增栈，弹出时计算以栈顶为高的矩形面积，加哨兵确保清空。

def largest_rectangle_area(heights: list[int]) -> int:
    stack: list[int] = []
    max_area = 0
    for i, h in enumerate(heights + [0]):  # 哨兵
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

11.6 案例 6：LeetCode 232 用栈实现队列

见 §8.1。

11.7 案例 7：LeetCode 102 二叉树层序遍历

见 §9.2。

12. 常见陷阱

12.1 顺序栈扩容时忘记拷贝元素

# 错误：扩容后丢失原数据
def push_wrong(self, item):
    if self._top == self._capacity:
        self._data = [None] * (self._capacity * 2)  # 直接替换，原数据丢失！
    self._data[self._top] = item
    self._top += 1

# 正确：先拷贝再替换
def push_correct(self, item):
    if self._top == self._capacity:
        new_data = [None] * (self._capacity * 2)
        for i in range(self._top):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity *= 2
    self._data[self._top] = item
    self._top += 1

12.2 循环队列判空判满歧义

# 错误：仅用 front == rear 无法区分空与满
def is_empty_wrong(self):
    return self._front == self._rear  # 空队列和满队列都返回 True！

# 正确：维护 size 变量
def is_empty_correct(self):
    return self._size == 0

def is_full_correct(self):
    return self._size == self._capacity

12.3 单调栈忘记存索引而是存值

# 错误：存值导致无法计算距离
def daily_temperatures_wrong(temperatures):
    stack: list[int] = []  # 存值
    answer = [0] * len(temperatures)
    for i, t in enumerate(temperatures):
        while stack and t > stack[-1]:
            prev_val = stack.pop()
            # 无法知道 prev_val 的索引，无法计算距离！
            pass
        stack.append(t)
    return answer

# 正确：存索引
def daily_temperatures_correct(temperatures):
    stack: list[int] = []  # 存索引
    answer = [0] * len(temperatures)
    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            prev = stack.pop()
            answer[prev] = i - prev  # 通过索引计算距离
        stack.append(i)
    return answer

12.4 链式队列出队后忘记更新尾指针

# 错误：队列只剩一个元素时，出队后 rear 仍指向被删除节点
def dequeue_wrong(self):
    if self.is_empty():
        raise IndexError
    item = self._front.value
    self._front = self._front.next
    # 若原队列只有一个元素，rear 仍指向被删除节点，导致内存泄漏与逻辑错误
    return item

# 正确：检查并更新 rear
def dequeue_correct(self):
    if self.is_empty():
        raise IndexError
    item = self._front.value
    self._front = self._front.next
    if self._front is None:  # 队列变空
        self._rear = None
    return item

12.5 Java 误用 Stack 类

// 不推荐：Stack 继承自 Vector，方法 synchronized，性能差
Stack<Integer> stack = new Stack<>();

// 推荐：使用 ArrayDeque 作为栈
Deque<Integer> stack = new ArrayDeque<>();

12.6 Python list 作为队列的低效用法

# 错误：list.pop(0) 是 O(n)，因为需要移动所有元素
queue = [1, 2, 3]
queue.append(4)     # O(1)
queue.pop(0)        # O(n)！n 次操作总 O(n^2)

# 正确：使用 collections.deque
from collections import deque
queue = deque([1, 2, 3])
queue.append(4)     # O(1)
queue.popleft()     # O(1)

12.7 单调队列忘记维护窗口边界

# 错误：未弹出超出窗口的队首，导致返回过期的最大值
def max_sliding_window_wrong(nums, k):
    dq = deque()
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])  # dq[0] 可能已超出窗口！
    return result

# 正确：弹出超出窗口的队首
def max_sliding_window_correct(nums, k):
    dq = deque()
    result = []
    for i, num in enumerate(nums):
        while dq and dq[0] <= i - k:  # 维护窗口边界
            dq.popleft()
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

12.8 递归栈溢出

# 错误：深度递归导致栈溢出
def deep_recursion(n):
    if n == 0:
        return 0
    return 1 + deep_recursion(n - 1)

# deep_recursion(10000) → RecursionError

# 正确：改为迭代
def deep_iteration(n):
    result = 0
    for _ in range(n):
        result += 1
    return result

13. 习题与解答

13.1 选择题

1. 下列关于栈与队列的描述，错误的是：

• A. 栈是 LIFO 结构，队列是 FIFO 结构
• B. 顺序栈的 push 操作均摊时间复杂度为 $O(1)$
• C. 循环队列的判空条件 front == rear 与判满条件 front == rear 相同，无法区分
• D. 双端队列可同时作为栈和队列使用

2. 给定入栈序列 1, 2, 3, 4, 5，下列哪个序列不可能是合法出栈序列？

• A. 5, 4, 3, 2, 1
• B. 2, 3, 4, 5, 1
• C. 4, 5, 3, 2, 1
• D. 2, 1, 4, 3, 5
• E. 3, 5, 4, 2, 1

3. 单调递减栈处理数组 [3, 1, 4, 1, 5, 9, 2, 6] 时，栈内最多同时有多少个元素？

• A. 3
• B. 4
• C. 5
• D. 6

13.2 填空题

1. 循环队列存储在数组 Q[0..n-1] 中，front 指向队首元素、rear 指向下一个待插入位置。当 front = 3、rear = 3 时，队列长度可能是 ____ 或 ____。

2. 已知栈的入栈序列为 a, b, c, d, e，出栈序列为 c, e, d, b, a，则栈的容量至少为 ____。

13.3 代码修正题

1. 以下代码实现”判断回文链表”，但存在 bug，请修正：

def is_palindrome(head) -> bool:
    stack = []
    p = head
    while p:
        stack.append(p.val)
        p = p.next
    p = head
    while p:
        if p.val != stack.pop():
            return False
        p = p.next
    return True

def is_palindrome(head) -> bool:
    if not head or not head.next:
        return True
    # 快慢指针找中点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # 前半入栈
    stack = []
    p = head
    while p is not slow:
        stack.append(p.val)
        p = p.next
    # 奇数长度跳过中点
    if fast:  # fast 不为 None 说明链表长度为奇数
        slow = slow.next
    # 后半与栈对比
    while slow:
        if slow.val != stack.pop():
            return False
        slow = slow.next
    return True