栈（Stack）

后进先出的数据结构与经典应用

一、栈的概述

栈（Stack） 是一种具有后进先出（Last In, First Out, LIFO）特性的线性数据结构。它只允许在数据集合的一端（称为栈顶，Top）进行插入和删除操作，另一端称为栈底（Bottom）。这种受限的访问方式使得栈成为计算机科学中最为基础且应用广泛的数据结构之一。

核心特性

LIFO 原则： 最后进入栈的元素最先被取出，就像一叠盘子——你总是先拿到最上面那个
操作受限： 只能在一端（栈顶）进行插入和删除，不允许随机访问中间元素
线性结构： 元素之间存在前后顺序关系，每个元素最多有一个直接前驱和一个直接后继

生活中的栈类比

一叠盘子： 洗完的盘子叠在一起，取用时总是从最上面拿
浏览器的后退按钮： 你访问页面 A -> B -> C，点击后退时回到 B，再点击回到 A
编辑器的撤销操作： 每次操作都被压入"操作栈"，撤销时弹出最近的操作
嵌套函数调用： 函数 A 调用函数 B，B 调用 C，C 返回后回到 B，B 返回后回到 A

为什么学习栈？

栈是理解计算机系统运行机制的关键。从 CPU 的函数调用栈到浏览器的前进后退，从编译器的语法解析到算法中的括号匹配，栈的应用贯穿于整个计算机科学领域。掌握栈的原理和实现，是每一位程序员的基本功。

二、栈的核心操作

栈的定义了一组标准的操作接口，任何栈的实现都应该支持以下核心操作：

操作列表

push(item) — 入栈： 将一个元素添加到栈顶
pop() — 出栈： 移除并返回栈顶元素；如果栈为空，则抛出异常（栈下溢）
peek() / top() — 查看栈顶： 返回栈顶元素但不移除；如果栈为空，则抛出异常
is_empty() — 判空： 检查栈中是否为空，返回布尔值
size() — 大小： 返回栈中元素的个数

栈的抽象数据类型（ADT）定义

class StackADT:
    """栈的抽象数据类型定义"""

    def push(self, item):
        """将 item 压入栈顶"""
        raise NotImplementedError

    def pop(self):
        """移除并返回栈顶元素，栈空时抛出异常"""
        raise NotImplementedError

    def peek(self):
        """返回栈顶元素但不移除，栈空时抛出异常"""
        raise NotImplementedError

    def is_empty(self):
        """检查栈是否为空"""
        raise NotImplementedError

    def size(self):
        """返回栈中元素个数"""
        raise NotImplementedError

三、Python 实现栈的多种方式

Python 提供了非常灵活的方式来实现栈。下面将介绍三种主流的实现方式，每种方式有其适用场景和优劣势。

3.1 使用列表（List）实现栈

Python 的 list 类型是动态数组，本身就提供了 append() 和 pop() 方法，可以天然地模拟栈的操作。append() 在列表末尾添加元素对应 push，pop() 从列表末尾移除元素对应 pop。

# 使用 Python 内置 list 实现栈
stack = []

# push 操作
stack.append(1)
stack.append(2)
stack.append(3)

# pop 操作
top = stack.pop()       # 返回 3
print(top)              # 输出: 3

# peek 操作（查看栈顶）
if stack:
    peek = stack[-1]    # 返回 2
    print(peek)         # 输出: 2

# is_empty 操作
print(len(stack) == 0)  # 输出: False

# size 操作
print(len(stack))       # 输出: 2

List 实现栈的优缺点

优点： 实现简单直接，性能优秀（append 和 pop 均为 O(1) 均摊时间复杂度）
缺点： 动态数组在扩容时有性能开销（但均摊后仍为 O(1)）；不是线程安全的
适用场景： 单线程环境下的通用栈操作，日常算法题解

3.2 使用 collections.deque 实现栈

collections.deque（双端队列）在两端都支持 O(1) 的插入和删除操作。使用 append() 和 pop() 方法同样可以充当栈，并且在频繁操作时性能优于 list。

from collections import deque

# 使用 deque 实现栈
stack = deque()

# push 操作
stack.append(10)
stack.append(20)
stack.append(30)

# pop 操作
top = stack.pop()       # 返回 30
print(top)              # 输出: 30

# peek
print(stack[-1])        # 输出: 20

# is_empty
print(len(stack) == 0)  # 输出: False

# size
print(len(stack))       # 输出: 2

