Python实现栈数据结构

栈是一种线性数据结构，它基于LIFO（Last-In-First-Out）原则，即最后进入的元素首先被访问。栈可以通过使用数组或链表来实现，但在本文中，我们将使用数组来实现栈数据结构。

Python提供了一个内置的list数据类型，我们可以使用该类型来创建一个栈。下面是一个简单的栈类的实现：

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

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def size(self):
        return len(self.items)

上面的代码中，我们定义了一个Stack类，它有以下几个方法：

- __init__: 初始化一个空的栈，使用一个空的list来保存栈的元素。

- is_empty: 检查栈是否为空，如果栈为空则返回True，否则返回False。

- push: 向栈中添加一个新的元素。

- pop: 弹出栈顶的元素，并返回该元素。

- peek: 返回栈顶的元素，不对栈做任何修改。

- size: 返回栈中元素的个数。

下面是一个使用栈来检查字符串中的括号是否匹配的例子：

def is_brackets_balanced(str):
    stack = Stack()

    for char in str:
        if char in '([{':
            stack.push(char)
        elif char in ')]}':
            if stack.is_empty():
                return False
            elif char == ')' and stack.peek() != '(':
                return False
            elif char == ']' and stack.peek() != '[':
                return False
            elif char == '}' and stack.peek() != '{':
                return False
            else:
                stack.pop()

    return stack.is_empty()

# 测试
print(is_brackets_balanced('()[]{}'))  # True
print(is_brackets_balanced('([)]'))    # False
print(is_brackets_balanced('{{[]}}'))  # True
print(is_brackets_balanced('({}]'))    # False

在上面的例子中，我们使用栈来检查字符串中的括号是否匹配。遍历字符串的每个字符，如果遇到左括号（'(', '[', '{'），则将其推入栈中；如果遇到右括号（')', ']', '}'），则弹出栈顶的元素，并检查是否与当前遍历的字符匹配。如果栈为空，或者弹出的元素与当前字符不匹配，则括号不匹配。

总结：

栈是一种重要的数据结构，我们可以使用栈来解决许多问题，包括表达式求值、括号匹配、迷宫求解等。通过使用Python中的list来实现一个栈类，我们可以很方便地使用栈来解决这些问题。