Python栈（列表模拟）

用Python列表模拟栈：像叠盘子一样后进先出

栈（stack）是一种“后进先出”（LIFO，Last In First Out）的数据结构。就像餐厅里叠盘子：后放上去的盘子最先被拿走，而最底下的盘子最后才被拿走。Python的列表天生就可以当作栈来使用，我们只需要利用append和pop方法，就能轻松实现“撤销操作”、“括号匹配”等功能。

什么是栈？

栈是一种有序集合，它只允许在一端（称为栈顶）进行添加和删除操作。生活中到处都是栈：

叠盘子：每次洗好一个盘子就放在最上面，取用时也从最上面拿。
浏览器的“后退”按钮：你访问的页面被依次压入栈中，点击后退就弹出当前页面，回到上一个。
游戏中的“撤销”：每一步操作都入栈，按Ctrl+Z就弹出最近的操作。

栈的核心规则就是后进先出，最后放进栈的元素会最先被取出。

用Python列表模拟栈

Python的列表天生在末尾操作非常快，所以我们直接用列表末尾当栈顶：

入栈：append() 将元素添加到列表末尾
出栈：pop() 删除并返回列表末尾的元素
查看栈顶：stack[-1] 不删除，只看最后一项

示例：模拟叠盘子

# 用列表模拟盘子堆
plates = []                     # 空栈

# 入栈：放盘子
plates.append("盘子1")          # 第一个盘子
plates.append("盘子2")          # 放在上面
plates.append("盘子3")          # 最上面
print("当前盘子堆:", plates)    # 输出：['盘子1', '盘子2', '盘子3']

# 查看栈顶（但不取出）
top_plate = plates[-1]           # 查看最上面的盘子
print("最上面的盘子是:", top_plate)  # 盘子3

# 出栈：取走最上面的盘子
taken = plates.pop()             # 拿走盘子3
print("取走了:", taken)          # 盘子3
print("剩余盘子堆:", plates)     # ['盘子1', '盘子2']

# 继续出栈
plates.pop()                     # 取走盘子2
plates.pop()                     # 取走盘子1
print("盘子堆空了:", plates)     # []

注意：如果对一个空列表执行pop()，会报错IndexError: pop from empty list。所以出栈前通常要检查栈是否为空。

栈的三大基本操作

操作	方法	说明	生活中类比
入栈（push）	`stack.append(x)`	将元素放到栈顶	往盘子堆上放一个新盘子
出栈（pop）	`stack.pop()`	移除并返回栈顶元素	拿走最上面的盘子
查看栈顶（peek）	`stack[-1]`	只看不取，返回栈顶元素	瞥一眼最上面的盘子

这些操作的时间复杂度都是 O(1)，非常高效，因为Python列表在末尾增删都是常数时间。

新手容易犯的错误

忘记检查栈空就直接pop
```
stack = []
stack.pop()   # ❌ 报错：IndexError: pop from empty list
```
正确做法：先判断 if stack: 再pop。

混淆列表索引方向
栈顶是列表末尾，有些人误以为索引0是栈顶。

stack = [1, 2, 3]
print(stack[0])  # 这是栈底，不是栈顶
print(stack[-1]) # ✅ 栈顶是3

用pop带参数
pop(i) 会删除并返回指定位置，这不是栈的标准操作。栈只允许从末尾删除。
```
stack = [1, 2, 3]
stack.pop(0)    # ❌ 这不是栈操作，会破坏LIFO顺序
```
入栈和出栈方向搞反
有些同学用insert(0, x)入栈，用pop(0)出栈，这样虽然也能实现，但时间成本极高（O(n)），而且违背了“只在栈顶操作”的原则。所以一定要用append和pop。

实际应用：括号匹配（详细版）

括号匹配是栈的经典应用。比如在数学表达式或编程代码中，括号必须成对且正确嵌套。判断[(])是错误的，而[()]是正确的。

思路：

遇到左括号（(, [, {）就入栈。
遇到右括号（), ], }）就检查：
- 如果栈为空，说明没有左括号与之匹配 → 错误
- 否则弹出栈顶，看这个左括号是否与当前右括号对应
最后如果栈为空，说明所有括号都匹配了；如果栈里还有左括号，说明有未闭合的。

完整代码（带详细注释）：

# 括号匹配函数：检查字符串s中的括号是否匹配
def check_brackets(s):
    stack = []                              # 空栈，存放左括号
    # 字典：右括号 -> 对应的左括号
    pairs = {')': '(', ']': '[', '}': '{'}
    
    for ch in s:
        if ch in "([{":                     # 如果是左括号，入栈
            stack.append(ch)
        elif ch in ")]}":                   # 如果是右括号
            if not stack:                   # 栈空，说明没有左括号匹配
                return False
            top = stack.pop()               # 弹出栈顶左括号
            if pairs[ch] != top:            # 检查是否匹配
                return False
        # 其他字符（如字母、数字）直接忽略
    return len(stack) == 0                 # 栈空才表示全部匹配

# ---- 测试 ----
test_strings = [
    "[()]",       # 正确嵌套
    "[(])",       # 错误：嵌套顺序不对
    "({[]})",     # 正确
    "((()))",     # 正确
    "(",          # 错误：左括号未闭合
    "]",          # 错误：右括号多余
    "a+b*(c-d)",  # 正确（只检查括号，忽略其他字符）
]

for s in test_strings:
    result = check_brackets(s)
    print(f"字符串 '{s}' 括号是否匹配？ {result}")

运行结果：

字符串 '[()]' 括号是否匹配？ True
字符串 '[(])' 括号是否匹配？ False
字符串 '({[]})' 括号是否匹配？ True
字符串 '((()))' 括号是否匹配？ True
字符串 '(' 括号是否匹配？ False
字符串 ']' 括号是否匹配？ False
字符串 'a+b*(c-d)' 括号是否匹配？ True

栈的更多应用

撤销操作（Ctrl+Z）：每次操作入栈，撤销时出栈，恢复上一步状态。
浏览器前进/后退：两个栈可以模拟前进后退（一个存后退历史，一个存前进历史）。
函数调用：系统用栈来保存函数调用信息，每次调用函数就入栈一个“栈帧”，返回时出栈。
深度优先搜索（DFS）：在图或树遍历中，用栈记录待访问的节点。

完整示例：用栈实现简单的文本编辑器撤销功能

# 模拟文本编辑器的撤销功能
text = ""                # 当前文本
history = []             # 历史记录栈

def type_char(c):
    """输入一个字符"""
    global text
    history.append(text) # 先保存当前状态
    text += c
    print(f"输入 '{c}' -> 当前内容: '{text}'")

def undo():
    """撤销上一次操作"""
    global text
    if history:          # 栈非空才能撤销
        text = history.pop()
        print(f"撤销 -> 当前内容: '{text}'")
    else:
        print("没有可撤销的操作")

# 测试
type_char('H')
type_char('e')
type_char('l')
type_char('l')
type_char('o')
undo()
undo()
type_char('y')
type_char('a')
undo()

运行输出：

输入 'H' -> 当前内容: 'H'
输入 'e' -> 当前内容: 'He'
输入 'l' -> 当前内容: 'Hel'
输入 'l' -> 当前内容: 'Hell'
输入 'o' -> 当前内容: 'Hello'
撤销 -> 当前内容: 'Hell'
撤销 -> 当前内容: 'Hel'
输入 'y' -> 当前内容: 'Hey'
输入 'a' -> 当前内容: 'Heya'
撤销 -> 当前内容: 'Hey'