Deque 实现栈的优缺点

优点： 两端操作均为 O(1)，没有 list 的扩容开销；性能稳定
缺点： 需要额外导入 deque；对于单线程纯栈场景，list 的可读性更好
适用场景： 需要稳定性能的生产环境代码，频繁的 push/pop 操作

3.3 自定义栈类（完整封装）

实际工程中，将栈封装为独立的类是最佳实践。这样可以提供清晰的接口、添加类型提示、实现自定义方法，也便于维护和扩展。

from typing import Generic, TypeVar, List

T = TypeVar('T')

class Stack(Generic[T]):
    """泛型栈实现，支持任意类型元素"""

    def __init__(self):
        """初始化空栈"""
        self._items: List[T] = []

    def push(self, item: T) -> None:
        """将元素压入栈顶"""
        self._items.append(item)

    def pop(self) -> T:
        """弹出并返回栈顶元素"""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self) -> T:
        """返回栈顶元素但不移除"""
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._items[-1]

    def is_empty(self) -> bool:
        """检查栈是否为空"""
        return len(self._items) == 0

    def size(self) -> int:
        """返回栈中元素个数"""
        return len(self._items)

    def __str__(self) -> str:
        """返回栈的字符串表示（栈顶在右侧）"""
        return f"Stack({self._items})"

    def __len__(self) -> int:
        """支持 len() 函数"""
        return self.size()


# 使用示例
if __name__ == "__main__":
    s = Stack[int]()
    s.push(1)
    s.push(2)
    s.push(3)
    print(s)           # Stack([1, 2, 3])
    print(s.pop())     # 3
    print(s.peek())    # 2
    print(len(s))      # 2
    print(s.is_empty())# False

3.4 使用链表实现栈

除了基于数组的实现，还可以使用链表（LinkedList）来实现栈。这种方式没有容量限制，push 和 pop 操作始终为 O(1)。

class ListNode:
    """链表节点"""
    def __init__(self, val):
        self.val = val
        self.next = None


class LinkedListStack:
    """基于链表的栈实现"""

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

    def push(self, item):
        """将元素压入栈顶（头插法）"""
        new_node = ListNode(item)
        new_node.next = self._top
        self._top = new_node
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        val = self._top.val
        self._top = self._top.next
        self._size -= 1
        return val

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

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

    def size(self):
        return self._size

四、时间复杂度分析

对比不同栈实现方式的时间复杂度和空间复杂度：

复杂度对照表

基于数组的栈（List / Deque）：
- push: O(1) 均摊（list 扩容时为 O(n)，但均摊后为 O(1)）
- pop: O(1)
- peek: O(1)
- is_empty / size: O(1)
- 空间复杂度: O(n)，但可能预留额外容量
基于链表的栈：
- push: O(1)（头插法）
- pop: O(1)
- peek: O(1)
- 空间复杂度: O(n)，每个节点需要额外存储指针的开销

从整体上看，两种实现的核心操作都是 O(1)，非常高效。数组实现的缓存局部性更好（内存连续），实际运行速度更快；链表实现则没有容量上限限制。

五、栈的经典应用

栈是计算机科学中应用最为广泛的基础数据结构之一，几乎渗透到了每一个软件系统的运行过程中。下面通过具体的代码示例来深入理解栈的经典应用场景。

5.1 括号匹配

括号匹配是栈最经典的应用之一。编译器在解析代码时，使用栈来检查括号是否匹配。算法思路：遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶是否是对应的左括号。

def is_valid_parentheses(s: str) -> bool:
    """
    验证括号字符串是否有效。

    有效规则：
    - 左括号必须由同类型的右括号闭合
    - 左括号必须以正确的顺序闭合

    示例：
    >>> is_valid_parentheses("()[]{}")   -> True
    >>> is_valid_parentheses("([)]")     -> False
    >>> is_valid_parentheses("{[]}")     -> True
    """
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in mapping:  # 右括号
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:                  # 左括号
            stack.append(char)

    return len(stack) == 0


# 测试
test_cases = ["()", "()[]{}", "(]", "([)]", "{[]}", ""]
for case in test_cases:
    result = is_valid_parentheses(case)
    print(f"'{case}' -> {result}")

# 输出:
# '()' -> True
# '()[]{}' -> True
# '(]' -> False
# '([)]' -> False
# '{[]}' -> True
# '' -> True

应用场景

