CC++ & Algorithm

Python栈（list实现）

中等4
语言版本：C++Python
概述：栈就像一叠盘子，只能从顶上取放，Python中可以用列表轻松模拟。

用Python列表轻松实现栈（后进先出）

栈就像你桌上一叠作业本——你只能把新的本子放在最上面，拿作业时也只能从最上面拿。这种“后进先出”（Last In, First Out，简称LIFO）的规则，就是栈的核心特点。在Python里，我们不用自己写复杂的代码，直接用列表（list）的append和pop方法就能模拟栈，就像你伸手放本子和拿本子一样简单。

什么是栈？先看几个生活中的例子

栈在生活里随处可见，只是你没注意到它而已：

  • 浏览器后退按钮：你访问了页面A、B、C。每次点击链接，新页面被“压”进栈顶。当你按“后退”时，先把C弹出来，再是B，最后是A。后看的页面先退出，完美符合栈规则。
  • 自动售货机的商品弹簧：最后放进去的饮料会最先掉出来（弹簧从顶部推出）。
  • 游戏里的“撤销”操作：你画了一笔，再画一笔，最后画的先被撤销（比如画图里的Ctrl+Z）。
  • 学校里交作业：课代表把作业本叠成一摞，最后交的作业在最上面，老师改作业时从最上面拿。

这些例子的共同点：操作只发生在栈顶。你不能从中间抽一本作业，也不能把作业插到中间——否则作业堆就塌了（数据就乱了）。

用Python实现一个栈（列表版）

Python的列表天生适合做栈，因为它有：

  • append(元素) —— 相当于“放盘子到最上面”（压栈，push）
  • pop() —— 相当于“拿走最上面的盘子”（出栈，pop，默认弹出最后一个元素）
  • stack[-1] —— 看一眼最上面的盘子，但不拿走（获取栈顶元素）
  • len(stack) —— 数一数有多少个盘子
  • if stack: —— 判断盘子堆是不是空的

下面我们一步步模拟一个“零食罐子”，只能从顶部取放：

# 创建一个空栈，用来装零食
snack_stack = []

# 入栈：往罐子里放零食（按顺序放薯片、饼干、巧克力）
snack_stack.append("薯片")     # 先放薯片
snack_stack.append("饼干")     # 再放饼干，饼干在薯片上面
snack_stack.append("巧克力")   # 最后放巧克力，在最高处
print("当前零食堆：", snack_stack)
# 输出：['薯片', '饼干', '巧克力'] （巧克力在栈顶）

# 出栈：从顶部拿零食（先拿到巧克力）
top_snack = snack_stack.pop()
print("拿出来的零食：", top_snack)   # 输出：巧克力
print("剩下的零食：", snack_stack)    # 输出：['薯片', '饼干']

# 查看栈顶（不拿走）：最上面现在是饼干
print("现在最上面的零食是：", snack_stack[-1])  # 输出：饼干

# 看看栈里还有多少零食
print("零食数量：", len(snack_stack))   # 输出：2

# 判断栈是否为空（用if条件）
if snack_stack:
    print("还有零食，继续吃")
else:
    print("零食吃光了")

小提醒：只能从栈顶操作！如果你用snack_stack.pop(0)想拿底下的薯片，那就不是栈了（变成了队列）。而且列表的pop(0)效率很低，因为需要移动所有元素。

栈的实际应用：不止是理论知识

栈在编程中非常有用，GESP考试也常考。下面是两个经典应用：

1. 括号匹配（检查代码里的括号是否成对）

