Python 栈：实现 LIFO 数据结构

每当您按下Ctrl+Z撤销错误、点击浏览器的后退按钮，或观看递归函数逐步回退其结果时，您都在依赖栈。由于它们深深嵌入到您日常使用的软件中，您经常在不自觉的情况下与栈打交道。

在本文中，我们将看看什么是栈、栈背后的核心逻辑，比较使用 Python 内置库的不同实现策略，并将它们应用于解决算法问题。

我建议您参加我们关于n Writing Efficient Python Code 的课程，将数据结构知识与性能最佳实践结合起来，并随手备一份 Python Basics Cheat Sheet 以便快速查阅。 

什么是 Python 中的栈？

在看代码之前，理解使 Python 栈如此强大的概念基础非常重要。让我们看看栈背后的核心原理，并了解它与其他常见数据结构有何不同。

LIFO 数据结构

栈是一种遵循“后进先出”（LIFO）原则的线性数据结构。这意味着最近添加的元素总是最先被移除。可以把它想象成自助餐厅里的一摞盘子。您把新盘子放在最上面，拿盘子时也总是先拿最上面的。您不会从中间或底部抽盘子。访问完全受限于顶部。

正是这一条“仅顶部访问”的约束，赋予了栈可预测性和高效性。每个元素都从同一端进出，使操作保持简单且快速。

需要早点说明的一点是，Python 并不像某些其他语言那样提供专用的原生栈类型。没有 stack 关键字或内置类。相反，Python 提供了强大的内置替代方案，例如 lists、collections.deque 和 queue.LifoQueue，它们都可以表现为栈。我们将在本文后面详细介绍这些实现。

栈与其他数据结构的比较

当您了解栈不是什么时，什么是栈就会更加清晰。与栈最常被比较的两种结构是队列和标准 Python 列表。

栈 vs 队列

队列遵循“先进先出”（FIFO）原则，与栈相反。在队列中，元素从尾部加入，从头部移除，就像在售票窗口排队。栈和队列都是线性的，且都限制您访问元素的方式，但它们以相反方向进行。

选错结构可能会悄无声息地破坏算法逻辑。例如，在深度优先搜索中用队列替代栈，会将其变成广度优先搜索，产生完全不同的结果。

栈 vs 列表

另一方面，标准的 Python 列表提供随机访问。您可以使用 my_list[3] 或 my_list.insert(2, value) 等操作在任意索引读取、插入或删除元素。这种灵活性在很多场景很有用，但也意味着没有任何机制能阻止您不小心访问或修改结构中间的元素。

当您在实现依赖严格 LIFO 顺序的算法时（如回溯、语法解析或撤销功能），列表这种不受限的特性可能引入微妙的错误。

这正是为什么栈的受限访问模式是“特性”而不是“限制”。通过只允许与顶部元素交互，Python 栈在设计上就强制了正确性。您不会不小心从错误的一端出队，或覆盖埋在结构深处的元素。

在算法设计中，类似这样的约束有助于让逻辑清晰、代码可预测。

核心栈操作与时间复杂度

现在我们已经了解了什么是 Python 栈以及它与其他结构的区别，接下来看看每个栈都支持的基本操作，并分析各自的效率。

标准栈操作

无论使用哪种编程语言，每种栈实现都基于一小组标准操作。每次使用栈时，您都会用到这些基石。

Push 会在栈顶添加一个元素。如果栈包含 [A, B]，您 push C，则栈变为 [A, B, C]，C 此时位于栈顶。

Pop 会移除并返回当前位于栈顶的元素。延续上例，从 [A, B, C] 弹出返回 C，栈变为 [A, B]。

Peek（有时称为 top）允许您查看栈顶元素而不移除它。当您的逻辑需要在决定是否弹出前检查当前顶部值时，这很有用，这种模式在表达式解析和平衡括号问题中经常出现。

除了这三个核心操作外，还有两个辅助方法对于编写安全、无错的栈代码很重要：

