限制即力量 —— 栈与队列

有时候，“能做的事更少”反而是一种优势。栈和队列用最简单的规则，解决了编程世界中大量的实际问题。

📋 开篇自测：你已经知道多少？

1. 你在浏览器里连续点击了5个链接，然后按”返回”键——浏览器是怎么记住该回到哪个页面的？
2. 为什么递归调用过深会导致”栈溢出”（Stack Overflow）错误？
3. 操作系统是如何管理打印任务的？先点打印的文件一定先被打印吗？

---

一、从自助餐的盘子说起——什么是栈

你去过自助餐厅吧？入口处总有一摞盘子，一个叠一个地放着。你拿盘子的时候，只能从最上面拿；工作人员放盘子的时候，也只能往最上面放。

这就是**栈（Stack）**的本质——后进先出（LIFO: Last In, First Out）。

最后放上去的盘子最先被拿走。你不能从中间抽出一个盘子（除非你想让整摞盘子塌掉），也不能从最下面拿。

栈只允许两种操作：

• 入栈（push）： 把一个元素放到栈顶
• 出栈（pop）： 把栈顶的元素取走

class Stack:
    """用列表实现栈"""

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

    def push(self, item):
        """入栈：把元素放到栈顶"""
        self._items.append(item)

    def pop(self):
        """出栈：取走栈顶元素"""
        if self.is_empty():
            raise IndexError("栈是空的，没有元素可以取")
        return self._items.pop()

    def peek(self):
        """查看栈顶元素（不取走）"""
        if self.is_empty():
            raise IndexError("栈是空的")
        return self._items[-1]

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

    def size(self):
        return len(self._items)

入栈和出栈的时间复杂度都是 O(1)——因为只操作末尾元素。

栈在编程中的第一个大用途：函数调用

每次你调用一个函数，计算机就在”调用栈”（Call Stack）上压入一个新帧。函数执行完毕时，对应的帧被弹出，程序回到上一个函数继续执行。

def func_a():
    print("进入A")
    func_b()
    print("离开A")

def func_b():
    print("进入B")
    func_c()
    print("离开B")

def func_c():
    print("进入C")
    print("离开C")

func_a()
# 调用栈变化过程：
# [] -> [A] -> [A, B] -> [A, B, C] -> [A, B] -> [A] -> []

输出顺序：进入A -> 进入B -> 进入C -> 离开C -> 离开B -> 离开A

这就是为什么递归调用太深会”栈溢出”——每次递归都往调用栈上压一个帧，调用栈的大小是有限的（Python默认1000层），超出限制就崩了。

🤔 想一想 你有没有遇到过Python报 RecursionError: maximum recursion depth exceeded 的错误？现在你知道它的本质是什么了——调用栈被压满了。

---

二、栈的经典应用

应用1：括号匹配——编辑器是怎么检查你的代码的

写代码时，IDE会帮你检查括号有没有配对。这背后就是一个栈在工作。

思路很简单：遇到左括号就入栈，遇到右括号就看栈顶是不是匹配的左括号。

def is_valid_brackets(text):
    """检查括号是否匹配"""
    stack = Stack()
    pairs = {')': '(', ']': '[', '}': '{'}

    for char in text:
        if char in '([{':
            stack.push(char)
        elif char in ')]}':
            if stack.is_empty():
                return False  # 右括号多了
            if stack.pop() != pairs[char]:
                return False  # 类型不匹配
    return stack.is_empty()  # 栈空说明全部匹配

print(is_valid_brackets("({[]})"))   # True
print(is_valid_brackets("([)]"))     # False
print(is_valid_brackets("((()"))     # False

应用2：表达式求值——计算器是怎么工作的

你输入 3 + 4 * 2，计算器怎么知道要先算乘法再算加法？答案是用两个栈——一个存数字，一个存运算符。

