详解Python数据结构之栈stack

什么是栈stack

栈是一种先进后出（LIFO）的数据结构，只允许在表的一端进行插入和删除操作。栈的入口称为栈底，出口称为栈顶。栈常用于表达式求值、函数调用等场景。

栈的操作

栈的基本操作包括入栈(push)和出栈(pop)。其他常用的操作有判断栈是否为空(isEmpty)、获取栈的大小(size)和获取栈顶元素(peek)。

下面是Python代码实现：

class Stack:

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

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

    def pop(self):
        return self.items.pop()

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

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

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

栈的应用

逆波兰表达式求值

逆波兰表达式是一种后缀表达式。和中缀表达式相比，逆波兰表达式没有括号，操作符位于操作数后面，因此不需要考虑运算的优先级和结合性。

例如，表达式1 + 2 * 3的逆波兰表达式为1 2 3 * +。

下面是Python实现逆波兰表达式求值的代码：

def evalRPN(tokens):
    stack = []
    operators = {"+": lambda x, y: x + y, "-": lambda x, y: x - y, "*": lambda x, y: x * y, "/": lambda x, y: int(x / y)}

    for token in tokens:
        if token in operators:
            right = stack.pop()
            left = stack.pop()
            result = operators[token](left, right)
            stack.append(result)
        else:
            stack.append(int(token))

    return stack.pop()

括号匹配

括号匹配问题是常见的栈的应用场景之一。给定一个只包含(、)、[、]、{和}的字符串，判断该字符串中的括号是否匹配。

下面是Python实现括号匹配的代码：

def is_valid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)

    return not stack

总结

本文详细讲解了Python中栈的基本操作和常用应用场景，并给出了两个示例代码，希望对您理解栈的概念和实际应用有所帮助。