Python栈（列表模拟）

用列表模拟栈：后进先出的数据结构

栈（Stack）是一种非常基础的数据结构，它遵循“后进先出”（Last In First Out，简称 LIFO）的原则。你可以把它想象成一摞盘子：每次只能把新盘子放在最上面，取盘子时也只能从最上面拿，所以最后放上去的盘子最先被取走。在Python中，我们不需要额外安装库，直接用列表（list）就能轻松模拟栈。

栈的概念与生活类比

生活中到处都是栈的影子：

餐厅里的一摞盘子 – 清洁阿姨会把洗好的盘子一个个叠上去，客人取用时从顶部拿。
浏览器的“后退”按钮 – 你浏览网页时，每点击一个新链接，浏览器就把当前页面“压入”栈中；点击后退，就“弹出”上一个页面。
文本编辑器的“撤销” – 每做一次操作（如打字、删除），就把操作记录推入栈；撤销时从栈顶取出最近的操作并回退。
函数调用 – 当你写一个函数A，函数A又调用了函数B，计算机先把A的信息压入“调用栈”，再压入B的信息；B执行完就弹出，然后继续执行A。

这些例子都符合 后进先出 的特点：最后一个进来的，最先出去。

用Python列表实现栈

Python的列表（list）天生就支持在末尾添加和删除元素，正好对应栈的“栈顶”操作。

栈的操作	列表方法	说明
入栈	`stack.append(x)`	把元素x放到栈顶（列表末尾）
出栈	`stack.pop()`	移除栈顶元素并返回它
查看栈顶	`stack[-1]`	只看看最上面的元素，不取走
判空	`len(stack) == 0`	判断栈里有没有元素

注意：pop() 如果栈为空，会抛出 IndexError，所以在出栈前要先检查栈是否为空。

经典应用1：模拟撤销功能（再次回顾）

我们已经在开头看到了文本编辑器撤销的例子，这里再补充一个“浏览器后退”的模拟，代码更清晰：

# 模拟浏览器的后退功能
back_stack = []   # 存已访问页面的栈
current_page = "首页"

# 访问几个新页面
back_stack.append(current_page)       # 入栈：保存当前页
current_page = "新闻"
back_stack.append(current_page)       # 入栈：保存新闻页
current_page = "体育"
back_stack.append(current_page)       # 入栈：保存体育页
current_page = "娱乐"
# 现在 current_page 是“娱乐”，栈里有：首页→新闻→体育

print("当前页面：", current_page)      # 娱乐
print("后退历史：", back_stack)        # ['首页', '新闻', '体育']

# 点击两次后退
last_page = back_stack.pop()          # 出栈：体育
current_page = last_page
print("后退一次后页面：", current_page) # 体育

last_page = back_stack.pop()          # 出栈：新闻
current_page = last_page
print("后退两次后页面：", current_page) # 新闻

print("剩余后退历史：", back_stack)    # ['首页']

这个例子展示了“后进先出”的直观含义：最后访问的“娱乐”其实没有入栈（因为没点击新链接？实际上我们模拟的是先入栈再跳转，这里为了演示简单，把每次访问前的页面入栈。实际浏览器更复杂，但原理类似。）

经典应用2：括号匹配检查

括号匹配是栈的经典考题，用于检查表达式中左右括号是否成对出现。比如 (1+2)*3 是合法的，而 ((1+2) 或 (1+2)) 就不合法。思路很简单：

遍历每个字符
遇到左括号 ( 就入栈
遇到右括号 ) 就检查栈是否空：如果空，说明右括号太多，返回 False；否则出栈一个左括号与之匹配
遍历结束后，如果栈为空，说明所有括号都匹配；否则有未匹配的左括号

下面是一个完整实现，并加入了更多注释：

def is_balanced(expression):
    """
    检查 expression 中的圆括号是否匹配
    """
    stack = []                    # 创建一个空栈
    for ch in expression:         # 遍历字符串中的每个字符
        if ch == '(':             # 遇到左括号：入栈
            stack.append(ch)
        elif ch == ')':           # 遇到右括号
            if len(stack) == 0:   # 栈为空，说明右括号多了
                return False
            stack.pop()           # 否则弹出匹配的左括号
    return len(stack) == 0        # 最后栈应为空

test1 = "(1+2)*3"
test2 = "((1+2)"
test3 = "(1+2))"
test4 = "()()(())"

print(is_balanced(test1))   # True
print(is_balanced(test2))   # False
print(is_balanced(test3))   # False
print(is_balanced(test4))   # True

这个程序可以轻松扩展支持花括号 {} 和方括号 []，只需要在遇到不同括号时判断是否配对即可（稍后会在完整示例中展示）。

新手容易犯的错误

对空栈执行 pop() 或 stack[-1]
初学者常常忘记先判断栈是否为空，导致 IndexError: pop from empty list。
正确做法：出栈或查看栈顶前，用 if stack: 或 if len(stack) > 0 检查。
混淆栈和队列
栈是后进先出，队列是先进先出。有些题目要求用栈，却误用 pop(0) 或 insert(0, x)，这会让效率变得极低（pop(0) 是 O(n) 操作），而且违背了栈的语义。
忘记保留原有内容
比如在括号匹配中，只检查了左括号入栈、右括号出栈，却没有在最后检查栈是否为空，导致 "((1+2)" 这种左括号多的情况被误判为合法。
用列表的 insert(0, x) 模拟“栈底”操作
有人觉得栈也可以从底部操作，但标准栈只允许在一端操作。用 insert(0, x) 会把元素插入到列表开头，这样做虽然能实现“后进先出”（插入在头部，取也从头部），但插入和删除头部都是 O(n) 操作，效率很差。记住：用 append 和 pop（末尾）才是栈的正确模拟。

完整示例：用栈将十进制数转换为二进制数

这是一个非常实用的例子。十进制转二进制的方法：不断除以2取余数，把余数压入栈中，最后再依次弹出。因为最后得到的余数是最高位，先得到的余数是最低位，后进先出正好符合我们的需求。

def decimal_to_binary(num):
    """
    将十进制整数 num 转换为二进制字符串
    使用栈模拟除2取余法
    """
    stack = []                    # 栈，用来存储余数
    if num == 0:
        return "0"
    while num > 0:                # 当 num 大于0时循环
        remainder = num % 2       # 取余数
        stack.append(remainder)   # 入栈（先得到的余数先入栈）
        num = num // 2            # 整数除法，更新 num
    # 此时栈中元素从栈底到栈顶依次是低位到高位
    binary_str = ""
    while stack:                  # 栈不为空时循环
        digit = stack.pop()       # 出栈（后进先出，高位先出）
        binary_str += str(digit)
    return binary_str

# 测试
number = 13                      # 二进制是 1101
result = decimal_to_binary(number)
print(f"{number} 的二进制是 {result}")   # 输出 13 的二进制是 1101

手动验证：

13 ÷ 2 = 6 余 1 → 入栈
6 ÷ 2 = 3 余 0 → 入栈
3 ÷ 2 = 1 余 1 → 入栈
1 ÷ 2 = 0 余 1 → 入栈
栈内容：[1, 0, 1, 1]（栈底→栈顶）
出栈顺序：1（高位）, 1, 0, 1（低位） → 得到 "1101" ✅