def evaluate_expression(expression):
    """简单的四则运算表达式求值"""
    num_stack = []
    op_stack = []
    priority = {'+': 1, '-': 1, '*': 2, '/': 2}

    def apply_op():
        b = num_stack.pop()
        a = num_stack.pop()
        op = op_stack.pop()
        if op == '+': num_stack.append(a + b)
        elif op == '-': num_stack.append(a - b)
        elif op == '*': num_stack.append(a * b)
        elif op == '/': num_stack.append(a / b)

    tokens = expression.split()
    for token in tokens:
        if token.isdigit():
            num_stack.append(int(token))
        else:
            while (op_stack and
                   op_stack[-1] != '(' and
                   priority.get(op_stack[-1], 0) >= priority.get(token, 0)):
                apply_op()
            op_stack.append(token)

    while op_stack:
        apply_op()

    return num_stack[0]

print(evaluate_expression("3 + 4 * 2"))    # 11
print(evaluate_expression("10 + 2 * 3"))   # 16

上面的实现只支持基本的四则运算。如果要支持括号呢？只需要加两条规则：遇到左括号直接入运算符栈，遇到右括号就不断弹出运算符并计算，直到遇到左括号为止。

def evaluate_with_parentheses(expression):
    """支持括号的四则运算表达式求值"""
    num_stack = []
    op_stack = []
    priority = {'+': 1, '-': 1, '*': 2, '/': 2}

    def apply_op():
        b = num_stack.pop()
        a = num_stack.pop()
        op = op_stack.pop()
        if op == '+': num_stack.append(a + b)
        elif op == '-': num_stack.append(a - b)
        elif op == '*': num_stack.append(a * b)
        elif op == '/': num_stack.append(a / b)

    tokens = expression.split()
    for token in tokens:
        if token.isdigit():
            num_stack.append(int(token))
        elif token == '(':
            op_stack.append(token)  # 左括号直接入栈
        elif token == ')':
            # 遇到右括号，不断计算直到碰到左括号
            while op_stack and op_stack[-1] != '(':
                apply_op()
            op_stack.pop()  # 弹出左括号
        else:
            while (op_stack and
                   op_stack[-1] != '(' and
                   priority.get(op_stack[-1], 0) >= priority.get(token, 0)):
                apply_op()
            op_stack.append(token)

    while op_stack:
        apply_op()

    return num_stack[0]

print(evaluate_with_parentheses("( 3 + 4 ) * 2"))    # 14
print(evaluate_with_parentheses("2 * ( 1 + 3 )"))    # 8
print(evaluate_with_parentheses("( 2 + 3 ) * ( 4 - 1 )"))  # 15

注意：这里的token仍然需要用空格分隔（包括括号前后），这是为了保持代码的简洁性。实际的计算器还需要处理没有空格分隔的情况、负数、浮点数等。

应用3：撤销操作——Ctrl+Z的秘密

文本编辑器的撤销功能天然适合用栈来实现。每次操作都入栈，每次按Ctrl+Z就弹出最近的操作并反转它。

class TextEditor:
    """带撤销功能的简易文本编辑器"""

    def __init__(self):
        self.content = ""
        self.history = Stack()

    def type_text(self, text):
        self.history.push(('insert', len(self.content), text))
        self.content += text

    def undo(self):
        if self.history.is_empty():
            print("没有可撤销的操作")
            return
        action, position, text = self.history.pop()
        if action == 'insert':
            self.content = self.content[:position]

# 演示
editor = TextEditor()
editor.type_text("Hello")
editor.type_text(" World")
print(editor.content)   # "Hello World"
editor.undo()
print(editor.content)   # "Hello"
editor.undo()
print(editor.content)   # ""

---

三、队列——先来后到的公平世界

和栈不同，**队列（Queue）遵循的是先进先出（FIFO: First In, First Out）**原则。

最好的比喻就是排队买奶茶——先到的人先买到，后来的人只能排在队尾。你不能插队，也不能让队尾的人先买。

队列的两种核心操作：

• 入队（enqueue）： 新元素加入队尾
• 出队（dequeue）： 队头元素离开队列

from collections import deque

class Queue:
    """用双端队列实现队列"""

    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        """入队：加入队尾"""
        self._items.append(item)

    def dequeue(self):
        """出队：移除队头"""
        if self.is_empty():
            raise IndexError("队列是空的")
        return self._items.popleft()

    def front(self):
        """查看队头元素"""
        if self.is_empty():
            raise IndexError("队列是空的")
        return self._items[0]

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

    def size(self):
        return len(self._items)

