第3章：栈、队列与双端队列

---

元数据卡

属性	值
章节编号	Vol 2 · 第3章
难度等级	（入门加固）
前置知识	数组、链表（第2章）
核心技能	LIFO / FIFO 操作、循环索引、单调性思维
关键字	Stack Queue Deque Circular Buffer Monotonic Stack Monotonic Queue BFS

---

你在哪

穿过两条岔路后，你发现森林里的资源需要排队使用——一份干粮只能顺序传递（队列）、但你必须先把最近拿到的地图处理完才能看更早的（栈）。角落里还有一个叫 Deque 的精灵——它能在两边同时操作。

你站在算法森林的入口——"基础营"。身后的帐篷里是上一章你亲手搭建的数组和链表。面前是一条被藤蔓覆盖的小路，通向森林深处。

路边立着一块木牌：

前方三种容器：后进先出、先进先出、两头通行。选对容器，过河不湿鞋。

你不是来逛的。你身后的野猪追兵已经逼近，你得选对容器才能活下来。

---

你的任务

本章分层

• 必读：栈（LIFO）和队列（FIFO）的核心概念与操作（push/pop/peek/enqueue/dequeue）；用栈解决括号匹配；用队列理解 BFS 层序遍历的直觉
• 选读：双端队列（deque）的头尾 O(1) 操作；循环队列的实现原理
• 深水区：单调栈和单调队列——算法技巧，首次接触时了解概念即可

本章不会要求你掌握

• 无锁队列（Lock-Free Queue）的并发实现
• LLVM / 硬件栈的具体细节
• 复杂单调栈变形（如直方图最大矩形）

1. 用数组和链表各实现一遍 栈（Stack）
2. 写出 队列（Queue） 的朴素实现和 循环队列（Circular Queue）
3. 用 Python 的 collections.deque 写一个 双端队列
4. 用栈解决 括号匹配
5. 用队列实现 BFS 层序遍历

---

遭遇战 → 获得技能

遭遇 #1：后进先出——栈

你跳进一条死胡同。唯一的活路是一扇从外面推开的门。你必须把东西先放进去，走着走着发现最后放进去的恰恰是打开门的钥匙。

栈 = 后进先出（LIFO, Last In First Out）

这是你掉进陷阱后趴在一张破草纸上发现的。手边只有树枝和泥巴：

# 栈其实就是……加了限制的列表
# 你只能从顶部操作：push（压入）、pop（弹出）、peek（看一眼顶部）

### 数组实现 —— 底层就是 Python list ###

class ArrayStack:
    """用数组实现的栈 —— 最简单，也最快"""

    def __init__(self):
        self._data = []          # 底层就是个 list

    def push(self, item):
        self._data.append(item)  # 从尾部添加 —— O(1) 均摊

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()  # 从尾部弹出 —— O(1)

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

# 试试看
st = ArrayStack()
st.push("🗝️ 钥匙")
st.push("🧱 砖头")
st.push("🐗 野猪")
print(st.pop())    # 🐗 野猪 —— 后放进去的先出来
print(st.pop())    # 🧱 砖头
print(st.pop())    # 🗝️ 钥匙 —— 先放进去的最后出来

🐗 野猪
🧱 砖头
🗝️ 钥匙

** Java 差异：** Java 的 Stack 继承自 Vector（线程安全但老了），官方推荐用 Deque 代替：

`Deque<String> stack = new ArrayDeque<>();`
stack.push("钥匙");
stack.push("野猪");
String top = stack.pop();  // "野猪"

注意 ArrayDeque 初始容量 16，扩容比 ArrayList 更省。

** C++ 差异：** C++ 的 std::stack 默认底层是 std::deque（不是 std::vector）：

std::stack<std::string> st;
st.push("钥匙");
st.push("野猪");
auto top = st.top();  // "野猪"
st.pop();             // 注意：pop 不返回值