代码编辑器/IDE 中的语法高亮和错误检测
编译器前端语法分析阶段的括号匹配
XML/HTML 标签嵌套的合法性检查
JSON 解析中的花括号匹配

5.2 表达式求值（中缀转后缀）

中缀表达式（如 3 + 4 * 2 / (1 - 5)）是人类习惯的写法，但计算机计算时通常使用后缀表达式（逆波兰表示法）。将中缀表达式转换为后缀表达式的经典算法——调度场算法（Shunting-yard algorithm）——就依赖栈来实现。

def infix_to_postfix(expression: str) -> str:
    """
    将中缀表达式转换为后缀表达式（逆波兰表示法）
    使用调度场算法（Shunting-yard algorithm）

    示例：
    >>> infix_to_postfix("3 + 4 * 2 / ( 1 - 5 )")
    "3 4 2 * 1 5 - / +"
    """
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    output = []
    op_stack = []

    tokens = expression.split()

    for token in tokens:
        if token.isdigit():
            output.append(token)
        elif token in precedence:
            while (op_stack and op_stack[-1] != '('
                   and precedence[op_stack[-1]] >= precedence[token]):
                output.append(op_stack.pop())
            op_stack.append(token)
        elif token == '(':
            op_stack.append(token)
        elif token == ')':
            while op_stack and op_stack[-1] != '(':
                output.append(op_stack.pop())
            op_stack.pop()  # 移除 '('

    while op_stack:
        output.append(op_stack.pop())

    return ' '.join(output)


# 测试
expr = "3 + 4 * 2 / ( 1 - 5 )"
print(f"中缀: {expr}")
print(f"后缀: {infix_to_postfix(expr)}")

# 输出:
# 中缀: 3 + 4 * 2 / ( 1 - 5 )
# 后缀: 3 4 2 * 1 5 - / +

5.3 逆波兰表达式（RPN）计算

逆波兰表达式（Reverse Polish Notation，RPN）将运算符放在操作数之后，计算时使用栈非常方便：遇到数字入栈，遇到运算符则弹出两个操作数计算后将结果入栈。

def eval_rpn(tokens: list) -> int:
    """
    计算逆波兰表达式的值。

    示例：
    >>> eval_rpn(["2", "1", "+", "3", "*"])
    9  (等价于 (2 + 1) * 3)
    """
    stack = []

    for token in tokens:
        if token in {'+', '-', '*', '/'}:
            b = stack.pop()  # 第二个操作数
            a = stack.pop()  # 第一个操作数
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(int(a / b))  # 整数除法向零截断
        else:
            stack.append(int(token))

    return stack[0]


# 测试
rpn_expr = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
# 等价于: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22
print(eval_rpn(rpn_expr))  # 输出: 22

# 简单例子: 3 4 + 5 *  = (3 + 4) * 5 = 35
print(eval_rpn(["3", "4", "+", "5", "*"]))  # 输出: 35

5.4 函数调用栈

编程语言中的函数调用机制本质就是一个栈结构。每当一个函数被调用，系统会在调用栈上压入一个"栈帧"（Stack Frame），包含函数的局部变量、参数和返回地址。函数执行完毕，对应的栈帧被弹出。

# 模拟函数调用栈
def func_a():
    print("Enter func_a")
    func_b()
    print("Exit func_a")

def func_b():
    print("  Enter func_b")
    func_c()
    print("  Exit func_b")

def func_c():
    print("    Enter func_c")
    print("    Doing work in func_c")
    print("    Exit func_c")

func_a()

# 调用栈变化:
# 1. |         |    2. |         |    3. |         |    4. |         |
#    |  main   |       | func_a   |       | func_b   |       | func_c   |
#    |_________|       |_________|       |_________|       |_________|
#
# 调用序列: main -> func_a -> func_b -> func_c
# 返回序列: func_c -> func_b -> func_a -> main
#
# 输出:
# Enter func_a
#   Enter func_b
#     Enter func_c
#     Doing work in func_c
#     Exit func_c
#   Exit func_b
# Exit func_a

深入理解函数调用栈

栈帧（Stack Frame）： 每个函数调用都会创建一个栈帧，包含局部变量、参数、返回地址等
调用约定（Calling Convention）： 决定了参数如何传递、栈如何清理等细节
栈溢出（Stack Overflow）： 当递归调用过深或无限递归时，调用栈会耗尽内存空间导致溢出
尾递归优化： 某些语言（如 Scheme、Haskell）对尾递归进行优化，复用当前栈帧避免栈溢出

