栈和队列详解：用 Python 示例讲清 LIFO 与 FIFO

栈和队列解决什么问题

许多程序需要先记住一些元素，之后再按固定顺序处理。栈先给出最近加入的元素，适合嵌套式的工作：函数调用、撤销历史、括号匹配和深度优先搜索。队列先给出最早加入的元素，适合公平的等待：打印任务、任务调度器、消息队列和广度优先搜索。

两者都是抽象数据类型：它们由操作定义，而不是由存储方式定义。你可以基于数组或链表来实现其中任何一个。

操作与名称

示例演练：逐步 push 和 pop

把 1、2、3 依次放入两种结构，然后移除两个元素。

Python 实现

Python 的 list 本身就是个不错的栈：append 和 pop() 都作用于列表末尾，均摊时间为 O(1)。做队列时不要用 list.pop(0)，因为它会移动所有剩余元素，代价是 O(n)。请使用 collections.deque，它在两端都是 O(1)。

from collections import deque
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop(), stack[-1])   # 3 2
queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft(), queue[0])  # a b
print(len(stack), len(queue))     # 2 2

如果想要有名字的方法和清晰的报错，可以用一个小类把内置类型包装起来：

from collections import deque
class Queue:
    def __init__(self):
        self._items = deque()
    def enqueue(self, item):
        self._items.append(item)
    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()
    def __len__(self):
        return len(self._items)
q = Queue()
q.enqueue("job1")
q.enqueue("job2")
print(q.dequeue(), len(q))  # job1 1

经典栈问题：括号匹配

要检查每个括号是否按正确顺序闭合，就把每个左括号压入栈。遇到右括号时，栈顶必须是与之匹配的左括号。

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
print(is_balanced("f(a[1], {b: 2})"))  # True
print(is_balanced("(]"))               # False
print(is_balanced("(("))               # False

同样的思路还能用来计算逆波兰表达式、把递归改写成循环，以及实现深度优先搜索：用你自己的列表代替调用栈。

经典队列问题：广度优先搜索

广度优先搜索按层访问图。队列恰好能做到这一点：先发现的节点先处理。

from collections import deque
def bfs_order(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs_order(graph, "A"))  # ['A', 'B', 'C', 'D']

时间与空间复杂度

均摊的意思是：偶尔一次 append 会重新分配底层数组，代价为 O(n)，但在大量操作上取平均，每次操作都是 O(1)。

变体与常见错误

• 双端队列（deque）：两端都能添加和移除。collections.deque 就是其中一种，它既可以当栈用，也可以当队列用。
• 优先队列：先移除最小（或最大）的元素，而不是最早的。使用 heapq；参见二叉堆页面。
• 循环缓冲区：用数组存储、下标回绕的定长队列。deque(maxlen=n) 在满时会丢弃最旧的元素。
• 线程安全队列：queue.Queue 用于线程，asyncio.Queue 用于协程，它们在等待元素时会阻塞。
• 用两个栈实现队列：向入栈压入元素，当出栈为空时把所有元素倒过去。每个元素只移动一次，所以操作是均摊 O(1)。