如果说数组和链表回答的是"数据怎么存",栈和队列回答的是"数据按什么顺序取"。这两种结构在操作系统、编译器、网络协议里无处不在,也是算法题的常客。这篇文章我们用 Python 把它们讲透:从最朴素的实现,到括号匹配、表达式求值、滑动窗口四个实战场景。

1. 栈:后进先出

栈(stack)只允许在一端操作:这一端叫栈顶。放数据叫入栈(push),取数据叫出栈(pop),而且永远先取到最后放进去的那个——这就是"后进先出"(LIFO)。想象一摞盘子,你总是先拿最上面那个。Python 里用 list 就能完美模拟栈:append 入栈、pop() 出栈、stack[-1] 只看栈顶不弹出。

stack = []
stack.append(1)          # 入栈
stack.append(2)
stack.append(3)
top = stack[-1]          # 看栈顶:3,不弹出
popped = stack.pop()     # 出栈:3
print(top, popped, stack)  # 3 3 [1, 2]
print(len(stack) == 0)     # False,栈还没空

栈的经典应用场景:函数调用的调用栈(递归就是靠它)、浏览器的前进后退、编辑器的撤销操作。理解栈,先记住一句话:它把"最近发生的事"放在最上面。

2. 队列:先进先出

队列(queue)正好相反:一端入队、另一端出队,先来的先走,即"先进先出"(FIFO),就像食堂排队打饭。Python 里实现队列要用 collections.deque(双端队列),不要用 list——list.pop(0) 删除头部元素时,后面所有元素都要往前挪,是 O(n) 操作;而 deque 两端增删都是 O(1)。

from collections import deque

q = deque()
q.append("a")            # 队尾入队
q.append("b")
q.append("c")
first = q.popleft()      # 队头出队
print(first, list(q))    # a ['b', 'c']
print(len(q))            # 2

看到 deque 这个名字别慌,它读作"deck",是 double-ended queue 的缩写,意思就是两端都能增删的队列。它既可以当队列用,也可以当栈用,是 Python 标准库里的常青树。

3. 实战一:括号匹配

括号匹配是栈的入门必做题:给定一个只含 ()[]{} 的字符串,判断括号是否成对且嵌套正确。思路:遇到左括号就入栈,遇到右括号就检查栈顶是不是对应的左括号——正好利用栈"后进先出"的特性,让最内层的括号最先被匹配。

def is_valid(s):
    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               # 全部匹配完,栈应为空

print(is_valid("()[]{}"))    # True
print(is_valid("([)]"))      # False,交叉嵌套不合法
print(is_valid("(]"))        # False
print(is_valid("("))         # False,左括号没闭合

两个细节:一是用字典把右括号映射到左括号,代码比一堆 if 清爽;二是最后要检查 not stack——很多人忘了"左括号多了"也是非法,比如 "(("。

4. 实战二:逆波兰表达式求值

逆波兰表达式(后缀表达式)把运算符写在数字后面,比如 "2 1 + 3 *" 就是 (2 + 1) * 3。它的好处是不需要括号,也没有优先级问题。求值过程依然靠栈:遇到数字入栈,遇到运算符就弹出两个数计算,再把结果压回去。

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in "+-*/":
            b = stack.pop()   # 注意:先弹出的是右操作数
            a = stack.pop()
            if t == '+':
                stack.append(a + b)
            elif t == '-':
                stack.append(a - b)
            elif t == '*':
                stack.append(a * b)
            else:
                stack.append(int(a / b))  # 除法向零取整
        else:
            stack.append(int(t))
    return stack[0]

print(eval_rpn(["2", "1", "+", "3", "*"]))   # 9
print(eval_rpn(["4", "13", "5", "/", "+"]))  # 6
print(eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*"]))  # 0

这里有个经典坑:a / b 的结果在 Python 里是浮点数,而题目通常要求整数除法且向零取整,所以要用 int(a / b) 而不是 a // b——后者是向下取整,对负数会出错(比如 -1 // 2 == -1,而 int(-1 / 2) == 0)。

5. 实战三:单调栈求下一个更大元素

给一个数组,求每个元素右边第一个比它大的数,没有则为 -1。暴力法是双重循环 O(n²);单调栈可以做到 O(n)。核心思路:维护一个从栈底到栈顶单调递减的栈(存下标),新元素入栈前,把所有比它小的下标弹出——这些下标的下一个更大元素,就是当前这个新元素。

def next_greater(nums):
    n = len(nums)
    ans = [-1] * n
    stack = []               # 栈里存下标,值单调递减
    for i in range(n - 1, -1, -1):   # 从右往左扫描
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()      # 比当前元素小的,永远不可能是答案
        if stack:
            ans[i] = nums[stack[-1]]
        stack.append(i)
    return ans

print(next_greater([2, 1, 4, 3]))      # [4, 4, -1, -1]
print(next_greater([1, 3, 2, 5, 4]))   # [3, 5, 5, -1, -1]

为什么弹出的小元素"永远不可能是答案"?因为当前元素 nums[i] 比它们大、又比它们靠左,以后任何查询都会先碰到它。这种"淘汰不可能候选"的思想,是单调栈的灵魂,也是它省时间的原因——每个元素最多入栈出栈一次。

6. 实战四:滑动窗口最大值

最后来个综合应用:数组里有一个长度固定的窗口从左滑到右,求每个窗口的最大值。这题用双端队列维护"候选最大值",队列里存下标,且对应的值从队头到队尾单调递减:队头永远是当前窗口最大值。新元素入队前,先清掉队尾所有比它小的(它们不可能是答案了),再淘汰掉已经滑出窗口的队头下标。

from collections import deque

def max_sliding(nums, k):
    dq = deque()       # 存下标,值单调递减
    ans = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()           # 队尾比 x 小,淘汰
        dq.append(i)
        if dq[0] <= i - k:     # 队头滑出窗口
            dq.popleft()
        if i >= k - 1:         # 窗口成型后才记录
            ans.append(nums[dq[0]])
    return ans

print(max_sliding([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

队列里的下标永远递增,所以判断过期只需看队头:如果队头下标 <= i - k,说明它已经滑出窗口。整个算法每个元素进出队列各一次,总复杂度 O(n),比暴力法快了一个数量级。

7. 总结与练习

这一节把两种结构各自的性格讲清楚了:栈"后进先出",适合处理嵌套与回溯——括号匹配、表达式求值、函数调用都是它;队列"先进先出",适合处理顺序与分层——任务调度、层序遍历都是它。而单调栈和双端队列,则是它们在大数据场景下的"进阶形态",核心都是"维护候选集、淘汰不可能"。

💡 做题时先问自己:这题的数据是"后到先处理"还是"先到先处理"?前者想栈,后者想队列;如果再涉及"找最近更大/更小",就上单调栈。

练习题: