江苏龙网

  1. 主页 > 生活百科 > >

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

Python

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

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

文章插图
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]  # 结果是 303. 弹栈操作移除栈顶的元素 。
# 弹栈操作top_element = stack.pop()  # 移除并返回栈顶元素，结果是 30# 此时栈的状态为 [10, 20]4. 栈的辅助操作4.1 检查栈是否为空is_empty = not bool(stack)  # 如果栈为空，结果为 True4.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())  # 20print(s.pop())   # 207. 综合案例：简单的后缀表达式求值后缀表达式，也称为逆波兰表示法，是一种不需要括号的数学表示法 。例如，表达式 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


推荐阅读


上一篇：cad倒角怎么操作？工具比方法更加重要！

下一篇：四条建议，打造精简、弹性、可维护的Android架构