栈

简介

栈类似于一叠盘子，总是从顶部添加和移除盘子。在栈中，最后添加的元素将是第一个被移除的元素。

栈的概念

栈（Stack）是一种遵循后进先出（LIFO，Last In First Out）原则的数据结构。

在Python中，栈可以通过列表（list）很容易地实现。

栈的基本操作

压栈（Push）：在栈顶添加一个元素。
弹栈（Pop）：移除栈顶元素，并返回该元素。
查看栈顶元素（Peek/Top）：查看栈顶元素，但不移除它。
检查栈是否为空（IsEmpty）：检查栈是否没有元素。
获取栈的大小（Size）：获取栈中元素的数量。

使用列表实现栈

Python的列表提供了append()和pop()方法，可以很方便地实现栈的操作。

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

    # 压栈操作
    def push(self, item):
        # 向链表末尾添加元素
        self.items.append(item)

    # 弹线操作
    def pop(self):
        # 如果栈不为空，进行弹栈
        if not self.is_empty():
            # 从列表末尾取出并删除元素
            return self.items.pop()
        # 如果栈为空，则返回空
        return None

    # 查看栈顶元素
    def peek(self):
        # 如果栈不为空
        if not self.is_empty():
            # 返回列表中最后一个元素
            return self.items[-1]
        # 否则返回空
        return None

    # 判断栈是否为空
    def is_empty(self):
        return self.size() == 0

    # 查看栈内元素个数
    def size(self):
        return len(self.items)

栈的应用示例

栈在编程中有许多应用，如函数调用栈、表达式求值、括号匹配检查等。

函数调用栈示例

在Python中，每当你调用一个函数，解释器都会将其添加到函数调用栈中。我们可以通过一个简单的例子来模拟这个过程。

def simulate_function_call():
    call_stack = Stack()

    # 模拟函数调用
    functions = ["func1", "func2", "func3"]
    for func in functions:
        call_stack.push(func)

    # 模拟函数执行结束并从栈中弹出
    while not call_stack.is_empty():
        current_function = call_stack.pop()
        print(f"函数执行结束: {current_function}")

simulate_function_call()

括号匹配检查示例

使用栈可以很容易地检查表达式中的括号是否正确匹配。

def is_parentheses_balanced(expression):
    # 实例一个栈对象
    stack = Stack()
    # 定义一个括号匹配规则
    pairs = {')': '('}
    # 遍历数据源
    for char in expression:
        # 如果字符在规则的值中，也就是字符是右括号时，进行压栈操作
        if char in pairs.values():
            stack.push(char)
        # 如果字符是key中，也就是字符是左括号时
        elif char in pairs.keys():
            # 判断栈是否为空 或者 出栈的字符不是规则对应的右括号时
            if stack.is_empty() or stack.pop() != pairs[char]:
                # 返回假
                return False
    # 如果遍历结束后，栈为空，说明括号匹配正确，如果栈不为空，说明括号匹配不正确
    return stack.is_empty()

# 测试括号匹配
expressions = ["(())", "((()))", "(()", ")(", "(a + b) * (c - d)"]
for expr in expressions:
    print(f"表达式 '{expr}' 的括号匹配: {is_parentheses_balanced(expr)}")

总结

栈是一种基本的数据结构，它在计算机科学中有着广泛的应用。

理解栈的概念和操作对于解决许多编程问题至关重要。

Python的列表类型为实现栈提供了便利。