5.5 浏览器的前进后退

浏览器使用"后退栈"（Back Stack）和"前进栈"（Forward Stack）两个栈来实现页面的前进和后退功能。每次访问新页面时，将当前页面压入后退栈并清空前栈栈。

class BrowserHistory:
    """使用双栈模拟浏览器的前进后退功能"""

    def __init__(self, homepage: str):
        self.back_stack = [homepage]   # 后退栈
        self.forward_stack = []         # 前进栈

    def visit(self, url: str) -> None:
        """访问新页面"""
        self.back_stack.append(url)
        self.forward_stack.clear()     # 访问新页面后清空前栈栈
        print(f"访问: {url}")

    def back(self, steps: int = 1) -> str:
        """后退 steps 步"""
        while steps > 0 and len(self.back_stack) > 1:
            page = self.back_stack.pop()
            self.forward_stack.append(page)
            steps -= 1
        current = self.back_stack[-1]
        print(f"后退到: {current}")
        return current

    def forward(self, steps: int = 1) -> str:
        """前进 steps 步"""
        while steps > 0 and self.forward_stack:
            page = self.forward_stack.pop()
            self.back_stack.append(page)
            steps -= 1
        current = self.back_stack[-1]
        print(f"前进到: {current}")
        return current

    def current(self) -> str:
        return self.back_stack[-1]


# 使用示例
browser = BrowserHistory("https://www.google.com")
browser.visit("https://github.com")
browser.visit("https://leetcode.com")
browser.visit("https://stackoverflow.com")

browser.back(2)       # 回到 github.com
browser.forward(1)    # 回到 leetcode.com
browser.visit("https://python.org")  # 访问新页面，清空前栈栈

print(f"当前页面: {browser.current()}")  # python.org

5.6 撤销操作（Undo/Redo）

文本编辑器、图像处理软件等应用程序使用"撤销栈"（Undo Stack）和"重做栈"（Redo Stack）来实现操作的撤销和重做。

class TextEditor:
    """使用双栈实现文本编辑器的撤销/重做功能"""

    def __init__(self):
        self.content = ""
        self.undo_stack = []    # 保存历史状态
        self.redo_stack = []    # 保存撤销的状态

    def type(self, text: str) -> None:
        """输入文本"""
        self.undo_stack.append(self.content)
        self.content += text
        self.redo_stack.clear()  # 新操作清空重做栈
        print(f"输入: '{text}' -> '{self.content}'")

    def undo(self) -> None:
        """撤销上一次操作"""
        if not self.undo_stack:
            print("无可撤销的操作")
            return
        self.redo_stack.append(self.content)
        self.content = self.undo_stack.pop()
        print(f"撤销 -> '{self.content}'")

    def redo(self) -> None:
        """重做上一次撤销的操作"""
        if not self.redo_stack:
            print("无可重做的操作")
            return
        self.undo_stack.append(self.content)
        self.content = self.redo_stack.pop()
        print(f"重做 -> '{self.content}'")


# 使用示例
editor = TextEditor()
editor.type("Hello")          # Hello
editor.type(" World")        # Hello World
editor.type("!")             # Hello World!
editor.undo()                     # Hello World
editor.undo()                     # Hello
editor.redo()                     # Hello World
editor.type(" Python")       # Hello World Python
# 此时 redo_stack 被清空，之前撤销的 "!" 丢失

双栈模式总结

浏览器的前进后退和编辑器的撤销重做都使用了"双栈"架构：一个栈记录历史，另一个栈记录"被撤销的历史"。关键点在于当用户执行新操作时，"前进栈"或"重做栈"必须被清空，因为新操作打断了历史分支。

六、单调栈（Monotonic Stack）

单调栈是栈的一种高级应用形式，其特点是栈内元素保持单调递增或单调递减的顺序。单调栈通常用于解决"下一个更大元素"、"每日温度"、"接雨水"等经典面试题。

6.1 单调栈的定义

单调栈分为两种：

单调递增栈： 从栈底到栈顶元素值递增（即栈顶最小），用于寻找左侧或右侧第一个更小的元素
单调递减栈： 从栈底到栈顶元素值递减（即栈顶最大），用于寻找左侧或右侧第一个更大的元素

6.2 经典问题：Next Greater Element（下一个更大元素）

