栈的实现：Python数据结构与算法

栈（Stack）是一种特殊的线性数据结构，遵循后进先出（LIFO）的原则，即最后添加进栈的元素最先被移除。

1. 栈的基本概念

栈的操作主要有两种：压栈（Push）和弹栈（Pop）。压栈是将元素放入栈顶，弹栈是从栈顶移除元素。

# 使用Python/ target=_blank class=infotextkey>Python的列表实现一个简单的栈
stack = []

# 压栈操作
stack.Append(10)
stack.append(20)
stack.append(30)

# 此时栈的状态为 [10, 20, 30]

2. 访问栈顶元素

不移除元素，只是查看栈顶的元素。

# 查看栈顶元素
top_element = stack[-1]  # 结果是 30

3. 弹栈操作

移除栈顶的元素。

# 弹栈操作
top_element = stack.pop()  # 移除并返回栈顶元素，结果是 30

# 此时栈的状态为 [10, 20]

4. 栈的辅助操作

4.1 检查栈是否为空

is_empty = not bool(stack)  # 如果栈为空，结果为 True

4.2 获取栈的大小

size = len(stack)  # 结果是 2，因为栈中有两个元素

5. 栈的应用

栈在编程中有很多应用，以下是一些常见的例子：

• 函数调用：每当函数被调用时，都会将一个新的记录（通常称为“帧”）压入调用栈。
• 撤销操作：例如文字编辑器的撤销功能。
• 括号匹配：检查表达式中的括号是否正确匹配。

5.1 括号匹配示例

def is_parentheses_balanced(expr):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}

    for char in expr:
        if char in mapping.values():
            stack.append(char)
        elif char in mapping.keys():
            if stack == [] or mapping[char] != stack.pop():
                return False
    return stack == []

# 使用示例
expr = "{[()]}"
print(is_parentheses_balanced(expr))  # True，因为括号是匹配的

6. 实现一个完整的栈类

为了更好地使用栈，我们可以实现一个栈类，提供更多有用的方法。

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        """压栈操作"""
        self.items.append(item)

    def pop(self):
        """弹栈操作，返回栈顶元素"""
        return self.items.pop()

    def peek(self):
        """查看栈顶元素，不移除"""
        return self.items[-1]

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

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

# 使用栈类
s = Stack()
s.push(10)
s.push(20)
print(s.peek())  # 20
print(s.pop())   # 20

7. 综合案例：简单的后缀表达式求值

后缀表达式，也称为逆波兰表示法，是一种不需要括号的数学表示法。例如，表达式 3 + 4 在后缀表达式中表示为 3 4 +。 我们可以使用栈来计算后缀表达式的值。

def evaluate_postfix(expr):
    stack = Stack()
    tokens = expr.split()

    for token in tokens:
        if token.isdigit():
            stack.push(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == "+":
                stack.push(operand1 + operand2)
            elif token == "-":
                stack.push(operand1 - operand2)
            elif token == "*":
                stack.push(operand1 * operand2)
            elif token == "/":
                stack.push(operand1 / operand2)

    return stack.pop()

# 使用示例
expr = "3 4 + 2 *"
print(evaluate_postfix(expr))  # 结果是 14，因为 (3 + 4) * 2 = 14

小结

栈是一个非常实用的数据结构，可以帮助我们解决许多编程问题。通过理解其后进先出的特性和如何在Python中实现，你可以更加灵活地应用栈来解决问题。