Python数据结构之栈详解

什么是栈？

栈（stack）是一种数据元素只能在一端进行插入和删除操作的线性表。

栈的特点是后进先出，即在一个非空栈中，最后放入的元素最先被取出。

栈的操作

栈操作的基本有两个：

• push(elem)：插入一个新的元素elem到栈中。
• pop()：弹出栈顶的元素，并返回这个被弹出元素的值。

此外还有一个用于查询栈顶元素的操作：

• peek()：返回栈顶的元素的值，但不删除该元素。

栈还有一个重要的概念：栈顶指针（Top），指向栈顶元素在栈中的位置。

以下是栈的基本操作的Python实现：

class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, elem):
        self.stack.append(elem)

    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()

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

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

栈的应用

栈有很多应用，例如：

• 括号匹配
• 表达式计算
• 浏览器的回退和前进

以下是一个栈的简单示例：如何判断一个字符串中的括号是否是匹配的。

def isValid(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for c in s:
        if c in mapping:
            top_elem = stack.pop() if stack else "#"
            if mapping[c] != top_elem:
                return False
        else:
            stack.append(c)
    return not stack

上述代码中，我们将括号的左右对应关系存储在一个字典mapping中，然后遍历字符串，如果是左括号就压入栈中，如果是右括号，就将栈顶元素取出来与mapping中对应的值进行比较，如果不匹配则返回False，否则将匹配的括号从栈中弹出。遍历完整个字符串后，如果栈为空，则说明括号匹配成功。

结语

以上是Python数据结构之栈的详解，栈在程序开发中有着广泛的应用，希望以上内容能对大家有所帮助。