std::stack 没有 peek()，得先 top() 再 pop()。这是 C++ 容器的"异常安全"设计哲学。

链表实现 —— 反向思考

你发现野猪追得太紧，得换个思路——不用连续内存，用节点串起来。

class Node:
    """链表节点，比数组多了一个指针"""

    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


class LinkedStack:
    """用链表实现的栈 —— push/pop 全部在头部 O(1)"""

    def __init__(self):
        self._head = None
        self._size = 0

    def push(self, item):
        # 新节点指向当前头部，新节点变成头部
        self._head = Node(item, self._head)
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        value = self._head.value
        self._head = self._head.next  # 头部直接跳过第一个
        self._size -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._head.value

    def is_empty(self):
        return self._head is None

    def __len__(self):
        return self._size

# 对比跑一下
ast = ArrayStack()
lst = LinkedStack()
for i in range(5):
    ast.push(i)
    lst.push(i)
for _ in range(5):
    print(f"数组栈: {ast.pop()}  |  链表栈: {lst.pop()}")

数组栈: 4  |  链表栈: 4
数组栈: 3  |  链表栈: 3
数组栈: 2  |  链表栈: 2
数组栈: 1  |  链表栈: 1
数组栈: 0  |  链表栈: 0

区别在哪？ 数组栈偶尔扩容痛一下（均摊 O(1)），链表栈每次都要分配节点（常数开销大但时间稳定）。野猪不关心这个，你跑掉就行。

---

遭遇 #2：先进先出——队列

逃出死胡同，你跳上一艘独木舟。前面是一条单行河，先上船的人先下船——这就是队列。

### 朴素队列 —— 用 list 是错的 ###

class NaiveQueue:
    """别这么写 —— 只是为了展示为什么不对"""

    def __init__(self):
        self._data = []

    def enqueue(self, item):
        self._data.append(item)   # 尾部入队 O(1)

    def dequeue(self):
        # 从头部出队 —— O(n) ！每次都要把后面所有元素往前挪
        return self._data.pop(0)  # ❌ 这是性能灾难

# 1000 个元素出队，就要挪~500 次 1000
## 队列的精神折磨

真的队列长这样：

### 循环队列 —— 用固定数组，头尾指针转圈走 ###