• is_empty() 用于检查栈是否包含任何元素。在空栈上调用 pop 或 peek 是运行时错误的常见来源，因此先检查是否为空是您应尽早养成的防御性编程习惯。

• size() 返回栈中当前元素数量。当您需要跟踪递归深度或还有多少项待处理时，这很有帮助。

最后，值得定义一个您会在教材和面试中遇到的术语：栈下溢（Stack Underflow）。当您尝试从空栈执行 pop 或 peek 时会出现的错误状态。没有可移除或可查看的内容，因此操作无效。

由此产生的具体异常或行为取决于实现。我们将在下一节查看 list、deque 和 LifoQueue 时，具体看看 Python 如何处理它。

复杂度分析

栈在算法中被广泛使用的最大原因之一是其高效性。让我们分解各操作的时间与空间复杂度。

Push 是 O(1)。在高效的栈实现中，将元素添加到顶部是常数时间操作。栈不需要移动或重排任何现有元素，只需把新项放在末尾。这对 collections.deque 以及摊销意义上的 Python 内置 list 都成立。

Pop 是 O(1)。移除顶部元素同样快速。栈直接访问最后一个位置，返回值并递减其内部大小计数器。同样，不需要移动其他元素。

Peek 是 O(1)。在不移除的情况下查看顶部元素是一次直接的索引查找，因此也是常数时间。

Search 是 O(n)。这正是栈揭示其刻意取舍的地方。如果您需要找出某个特定值是否存在于栈中的某处，别无选择，只能从上到下扫描全部 n 个元素。

栈并不是为任意查找而设计的。它牺牲了搜索能力，以换取快速、可预测的 push 和 pop。如果您的用例需要频繁搜索，使用集合或字典等其他数据结构会更合适。

空间复杂度为 O(n)。持有 n 个元素的栈需要与 n 成正比的内存。除了存储元素本身所需外，没有额外的隐藏开销，仅有用于结构内部簿记的小常数。

下面是一个简要总结：

关键结论是：Python 栈针对在一端进行快速插入和删除进行了优化。只要将其用于本职工作（如管理有序的 LIFO 访问），它就能提供出色性能。一旦您发现自己经常在栈中搜索，这就是重新考虑数据结构选择的信号。

Python 栈的实现

在完成理论和复杂度分析之后，是时候编写实际代码了。Python 提供三种主要方式来实现栈，各有优劣。让我们逐一走过，看看如何为我们的用例做出选择。

使用内置 list 的 Python 栈

创建 Python 栈最直接的方法是使用内置的 list。由于列表是支持从末尾添加和移除元素的动态数组，它们与栈行为天然契合。

.append() 方法充当 push，而不带参数的 .pop() 会移除并返回最后一个元素。下面通过代码示例看看：

# Creating a stack using a Python list
stack = []

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)

# Pop the top element
top = stack.pop()
print(top)
print(stack)

# Peek at the top element
print(stack[-1])

[10, 20, 30]
30
[10, 20]
20

这很好用，但您需要谨慎处理空栈情况。在 Python 中，当列表为空时，.pop() 和 stack[-1] 都会抛出 IndexError。这就是 Python 暴露我们之前定义的栈下溢状态的方式。

最佳实践是将这些调用包裹在 try/except 块中，或在访问顶部之前检查是否为空，如下例所示：

# Handling Stack Underflow with try/except
stack = []

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty stack")

try:
    top = stack[-1]
except IndexError:
    print("Stack Underflow: cannot peek at an empty stack")

# Alternatively, check before accessing
if stack:
    top = stack.pop()
else:
    print("Stack is empty")

Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is empty

有一个值得理解的性能细节。Python 列表由动态数组支撑。当您调用 .append() 时，操作通常是瞬时的 O(1)。但是，当内部数组用尽了预分配空间时，Python 必须分配一个更大的内存块并将所有现有元素复制过去。

