第 5 课：栈 (Stack)

学习目标

通过本节课的学习，你将能够：

1. 理解并准确描述栈这种数据结构的核心特性（LIFO）。
2. 掌握栈的两种核心操作（压栈与弹栈）的原理和用法。
3. 使用 Python 列表（或其他方式）实现一个基本的栈。
4. 识别并分析栈在解决实际问题中的典型应用场景。
5. 避免在实现和使用栈时常见的错误。

核心概念

想象一下，你在一个自助餐厅取餐。盘子们被叠放在一起，你每次只能从最顶部取走一个盘子，新清洗的盘子也只能放在最顶部。这个叠放盘子的容器，就是栈。

栈是一种遵循后进先出 (Last-In, First-Out, LIFO) 原则的线性数据结构。这意味着，最后一个被放入栈中的元素，将会是第一个被取出的元素。

栈的操作被严格限制在结构的一端，这一端被称为栈顶 (Top)。另一端称为栈底 (Bottom)。就像你只能接触最上面的盘子一样，所有的添加和移除操作都只能在栈顶进行。

栈的两个基本操作是：

• 压栈 (Push): 将一个新元素添加到栈顶。
• 弹栈 (Pop): 移除并返回栈顶的元素。

此外，还有一个常用的查看操作：

• 窥视 (Peek/Top): 返回栈顶的元素，但不移除它。

代码示例

下面我们用 Python 的列表来实现一个简单的栈。Python 列表的 append() 和 pop() 方法天然地支持栈操作，因为它们都是在列表的末尾（即我们的“栈顶”）进行操作。

class Stack:
    def __init__(self):
        """初始化一个空栈"""
        self.items = [] # 使用列表存储栈元素

    def is_empty(self):
        """判断栈是否为空"""
        return len(self.items) == 0

    def push(self, item):
        """将元素压入栈顶"""
        self.items.append(item)
        print(f'压入元素: {item}')

    def pop(self):
        """弹出并返回栈顶元素"""
        if self.is_empty():
            raise IndexError("栈为空，无法弹出")
        item = self.items.pop()
        print(f'弹出元素: {item}')
        return item

    def peek(self):
        """窥视栈顶元素（不弹出）"""
        if self.is_empty():
            raise IndexError("栈为空，无法窥视")
        return self.items[-1]

    def size(self):
        """返回栈的大小"""
        return len(self.items)

    def __str__(self):
        """以易读的字符串形式打印栈"""
        return f'栈内容 (栈顶->栈底): {self.items[::-1]}'


# --- 使用我们的栈类 ---
if __name__ == "__main__":
    # 1. 创建一个栈
    my_stack = Stack()
    print(f'栈是否为空? {my_stack.is_empty()}') # 输出: True

    # 2. 压栈操作
    my_stack.push('A')
    my_stack.push('B')
    my_stack.push('C')
    print(my_stack) # 输出: 栈内容 (栈顶->栈底): ['C', 'B', 'A']

    # 3. 窥视操作
    top_item = my_stack.peek()
    print(f'栈顶元素是: {top_item}') # 输出: C

    # 4. 弹栈操作
    my_stack.pop() # 弹出 C
    my_stack.pop() # 弹出 B
    print(f'栈的大小: {my_stack.size()}') # 输出: 1
    print(my_stack) # 输出: 栈内容 (栈顶->栈底): ['A']

    # 5. 再次弹栈，栈变为空
    my_stack.pop() # 弹出 A
    print(f'栈是否为空? {my_stack.is_empty()}') # 输出: True

运行结果：

栈是否为空? True
压入元素: A
压入元素: B
压入元素: C
栈内容 (栈顶->栈底): ['C', 'B', 'A']
栈顶元素是: C
弹出元素: C
弹出元素: B
栈的大小: 1
栈内容 (栈顶->栈底): ['A']
弹出元素: A
栈是否为空? True

实践练习

练习 1：基础操作

创建一个栈，依次压入数字 10, 20, 30。然后弹出两次，并打印每次弹出的元素以及栈中剩余的元素。

练习 2：括号匹配检查器

使用栈来检查一个字符串中的括号是否匹配。例如，"({[]})" 是匹配的，而 "({[})" 则不匹配。 要求：编写一个函数 is_brackets_balanced(s)，如果字符串 s 中的括号（(), [], {}）正确嵌套则返回 True，否则返回 False。 提示：遍历字符串，遇到左括号就压栈；遇到右括号就检查栈顶是否是对应的左括号，如果是就弹栈，否则不匹配。

练习 3：逆序输出链表

给定一个单链表，使用栈来实现将其所有元素逆序打印。 提示：遍历链表，将每个节点的值压入栈。遍历完成后，依次弹栈并打印，即可实现逆序。

常见错误

1. 在空栈上执行弹栈或窥视操作：

   • 错误代码：my_stack.pop() # 当 my_stack 为空时
   • 后果：会抛出 IndexError 异常。
   • 正确做法：在执行 pop() 或 peek() 前，务必先使用 is_empty() 进行检查。

2. 混淆栈顶和栈底：

   • 错误概念：以为第一个压入的元素在栈顶。
   • 正确概念：LIFO，最后一个压入的元素在栈顶，最先弹出。实现时，要确保 push 和 pop 操作都在数据结构的同一端（如列表的末尾）进行。

3. 将栈与列表完全等同：

   • 错误用法：使用 insert(0, item) 或 pop(0) 在列表头部进行操作来模拟栈。
   • 后果：虽然逻辑上可以，但在列表头部进行插入和删除的时间复杂度为 O(n)，效率很低。
   • 正确做法：始终使用列表的尾部（append 和 pop）作为栈顶，它们的操作时间复杂度为 O(1)。

小结

• 核心特性：栈是后进先出 (LIFO) 的数据结构，只能在栈顶进行插入和删除。
• 基本操作：
  • push(item): 压栈，将元素添加到栈顶。
  • pop(): 弹栈，移除并返回栈顶元素。
  • peek(): 窥视，返回栈顶元素但不移除。
  • is_empty(): 判断栈是否为空。
• 实现方式：可以使用数组（如 Python 列表）或链表来实现。使用列表的尾部作为栈顶是最高效的方式。
• 典型应用：函数调用栈、撤销(Undo)机制、浏览器历史记录（后退按钮）、括号匹配检查、表达式求值等。
• 重要提醒：操作前检查栈空，确保所有操作都在栈顶进行。