class CircularQueue:
    """
    循环队列：头尾指针在环形空间里追着跑。
    浪费一格来区分"空"和"满"。
    """

    def __init__(self, capacity=8):
        self._data = [None] * capacity
        self._capacity = capacity
        self._head = 0    # 队首指针
        self._tail = 0    # 队尾指针（下一个插入位置）
        self._size = 0

    def enqueue(self, item):
        if self.is_full():
            self._resize(self._capacity * 2)
        self._data[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity  # 转圈！
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        value = self._data[self._head]
        self._data[self._head] = None  # 释放引用
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return value

    def is_empty(self):
        return self._size == 0

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

    def _resize(self, new_cap):
        """扩容时重新排列 —— 让 head 回到 0"""
        old = self._data
        self._data = [None] * new_cap
        for i in range(self._size):
            self._data[i] = old[(self._head + i) % self._capacity]
        self._head = 0
        self._tail = self._size
        self._capacity = new_cap

# 跑一圈看看
cq = CircularQueue(4)
for i in range(1, 5):
    cq.enqueue(i)
print("出队:", cq.dequeue())
print("出队:", cq.dequeue())
cq.enqueue(5)
cq.enqueue(6)
print("当前状态: ", end="")
while not cq.is_empty():
    print(cq.dequeue(), end=" ")
print()

出队: 1
出队: 2
当前状态: 3 4 5 6

** Java 差异：** Java 的 ArrayDeque 就是循环数组实现，没有 Queue 单字类：

`Queue<String> queue = new ArrayDeque<>();`
queue.offer("第一个");
queue.offer("第二个");
String front = queue.poll();  // "第一个"

offer 入队，poll 出队（空返回 null），remove 出队（空抛异常）。

Python 偷懒方案

真写业务代码时，没人写循环队列。Python 标准库给了你：

from collections import deque

dq = deque()
dq.append("第一")     # 右侧入队
dq.append("第二")
print(dq.popleft())   # 第一 —— 左侧出队 ❄️
print(dq.popleft())   # 第二

deque 是 双端队列（Double-Ended Queue），头尾操作都是 O(1)。但现在是战地教学，自己造轮子是为了理解原理。

---

遭遇 #3：双端队列——左右通吃

独木舟漂到一个三岔河口。左边有鱼，右边有果。你发现河马大爷左右都能张嘴——双端队列就是河马的嘴。

from collections import deque

## Deque——两边都能加，两边都能取
river = deque()

# 右侧（尾部）操作 —— 和普通队列一样
river.append("🐟 鱼")          # 右边进
river.append("🦐 虾")

# 左侧（头部）操作 —— 普通队列做不到
river.appendleft("🍎 苹果")     # 左边进
river.appendleft("🍌 香蕉")

print("当前队列:", list(river))

# 两边都能取
print("右边出:", river.pop())       # 🦐 虾
print("左边出:", river.popleft())   # 🍌 香蕉

当前队列: ['🍌 香蕉', '🍎 苹果', '🐟 鱼', '🦐 虾']
右边出: 🦐 虾
左边出: 🍌 香蕉

什么时候用双端？ 滑动窗口、撤销/重做、任务双端调度。后面你会亲眼看到。

---

常见陷阱

技能到手了。现在动手解决真实问题。

拆解 #1：括号匹配 —— 栈的绝配

你怎么知道 [{()}] 是对的而 [(]) 是错的？编译器和解释器在扫描代码时就这么判断——用栈。

def is_valid_brackets(s: str) -> bool:
    """检查括号是否匹配 —— 栈的经典应用"""
    pair = {')': '(', ']': '[', '}': '{'}
    stack = []

    for ch in s:
        if ch in '({[':                     # 左括号 → 压栈
            stack.append(ch)
        elif ch in ')]}':                   # 右括号 → 检查栈顶
            if not stack or stack.pop() != pair[ch]:
                return False
        # 其他字符忽略（代码里总有文字）

    return not stack  # 栈空了才完全匹配


# 试一试
tests = [
    "()",                # ✅
    "()[]{}",            # ✅
    "({[]})",            # ✅
    "({[}])",            # ❌ 类型交错
    "((()))",            # ✅
    "(",                 # ❌ 多了一个左括号
    "]",                 # ❌ 多了一个右括号
]
for t in tests:
    r = is_valid_brackets(t)
    icon = "✅" if r else "❌"
    print(f"{icon}  {t}")

✅  ()
✅  ()[]{}
✅  ({[]})
❌  ({[}])
✅  ((()))
❌  (
❌  ]

为什么是栈？ 最近出现的左括号必须最先被匹配——这不就是后进先出吗？编译器、IDE 语法高亮、JSON 验证器，全在用。

---

拆解 #2：BFS 层序遍历 —— 队列的天命

你要在森林里一层一层地搜：先搜脚下这一圈，再搜下一圈，再下一圈。BFS（广度优先搜索）天生就是队列。

比如你在一棵二叉树里找宝藏，要打印每一层的节点：

from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def bfs_level_order(root):
    """层序遍历 —— 队列一次进出解决"""
    if not root:
        return []
    result = []
    q = deque([root])

    while q:
        level_size = len(q)     # 当前层的节点数
        level = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)

    return result


# 造一棵树
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6
root = TreeNode(1)
root.left = TreeNode(2); root.right = TreeNode(3)
root.left.left = TreeNode(4); root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

print(bfs_level_order(root))

[[1], [2, 3], [4, 5, 6]]