这种偶发的重新分配使得 .append() 成为摊销 O(1) 而不是严格 O(1)。在实践中，这种延迟很少且很短，但在延迟敏感或实时应用中，这种不可预测性可能很重要。

尽管有此注意事项，列表上的 .append() 和 .pop() 仍是大多数简单栈任务的首选方法。无需导入、语法熟悉、开发者普遍熟悉，使其成为很好的默认选择，尤其适用于脚本、原型和注重简洁的面试问题。

使用 collections.deque 的 Python 栈

如果您需要稳定的 O(1) 性能而不想要偶发的重新分配延迟，推荐使用 collections.deque。名称代表“双端队列”，但它作为高性能的 Python 栈同样合适。我们之前的示例用 deque 语法如下：

from collections import deque

# Creating a stack using deque
stack = deque()

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) 

# Pop the top element
top = stack.pop()
print(top)
print(stack)
 
# Peek at the top element
print(stack[-1])

deque([10, 20, 30])
30
deque([10, 20])
20

请注意，其接口与基于列表的方法完全相同。.append()、.pop() 和 [-1] 的用法一致。空访问时的 IndexError 行为也未改变，因此您的错误处理代码无需任何修改：

from collections import deque

stack = deque()

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty deque stack")

Stack Underflow: cannot pop from an empty deque stack

关键差异在于底层实现。deque 实现为固定大小块组成的双向链表，而非单个数组。这意味着它在增长时不需要重新分配并复制整个结构。

每一次 .append() 和 .pop() 都是真正、保证的 O(1) 操作，不是摊销，而是稳定一致。对于需要成千上万、数百万次 push 和 pop 的算法密集型工作，这种一致性优势会被放大。

使用 queue.LifoQueue 的 Python 栈

Python 标准库还包含 queue.LifoQueue，这是一种专为多线程程序设计的栈实现。名称中的 “LIFO” 表明它遵循后进先出顺序，但其接口和行为与前两种方法有相当不同。看如下代码示例：

from queue import LifoQueue

# Creating a thread-safe stack
stack = LifoQueue()

# Push elements using .put()
stack.put(10)
stack.put(20)
stack.put(30)
print(stack.qsize())

# Pop the top element using .get()
top = stack.get()
print(top)
print(stack.qsize())

3
30
2

首先要注意语法变化。Push 变为 .put()，pop 变为 .get()。这种命名来自 queue 模块的生产者-消费者设计模式，其中一个线程“放入（put）”项，另一个线程“获取（get）”项。

有两点重要的行为差异需要注意。

其一，LifoQueue 没有安全的 peek 方法。没有内置方式在不移除元素的情况下查看栈顶。您可以访问内部属性，但在多线程环境中这样做会违背使用线程安全类的初衷，并带来竞争风险。

其二，当您尝试从空栈获取元素时，LifoQueue 不会抛出 IndexError。默认情况下，.get() 会阻塞。它会暂停调用线程并无限期等待，直到另一个线程向栈中放入项。如果您希望非阻塞行为，可以传入 block=False，此时会改为抛出 queue.Empty 异常。如下示例：

from queue import LifoQueue, Empty

stack = LifoQueue()

# Non-blocking get raises Empty, not IndexError
try:
    stack.get(block=False)
except Empty:
    print("Stack is empty — no items to get")

Stack is empty — no items to get

由于使 LifoQueue 线程安全的内部加锁机制，其操作比 list 或 deque 开销更大。这使它在单线程代码中表现不佳。仅当您有多线程并发生产与消费数据的场景时才使用 LifoQueue，其他情况下请选择 deque 或 list。

选择合适的 Python 栈实现

有三种选项可用，下面是并排对比，帮助您做出决策：

以下是我用来选择最佳实现的决策框架：

• 当您需要无需导入的快速栈（如脚本、笔记本和面试白板）时使用 list。