给定一个数组，返回每个元素右边第一个比它大的元素，不存在则为 -1。这是单调栈最经典的入门题，LeetCode 496 题。

def next_greater_element(nums: list) -> list:
    """
    计算每个元素右边第一个更大的元素

    示例：
    >>> nums = [2, 1, 5, 3, 4]
    >>> next_greater_element(nums)
    [5, 5, -1, 4, -1]

    解释：
    - 2 右边第一个比 2 大的是 5
    - 1 右边第一个比 1 大的是 5
    - 5 右边没有更大的元素，返回 -1
    - 3 右边第一个比 3 大的是 4
    - 4 右边没有更大的元素，返回 -1
    """
    n = len(nums)
    result = [-1] * n
    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


# 测试
print(next_greater_element([2, 1, 5, 3, 4]))  # [5, 5, -1, 4, -1]
print(next_greater_element([1, 2, 3, 4, 5]))  # [2, 3, 4, 5, -1]
print(next_greater_element([5, 4, 3, 2, 1]))  # [-1, -1, -1, -1, -1]

单调栈的核心思想

单调栈的巧妙之处在于：栈中保存的是尚未找到"下一个更大元素"的索引。当遇到一个新元素时，它可能成为栈中某些元素的"下一个更大元素"，于是将它们一一弹出并记录结果。这样每个元素最多入栈一次、出栈一次，时间复杂度为 O(n)。

6.3 每日温度问题

给定一个温度列表，返回需要等多少天才会出现更高的温度。LeetCode 739 题。