队列在这里干了什么？ 每一轮把当前层的孩子按顺序排到队尾——"先来先出"，天然就是按层展开。

** 如果用的是普通 list 做队列：** pop(0) 每出队一次就 O(n)，一棵 n 个节点的树 BFS 变成 O(n²)。 用循环队列或 deque，总复杂度 O(n)。数据结构选错，复杂度翻倍。

---

进阶挑战：单调栈 —— 下一个更大元素

本节属于进阶内容。 主线先掌握括号匹配和 BFS 即可。单调栈是一个重要的技巧，但建议回来看。

你拿到了森林藏宝图，但每个数字旁边只标了下一步的线索。你得找到每个数字右边第一个比它大的数字。这个谜题叫 "Next Greater Element"，是森林石碑上的常见试炼。

def next_greater_element(nums):
    """
    单调递减栈：找右边第一个更大的元素
    栈里存的是索引，不是值。
    """
    n = len(nums)
    result = [-1] * n       # 默认 -1（没有更大的）
    stack = []              # 单调递减栈（从栈底到栈顶递减）

    for i in range(n):
        # 当前数字比栈顶大？说明栈顶找到了它的"下一个更大"
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)     # 当前索引入栈

    return result


# 试试
arr = [2, 1, 5, 3, 4]
print(f"原数组:      {arr}")
print(f"下一个更大:  {next_greater_element(arr)}")

原数组:      [2, 1, 5, 3, 4]
下一个更大:  [5, 5, -1, 4, -1]

为什么是单调栈？ 暴力法是 O(n²)——每个元素往后扫。单调栈让每个元素进栈一次出栈一次，O(n)。当你在"找右边第一个更大/更小"时，先想想单调栈。

** Java 差异：** Java 中单调栈通常用 Deque<Integer> 当栈用：

`Deque<Integer> stack = new ArrayDeque<>();`
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
    int idx = stack.pop();
    result[idx] = nums[i];
}
stack.push(i);

---

进阶挑战：单调队列 —— 滑动窗口最大值

本节属于进阶内容。 主线先掌握栈、队列、deque 的基本操作即可。

你在森林望远镜里一次只能看到连续 k 个树。每移动一格，你要报告当前窗口里最高的树。不看全部，只问当前窗口的最大值。

这就是 239. 滑动窗口最大值——单调队列入门题。

from collections import deque

def max_sliding_window(nums, k):
    """
    单调递减队列：队首就是当前窗口的最大值
    队列里存索引，不是值。
    核心规则：
      1. 窗口右移 → 右边新元素入队列
      2. 窗口左移 → 左边旧元素出队列
      3. 保持单调递减 → 新来的比队尾大，队尾滚蛋
    """
    dq = deque()        # 单调递减队列（存索引）
    result = []

    for i, val in enumerate(nums):
        # 右边：把比新元素小的全部踢出去（它们不可能是最大值了）
        while dq and nums[dq[-1]] < val:
            dq.pop()

        dq.append(i)

        # 左边：队首如果已经滑出窗口了，移除
        if dq[0] <= i - k:
            dq.popleft()

        # 当窗口长度达到 k 时，记录结果
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result


arr = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(f"数组: {arr}")
print(f"窗口大小 k={k}")
print(f"滑动最大值: {max_sliding_window(arr, k)}")

数组: [1, 3, -1, -3, 5, 3, 6, 7]
窗口大小 k=3
滑动最大值: [3, 3, 5, 5, 6, 7]

手算验证： 窗口 [1,3,-1] 最大是 3，滑到 [3,-1,-3] 最大还是 3，再滑到 [-1,-3,5] 最大是 5……和输出一致。

为什么单调队列能 O(n)？ 每个元素最多入队一次出队一次。暴力法每窗口扫一遍是 O(n·k)。

** C++ 差异：** C++ 用 std::deque 实现是一样的逻辑：