注意这里用了 collections.deque 而不是普通列表。因为列表的 pop(0) 是O(n)操作（需要移动所有元素），而deque的 popleft() 是O(1)。

队列的经典应用

应用1：打印任务管理

办公室里的共享打印机就是一个队列。谁先点了打印，谁的文件就先被打印。

def simulate_printer(jobs):
    """模拟打印队列"""
    print_queue = Queue()
    for job in jobs:
        print_queue.enqueue(job)
        print(f"任务'{job}'加入打印队列")

    while not print_queue.is_empty():
        current_job = print_queue.dequeue()
        print(f"正在打印：{current_job}")

simulate_printer(["报告.pdf", "简历.docx", "照片.jpg"])

应用2：消息队列——系统间的”传话筒”

在大型系统中，服务之间的通信经常用消息队列。生产者把消息放入队列，消费者按顺序取出处理。这样即使消费者处理速度跟不上，消息也不会丢失。

class MessageQueue:
    """简易消息队列"""

    def __init__(self):
        self.queue = Queue()

    def send(self, message):
        self.queue.enqueue(message)
        print(f"消息已发送：{message}")

    def receive(self):
        if self.queue.is_empty():
            print("没有新消息")
            return None
        msg = self.queue.dequeue()
        print(f"收到消息：{msg}")
        return msg

mq = MessageQueue()
mq.send("用户下单了")
mq.send("支付成功了")
mq.send("开始发货")
mq.receive()  # 收到消息：用户下单了
mq.receive()  # 收到消息：支付成功了

🤔 想一想 你用过的哪些软件或系统背后可能用到了队列？想想外卖平台的订单处理、客服系统的排队等候、12306的购票队列…

---

四、队列的变体——双端队列与优先队列

双端队列（Deque）

普通队列只能从一端进、另一端出。双端队列两端都可以进出，就像一个两头都能开门的走廊。

Python的 collections.deque 就是双端队列：

from collections import deque

dq = deque()
dq.append(1)        # 从右端加入
dq.appendleft(0)    # 从左端加入
dq.append(2)        # 从右端加入

print(list(dq))     # [0, 1, 2]

dq.pop()             # 从右端取出：2
dq.popleft()         # 从左端取出：0
print(list(dq))     # [1]

一个经典应用是滑动窗口最大值问题——用双端队列可以在O(n)时间内找到每个窗口内的最大值。

优先队列（Priority Queue）

有时候不是”先来先服务”，而是”最重要的先服务”。比如医院急诊——不管你排第几个，病情最紧急的病人总是优先治疗。

import heapq

class PriorityQueue:
    """用堆实现优先队列"""

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

    def push(self, priority, item):
        """加入队列，数字越小优先级越高"""
        heapq.heappush(self._items, (priority, item))

    def pop(self):
        """取出优先级最高的元素"""
        if not self._items:
            raise IndexError("优先队列为空")
        return heapq.heappop(self._items)

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

# 医院急诊模拟
er = PriorityQueue()
er.push(3, "感冒发烧")
er.push(1, "心脏骤停")
er.push(2, "骨折")
er.push(4, "皮肤过敏")

while not er.is_empty():
    priority, patient = er.pop()
    print(f"[优先级{priority}] 正在处理：{patient}")
# 输出：心脏骤停 -> 骨折 -> 感冒发烧 -> 皮肤过敏

---

五、循环队列——让空间循环利用

普通队列有一个问题：随着元素不断入队出队，队头前面的空间就浪费了。就像一排座位，前面的人走了但没人补上来，只能一直往后坐。

循环队列把数组的首尾相连，形成一个”环”。当队尾到达数组末尾时，如果前面有空位，就绕回到数组开头。