def daily_temperatures(temperatures: list) -> list:
    """
    计算需要等待的天数直到出现更高的温度

    示例：
    >>> temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
    >>> daily_temperatures(temperatures)
    [1, 1, 4, 2, 1, 1, 0, 0]
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # 单调递减栈，存储索引

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)

    return result


# 测试
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]

# 解释:
# 第0天73° -> 第1天74°  (等1天)
# 第1天74° -> 第2天75°  (等1天)
# 第2天75° -> 第6天76°  (等4天)
# 第3天71° -> 第5天72°  (等2天)
# 第4天69° -> 第5天72°  (等1天)
# 第5天72° -> 第6天76°  (等1天)
# 第6天76° -> 没有更高   (等0天)
# 第7天73° -> 没有更高   (等0天)

6.4 接雨水问题

接雨水（Trapping Rain Water）是 LeetCode 42 题，也是单调栈的经典难题。给定一个柱状图高度数组，计算这些柱子能够接住多少雨水。

def trap_rain_water(height: list) -> int:
    """
    使用单调栈计算能接的雨水量

    示例：
    >>> height = [0,1,0,2,1,0,1,3,2,1,2,1]
    >>> trap_rain_water(height)
    6
    """
    stack = []         # 单调递减栈，存储索引
    total_water = 0
    n = len(height)

    for i in range(n):
        while stack and height[i] > height[stack[-1]]:
            # 弹出栈顶（"凹槽"的底部）
            bottom_idx = stack.pop()
            if not stack:
                break   # 左侧没有墙，无法蓄水

            left_idx = stack[-1]
            width = i - left_idx - 1
            bounded_height = min(height[left_idx], height[i]) - height[bottom_idx]
            total_water += width * bounded_height

        stack.append(i)

    return total_water


# 测试
print(trap_rain_water([0,1,0,2,1,0,1,3,2,1,2,1]))  # 6

# 可视化：
#              █
#      █~~~~~~~█~█~~~~█
#  █~~~█~█~~~█~████████████
#  ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
#  ~ 表示积水 (共6个单位)

单调栈核心要点

单调栈使原本嵌套循环 O(n^2) 的问题优化为线性时间 O(n)
核心思想是"延迟处理"——元素入栈时还不知道答案，等后续更大的元素出现时才出栈并记录
单调递增栈用于找"下一个更小"，单调递减栈用于找"下一个更大"
LeetCode 相关经典题目：496（下一个更大元素 I）、739（每日温度）、42（接雨水）、84（柱状图中最大的矩形）

七、栈的更多应用场景

深度优先搜索（DFS）

图的深度优先搜索（Depth-First Search）可以显式地使用栈来实现（非递归版本）。栈中保存待访问的节点，每次从栈顶取出一个节点访问，然后将未访问的邻接节点入栈。

def dfs_stack(graph, start):
    """使用栈实现图的深度优先搜索（非递归版本）"""
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=" -> ")
            # 逆序入栈以保持与递归版本一致的访问顺序
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return visited


# 测试
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
dfs_stack(graph, 'A')  # A -> B -> D -> E -> F -> C ->

递归与栈的转换

任何递归算法都可以转换为使用栈的非递归算法。因为递归调用本质就是在使用系统的函数调用栈。理解这种转换关系，有助于深入理解递归的工作机制。

# 递归版 Fibonacci
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)


# 栈模拟版 Fibonacci
def fib_stack(n):
    if n <= 1:
        return n
    stack = [(n, 0, 0)]  # (n, state, result)
    # state: 0=开始计算, 1=已得f(n-1), 2=已得f(n-2)
    last_result = 0

    while stack:
        n, state, val = stack[-1]

        if n <= 1:
            last_result = n
            stack.pop()
            if stack:
                _, s, v = stack[-1]
                if s == 0:
                    stack[-1] = (stack[-1][0], 1, last_result)
                elif s == 1:
                    stack[-1] = (stack[-1][0], 2, v + last_result)
                elif s == 2:
                    stack[-1] = (stack[-1][0], 3, v + last_result)
            continue

        if state == 0:
            stack[-1] = (n, 1, 0)
            stack.append((n - 1, 0, 0))
        elif state == 1:
            stack[-1] = (n, 2, last_result)
            stack.append((n - 2, 0, 0))
        elif state == 2:
            last_result = val + last_result
            stack.pop()
            if stack:
                _, s, v = stack[-1]
                if s == 1:
                    stack[-1] = (stack[-1][0], 2, v + last_result)

    return last_result


# 验证两者结果一致
for i in range(10):
    assert fib_recursive(i) == fib_stack(i), f"Mismatch at {i}"
print("所有结果验证通过!")  # 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

八、栈的局限性与替代方案

虽然栈是一种强大的数据结构，但在某些场景下并不适用，需要选择更合适的数据结构：

局限性

不支持随机访问： 栈只能访问栈顶元素，不能直接访问或修改栈中间的元素
不支持查找： 查找某个元素需要弹出所有元素，破坏栈的结构
不支持遍历： 标准的栈接口不支持迭代遍历（但底层的数组实现可以遍历）
容量限制： 基于数组的实现可能存在扩容问题，基于链表的实现则增加了内存开销

替代方案选择

需要随机访问： 使用数组（列表）或动态数组
需要 FIFO 顺序： 使用队列（Queue）
需要双端操作： 使用双端队列（deque）
需要优先级顺序： 使用优先队列（堆，Heap）
需要快速查找： 使用哈希表（Hash Table）或二叉搜索树（BST）

九、核心要点总结

栈的本质： 一种受限的线性数据结构，遵循后进先出（LIFO）原则，所有操作都在栈顶进行
核心操作： push（入栈）、pop（出栈）、peek（查看栈顶）、is_empty（判空）、size（大小），均为 O(1) 时间复杂度
Python 实现： list（简单直接）、collections.deque（性能稳定）、自定义类（封装完整）、链表（无容量限制）
括号匹配： 遍历字符串，左括号入栈，右括号匹配栈顶，最后栈为空则全部匹配
表达式求值： 调度场算法（Shunting-yard）用栈实现中缀转后缀（逆波兰），再用栈计算后缀表达式
双栈应用： 浏览器的前进后退、编辑器的撤销重做都使用两个栈配合实现历史导航
函数调用栈： 每个函数调用创建一个栈帧，递归过深会导致栈溢出（Stack Overflow）
单调栈： 栈内元素保持单调递增或递减，用于"下一个更大元素"等场景，将 O(n^2) 优化为 O(n)
DFS 非递归： 使用栈可以模拟递归的深度优先搜索，避免系统调用栈的限制
递归转迭代： 理解栈是实现所有递归算法非递归版本的基础工具

十、进一步思考

栈不仅仅是一种数据结构，更是一种编程思想。当你遇到以下场景时，不妨想一想栈是否能派上用场：

思考方向

嵌套结构的处理： HTML/XML 解析、Markdown 渲染、编程语言的语法分析
回溯算法： 八皇后问题、迷宫求解、数独求解等需要"尝试-回退"模式的算法
序列化/反序列化： 将树形结构序列化为线性结构，再用栈反序列化回来
计算器实现： 从简单四则运算到带括号和函数的科学计算器，都可以用栈实现
中间代码生成： 编译器的中间代码生成阶段大量使用栈来管理运算优先级