比如(1+2)*[3+{4-5}]是合法的，而(1+2]就不合法。原理就是：遇到左括号( [ {就压栈，遇到右括号就弹出栈顶并检查是否匹配。如果遍历完栈为空，则配对成功。

2. 浏览器后退模拟（用两个栈还能实现前进）

用一个栈存“已访问的页面”，后退时把当前页面弹出并存入另一个栈（前进栈）。代码如下：

# 模拟浏览器后退功能
history = []       # 历史栈，保存已访问的页面
current_page = None

def visit(url):
    """访问一个新页面"""
    global current_page
    if current_page:
        history.append(current_page)  # 把当前页面压入历史栈
    current_page = url
    print(f"正在访问：{current_page}")

def back():
    """后退到上一页"""
    global current_page
    if history:
        current_page = history.pop()  # 从栈顶弹出上一页
        print(f"后退到：{current_page}")
    else:
        print("没有历史记录了！")

# 测试
visit("百度")      # 当前：百度
visit("知乎")      # 当前：知乎，历史栈：['百度']
visit("B站")       # 当前：B站，历史栈：['百度', '知乎']
back()             # 后退到：知乎
back()             # 后退到：百度
back()             # 没有历史记录了！

3. 函数调用栈（你每天都在用）

程序运行时，每次调用函数都会把一个“栈帧”压入调用栈，函数执行完再弹出。如果你在函数里调用自己（递归），栈就会越压越高，直到超出限制（RecursionError）。这就是为什么递归太深会报错。

新手最容易犯的3个错误

错误1：从栈中间或底部操作

stack = [1, 2, 3]
stack.insert(0, 0)   # 把0插到最底下 —— 破坏了栈的规则！
stack.pop(0)          # 弹出最底下的元素 —— 不是栈操作！

改正：只使用append和pop()（不带参数）操作栈顶。

错误2：出栈前不检查栈是否为空

stack = []
item = stack.pop()   # 报错！IndexError: pop from empty list

改正：先判断if stack:，或者用try...except捕获错误。

错误3：混淆栈和队列

栈是后进先出（LIFO），队列是先进先出（FIFO）。比如排队打饭：先来的人先打到饭，这是队列，不能用栈模拟。

完整可运行示例：检查括号是否配对

下面是一个完整的程序，用来检查一段表达式里的括号是否都正确配对。你可以把代码复制到Python环境里运行测试。

def check_brackets(expression):
    """检查表达式中的括号是否匹配，返回True或False"""
    stack = []                  # 创建一个空栈
    # 字典：左括号对应右括号
    brackets = {'(': ')', '[': ']', '{': '}'}
    
    for char in expression:     # 遍历表达式中的每个字符
        if char in brackets:    # 如果是左括号，压栈
            stack.append(char)
        elif char in brackets.values():  # 如果是右括号
            if not stack:       # 栈为空，说明没有左括号与之配对
                return False
            left = stack.pop()  # 弹出栈顶的左括号
            # 检查弹出的左括号是否与当前右括号匹配
            if brackets[left] != char:  
                return False   # 不匹配，比如 [ 遇到 }
    
    # 遍历完后，如果栈为空说明全部配对
    return len(stack) == 0

# 测试几个例子
test_expressions = [
    "(1+2)*[3+{4-5}]",   # 正确
    "{([])}",             # 正确
    "({[})",              # 错误：} 和 [ 不匹配
    "(()",                # 错误：少一个右括号
    ")",                  # 错误：孤立右括号
]

for expr in test_expressions:
    result = check_brackets(expr)
    print(f"{expr:20} -> {'√配对正确' if result else '×配对错误'}")

运行结果：

(1+2)*[3+{4-5}]    -> √配对正确
{([])}             -> √配对正确
({[})              -> ×配对错误
(()                -> ×配对错误
)                  -> ×配对错误

想继续学习？这些知识点和栈有关

  • 队列（queue）：用collections.deque实现先进先出，适合模拟排队。
  • 双端队列（deque）：可以两端操作，比列表更适合做栈和队列。
  • 递归函数：理解函数调用栈（call stack）能帮你搞懂递归原理。
  • 深度优先搜索（DFS）：图算法中常用栈实现（或递归本质也是栈）。
  • 逆波兰表达式（后缀表达式）：计算器如何计算1 2 + 3 *？全靠栈！

栈虽然简单，但它是很多高级算法的基石。掌握了它，你就能像搭积木一样，用它解决各种实际问题。

例题精讲

1单选题

使用Python列表模拟栈时，下列哪个方法是正确的压栈操作？

Astack.insert(0, item)
Bstack.append(item)
Cstack.push(item)
Dstack.add(item)
2判断题

用Python列表模拟栈时，pop()方法默认删除并返回列表最后一个元素，对应栈的出栈操作。

3填空题
以下代码使用列表模拟栈，实现了一个检查括号是否匹配的功能。请补全缺失的代码。

def is_balanced(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            ___
    return not stack
4单选题

已知一个栈初始为空，依次执行以下操作：push(1), push(2), pop(), push(3), pop()。最终栈中的元素是？

A[1]
B[3]
C[2, 3]
D[1, 3]
5判断题

使用Python列表的insert(0, x)方法模拟栈的压栈操作，其时间复杂度为O(1)，与append相同。