class CircularQueue:
    """循环队列"""

    def __init__(self, capacity):
        self._items = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, item):
        if self._size == self._capacity:
            raise OverflowError("队列已满")
        self._items[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity  # 取模实现循环
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("队列为空")
        item = self._items[self._head]
        self._items[self._head] = None
        self._head = (self._head + 1) % self._capacity  # 取模实现循环
        self._size -= 1
        return item

    def display(self):
        result = []
        idx = self._head
        for _ in range(self._size):
            result.append(str(self._items[idx]))
            idx = (idx + 1) % self._capacity
        return " -> ".join(result)

# 演示
cq = CircularQueue(4)
cq.enqueue("A")
cq.enqueue("B")
cq.enqueue("C")
print(cq.display())      # A -> B -> C
cq.dequeue()              # 取出A
cq.enqueue("D")
cq.enqueue("E")           # E绕回到了A原来的位置
print(cq.display())       # B -> C -> D -> E

这个技巧的精髓在于那个 % self._capacity（取模运算）。它让索引到达末尾后自动绕回到开头，就像时钟的指针走过12点后回到1点。

⚠️ 常见误区

• 误区1：“栈和队列是两种独立的数据结构” —— 从本质上说，栈和队列都是对数组或链表施加了特定操作限制的”受限版”。正是这些限制让它们在特定场景下更可靠、更不容易出错。
• 误区2：“我用列表也能实现栈和队列，何必单独学” —— 当然可以。但使用专门的栈/队列接口有两个好处：一是代码意图更清晰（别人一看就知道你在做什么），二是减少误操作（你不会不小心从中间取元素）。
• 误区3：“优先队列和普通队列差不多” —— 差很远。普通队列是O(1)入队O(1)出队，优先队列的入队或出队至少有一个是O(log n)，因为需要维护优先级关系。

---

六、栈与队列的对比总结

特性	栈	队列
顺序原则	后进先出（LIFO）	先进先出（FIFO）
生活比喻	叠盘子	排队买票
添加操作	push（压入栈顶）	enqueue（加入队尾）
移除操作	pop（弹出栈顶）	dequeue（移除队头）
典型应用	函数调用、撤销、括号匹配	任务调度、BFS、消息队列
Python实现	list（用append/pop）	collections.deque

一个有趣的事实：用两个栈可以模拟一个队列，用两个队列也可以模拟一个栈。 这是面试中常考的题目，思路如下：

class QueueUsingTwoStacks:
    """用两个栈实现队列"""

    def __init__(self):
        self.in_stack = []   # 用于入队
        self.out_stack = []  # 用于出队

    def enqueue(self, item):
        self.in_stack.append(item)

    def dequeue(self):
        if not self.out_stack:
            # 把in_stack的所有元素倒入out_stack
            # 顺序就反过来了，最先入队的到了栈顶
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        if not self.out_stack:
            raise IndexError("队列为空")
        return self.out_stack.pop()

# 验证
q = QueueUsingTwoStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1（先进先出）
print(q.dequeue())  # 2
q.enqueue(4)
print(q.dequeue())  # 3
print(q.dequeue())  # 4

---

📝 掌握度自测

1. 概念题： 用自己的话解释”后进先出”和”先进先出”的区别，并各举一个你在日常生活中见过的例子。
2. 代码题： 用栈实现一个函数，判断一个字符串是否是回文（正着读和反着读一样），比如”racecar”。
3. 分析题： 为什么Python中用list实现队列（用list.pop(0)做出队操作）效率很差？具体差在哪里？
4. 设计题： 如果你要实现一个”最近浏览记录”功能（最多保存50条，超过就淘汰最旧的），你会用栈还是队列？还是其他数据结构？
5. 挑战题： 实现一个”最小栈”——除了push和pop之外，还支持O(1)时间获取栈中最小元素的操作。

💡 自我评估

• 全部答对：栈和队列已经是你的趁手工具了，继续前进。
• 答对3-4题：核心掌握得不错，建议把挑战题多想想。
• 答对1-2题：重新阅读”经典应用”部分，每个应用场景都试着手写一遍代码。
• 全部答错：栈和队列是最基础的数据结构之一，建议你放慢节奏，把每段代码都实际运行一下，观察输出。

---

到目前为止，我们学的数据结构都需要遍历才能找到目标元素。有没有一种方法能做到”一步到位”的查找？下一章的主角哈希表就有这个本领——平均 O(1) 的查找速度，堪称数据结构中的”效率之王”。