`deque<int> dq;`
for (int i = 0; i < n; ++i) {
    while (!dq.empty() && nums[dq.back()] < nums[i])
        dq.pop_back();
    dq.push_back(i);
    if (dq.front() <= i - k)
        dq.pop_front();
    if (i >= k - 1)
        res.push_back(nums[dq.front()]);
}

区别：C++ 的 deque 是分段连续存储，和 Python 的 collections.deque 原理相似但底层实现不同。

---

通关挑战

试试这些——在森林里练过的，到代码世界也一样用：

难度	题目	考察点
	LeetCode 20. Valid Parentheses	栈 + 括号匹配
	LeetCode 232. Implement Queue using Stacks	双栈模拟队列
	LeetCode 155. Min Stack	辅助栈存最小值
	LeetCode 239. Sliding Window Maximum（选做）	单调队列
	LeetCode 739. Daily Temperatures（选做）	单调栈

进阶挑战： 用两个栈实现一个队列的 push、pop、peek、empty——这正是 LeetCode 232。思路：一个栈负责入，一个栈负责出，出栈空了就把入栈的全部倒进去。

---

验收标准

通关后你真的理解了吗？问自己：

• [ ] 手写一个数组栈和一个链表栈，说出各自的内存/性能特点
• [ ] 解释为什么 list.pop(0) 不是队列，循环队列的 (head + 1) % cap 在干什么
• [ ] deque 的头尾操作各是什么复杂度
• [ ] 括号匹配为什么非栈不可——能用队列做吗？为什么不行
• [ ] BFS 层序遍历为什么用队列不用栈
• [ ] 单调栈/单调队列为什么能把 O(n²) 变成 O(n)——每个元素进/出多少次

---

常见卡点

卡点	破法
循环队列的判空判满	浪费一格是最简单的方案。head == tail 空，(tail+1)%cap == head 满
单调栈存索引还是值	存索引。存值你拿不到位置，存索引值可以查。面试写错就尴尬了
滑动窗口左边不及时 pop	检查 dq[0] <= i - k，别检查值——值可能重复
BFS 分不清层	在 while 开头记录 len(q)，这代表当前层的节点数。每个 for 循环跑完就是一层

---

现在不需要理解

• 栈的硬件实现 —— CPU 调用栈是硬件体系结构的事，数据结构层面你只关心逻辑
• 无锁队列（Lock-Free Queue） —— 并发编程章节的事，现在别碰
• deque 的分段存储细节 —— Python 的 deque 是用双向链表 + 定长块数组实现的"混合体"，但作为使用者你只关心它是双端 O(1)
• 优先队列（Priority Queue） —— 这是堆（第6章）的事

---

旅人笔记

你从森林入口走到了第一个营地。总结下这一趟：

1. 栈 —— 先进后出。数组实现最简单，链表实现最灵活。核心操作：push / pop / peek。
2. 队列 —— 先进先出。循环数组是正经实现，别用 list.pop(0) 糊弄。
3. 双端队列 —— collections.deque 是 Python 神器，头尾 O(1)。
4. 括号匹配 —— 左括号进栈，右括号和栈顶比。编译器每天都在做这件事。
5. BFS 层序遍历 —— 没队列你没法优雅地按层展开。
6. 单调栈/单调队列 —— 每个元素进栈/队列一次出一次，O(n) 吊打暴力 O(n²)。

你的行囊里现在装了三种容器。前面就是哈希森林，那里的树靠哈希函数导航——每个元素都有一个"钥匙孔"。

但那是下一章的事了。先打个盹儿，野猪已经跑远了。

---

🔜 下一站预告

第4章：哈希表——"把 O(n) 的查找变成 O(1)，靠的是魔法还是数学？你马上就会知道。顺便，你得先想清楚：如果两个东西算出的钥匙一样怎么办？"

---

** 代码仓库位置：** vol-02-dsa/examples/ch03/ 下有此章完整示例代码