• 当您在编写算法代码、处理大型数据集或构建任何对性能敏感的内容时使用 collections.deque。

• 仅在存在天然多线程并发访问场景时使用 queue.LifoQueue。

您可能也会看到一些教程使用自定义链表类从零实现 Python 栈，其中每个节点保存一个值和指向下方节点的指针。在我看来，这确实是非常有价值的学习练习，能加深您对栈内部工作原理以及内存引用如何串联的理解。

不过，在生产级 Python 代码中，由于创建单个节点对象的开销，基于链表的栈几乎总是比 deque 慢。对于真实的 Python 工作，collections.deque 在速度、清晰度与可靠性之间提供了最佳组合。

Python 栈的应用

理解如何实现 Python 栈只是成功的一半。当您看到它们解决在没有 LIFO 顺序时会复杂得多的问题时，栈的真正价值才会显现。让我们看看在编程面试、软件系统和算法设计中经常出现的三个经典应用。

检查括号是否匹配

平衡括号问题是技术面试中最常被问及的栈问题之一。给定包含括号（如 ()、[] 和 {}）的字符串，您需要判断每个左括号是否都有按正确顺序对应的右括号。

这套逻辑与栈完美契合。从左到右扫描字符串，遇到左括号就推入栈中。遇到右括号时，弹出栈顶并检查是否匹配。

如果在尝试弹出时栈为空，或弹出的括号不匹配，则字符串不平衡。处理完整个字符串后，栈应为空。任何剩余的左括号都意味着有未闭合的内容。下面看看示例：

from collections import deque

def is_balanced(expression):
    stack = deque()
    matching = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack:
                return False  # closing bracket with nothing to match
            if stack.pop() != matching[char]:
                return False  # mismatched pair
    
    return len(stack) == 0  # stack should be empty if balanced

# Test cases
print(is_balanced("([])")) 
print(is_balanced("{[()]}"))
print(is_balanced("([)]"))
print(is_balanced("(("))
print(is_balanced(""))

True
True
False
False
True

让我们逐步跟踪 "{[()]}"，看看栈如何发挥作用：

最后栈为空，因此该表达式是平衡的。

同样的逻辑远不止用于面试题。编译器和解释器使用它来验证语法，确保源代码中的每个起始标签、括号或分隔符都有正确的匹配。

如果您曾见过 Python 的 SyntaxError: unexpected EOF 消息，那就是此类检查的一种体现。HTML 校验器、JSON 解析器，甚至配置文件的 linter 都依赖这种基于栈的方法变体。

实现深度优先搜索（DFS）

深度优先搜索是基础的图遍历算法之一，而栈正是驱动它的数据结构。思想很简单：从一个结点开始，沿着一条分支尽可能深入，再回溯尝试下一条。Python 栈的 LIFO 特性使这种“先深后广”的行为自然而然地发生。

大多数入门课程用递归教授 DFS，此时调用栈隐式地管理遍历顺序。但递归方法有实际限制。Python 的默认递归深度为 1000 帧。

对于大型或嵌套很深的图，这会导致 RecursionError。使用显式栈的迭代版本可以避免该问题，并让您完全控制遍历过程。

让我们看一个代码示例。我们将对下图进行 DFS：

from collections import deque

def dfs_iterative(graph, start):
    visited = set()
    stack = deque()
    stack.append(start)
    traversal_order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            # Push neighbors onto the stack
            # Reverse to maintain left-to-right order after LIFO popping
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return traversal_order

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(dfs_iterative(graph, 'A'))

['A', 'B', 'D', 'E', 'F', 'C']

让我们跟踪执行，看看栈如何支配遍历：

请注意，LIFO 顺序迫使算法在回溯访问 C 之前，彻底探索 A → B → D 和 A → B → E → F 两条分支。这正是深度优先搜索与广度优先搜索（使用队列、先遍历当前深度所有邻居）之间的区别。

这里展示的迭代 DFS 模式适用于树、有向图和无向图。它还是更高级算法（如拓扑排序、环检测、迷宫与拼图求解）的基础。

管理撤销/重做操作

如果您使用过文本编辑器、绘图应用或电子表格，您很可能在不经意间依赖了撤销与重做。其机制很优雅，正是由两组栈驱动。

撤销栈在用户进行更改时存储每个动作或状态。用户触发撤销时，当前状态从撤销栈弹出并推入重做栈。

若用户随后触发重做，则状态从重做栈弹出并推回撤销栈。若用户在撤销后进行全新更改，则清空重做栈。您无法重做已经被新操作覆盖的内容。下面看一个代码示例：

from collections import deque

class TextEditor:
    def __init__(self):
        self.content = ""
        self.undo_stack = deque()
        self.redo_stack = deque()

    def type_text(self, text):
        """Record current state and apply new text."""
        self.undo_stack.append(self.content)
        self.content += text
        self.redo_stack.clear()  # new action invalidates redo history

    def undo(self):
        """Revert to the previous state."""
        if not self.undo_stack:
            print("Nothing to undo")
            return
        self.redo_stack.append(self.content)
        self.content = self.undo_stack.pop()

    def redo(self):
        """Re-apply the last undone action."""
        if not self.redo_stack:
            print("Nothing to redo")
            return
        self.undo_stack.append(self.content)
        self.content = self.redo_stack.pop()

    def show(self):
        print(f'Content: "{self.content}"')

# Demonstrate the undo/redo flow
editor = TextEditor()
editor.type_text("Hello")
editor.show()                

editor.type_text(" World")
editor.show()                

editor.type_text("!")
editor.show()              

editor.undo()
editor.show()           

editor.undo()
editor.show()           

editor.redo()
editor.show()

editor.type_text(" Python")
editor.show()         

editor.redo()  

Content: "Hello"
Content: "Hello World"
Content: "Hello World!"
Content: "Hello World"
Content: "Hello"
Content: "Hello World"
Content: "Hello World Python"
Nothing to redo

两个栈之间的状态流转遵循清晰的模式：

这种双栈模式并不限于文本编辑器。任何需要在一系列更改中前后移动的场景（几乎无处不在）都会用到它：

• 图像编辑软件
• 数据库事务回滚
• 游戏状态管理

底层原理始终相同：一个 Python 栈跟踪历史，另一个跟踪未来，LIFO 顺序确保您总是优先回到最近的状态。

Python 栈的进阶概念

栈还在您运行的每个 Python 程序的幕后扮演重要角色，并为某些问题提供能显著降低时间复杂度的优化技术。让我们看看这两个高级层面。

理解调用栈

每当您在 Python 中调用一个函数，幕后都会发生您无法直接控制的事情。Python 会将一个新帧压入称为调用栈的内部数据结构中。该帧保存函数的局部变量、参数以及返回到发起调用的那行代码的指针。

当函数执行完毕，其帧会从调用栈弹出，控制权返回给调用方。

您可以使用一个简单示例来观察这种行为：

def function_c():
    print("Inside function_c")
    # At this point, the call stack holds:
    # [main → function_a → function_b → function_c]  (top)

def function_b():
    print("Inside function_b")
    function_c()

def function_a():
    print("Inside function_a")
    function_b()

function_a()

Inside function_a
Inside function_b
Inside function_c

当 function_c 执行时，调用栈上叠着四个帧。随着每个函数完成，其帧会按 LIFO 顺序弹出。function_c 先结束，然后是 function_b、function_a，最后是主模块作用域。

这正是让递归得以工作的机制。每次递归调用都会压入一个包含自己局部变量的新帧，并在帧被弹出时回退结果。如下示例：

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

# Call stack at deepest point:
# factorial(1)  ← top (returns 1)
# factorial(2)  ← waiting for factorial(1)
# factorial(3)  ← waiting for factorial(2)
# factorial(4)  ← waiting for factorial(3)
# factorial(5)  ← waiting for factorial(4)

120

当递归过深时会出现问题。Python 设定了默认 1000 帧的递归限制，以防调用栈耗尽所有可用内存。如果您的递归函数超过此限制，Python 会抛出 RecursionError。如下示例：

def infinite_recursion(n):
    return infinite_recursion(n + 1)

try:
    infinite_recursion(0)
except RecursionError:
    print("RecursionError: maximum recursion depth exceeded")

RecursionError: maximum recursion depth exceeded

您可以使用 sys 模块检查并修改该限制，但提高时应谨慎：

import sys

print(sys.getrecursionlimit())  
sys.setrecursionlimit(5000)     # Increase with caution

5000

需要牢记的重要区别是，调用栈是由 Python 解释器自身管理的系统级结构。您无法直接向其 push 或 pop。我们在前面部分构建的 list、deque 和 LifoQueue 栈是用户定义的数据结构，存在于程序的堆内存中。它们用途不同，但都遵循相同的 LIFO 原则。

使用单调栈

单调栈是一种特殊变体，其中元素保持非递减或非递增顺序（有时是严格增/减，取决于问题）。每当您压入新元素时，先弹出所有会破坏该有序约束的元素。它是以线性时间解决一整类优化问题的关键。

经典例子是“下一个更大元素”问题：给定一个整数数组，为每个元素找出其右侧第一个比它大的元素。用双重循环的暴力方法是 O(n²)：对于每个元素，扫描其右侧所有元素。单调栈可以把它降为 O(n)。

关键洞见是从右向左遍历数组，维护一个递减栈。对于每个元素，弹出所有小于或等于它的栈内元素。这些值不可能再成为左侧某个未来元素的“下一个更大元素”。

弹出后栈顶剩下的就是当前元素的答案。然后将当前元素压入栈。让我们通过代码看看。注意此处 -1 表示该数字右侧不存在更大的元素：

from collections import deque

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # default: no greater element found
    stack = deque()     # monotonic decreasing stack (stores values)

    # Traverse from right to left
    for i in range(n - 1, -1, -1):
        # Pop elements that are not greater than current
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        
        # If stack is not empty, top is the next greater element
        if stack:
            result[i] = stack[-1]
        
        # Push current element onto the stack
        stack.append(nums[i])

    return result

nums = [4, 5, 2, 25, 7, 18]
print(next_greater_element(nums))

[5, 25, 25, -1, 18, -1]

让我们跟踪执行，看看如何维护单调性：

请注意，每个元素仅被压入一次、最多被弹出一次。这就是尽管有内层 while 循环，整体时间复杂度仍为 O(n) 的原因：跨所有迭代的 push 与 pop 总次数不超过 2n。

正如我之前提到的，还有许多类似问题可用单调栈将复杂度从 O(n²) 降至 O(n)，包括：

• 股票跨度问题：对每一天的价格，找出前面连续小于或等于该价的天数。
• 柱状图中的最大矩形：求能容纳在柱状图下方的最大矩形面积（经典高难度面试题）。
• 每日温度：给定每日温度数组，找出需要等待多少天才能遇到更高温度。
• 接雨水：计算不同高度的柱子之间能接住多少雨水。

在每种情况下，核心思想相同：单调性约束让您丢弃不再可能影响未来结果的元素，从而将搜索空间从二次削减为线性。

结语

栈是每位程序员最先学习的 数据结构之一，也是他们很久都不断发现新用法的数据结构之一，这与其“后进先出”的本性恰成反比。

在本文中，我们看到 LIFO 约束如何在多种场景下发挥作用：从验证嵌套括号、驱动深度优先遍历，到管理撤销/重做状态，再到用单调栈优化数组问题。

如果要带走一条建议，那就是：除非有特定原因，请将 collections.deque 作为您实现 Python 栈的首选方案。

下一步，我建议参加我们关于的课程 Data Structures and Algorithms in Python。