Python 堆栈数据结构教程

在 Python 中实现 LIFO 堆栈。运行我们的交互式堆栈代码示例来掌握推送、弹出、查看和容量限制。

在编辑器中尝试

概述

堆栈是一种遵循后进先出 (LIFO) 原则的线性数据结构。这意味着添加到堆栈中的最后一个元素是第一个被删除的元素，类似于一堆盘子。

堆栈支持两种主要操作：入栈（将项目添加到顶部）和弹出（删除最近添加的项目）。此外，查看或顶部操作允许检查顶部元素而不将其移除。

在 Python 中，可以使用具有“.append()”和“.pop()”方法的列表，或者使用“collections.deque”对象轻松构建堆栈，该对象在 O(1) 时间内提供优化的双端队列操作。

代码和执行输出

使用 Python 的列表结构来模拟推送、弹出和查看功能的自定义堆栈实现。

stack.py

在编辑器中尝试

class Stack:
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        return len(self.items) == 0
        
    def push(self, item):
        self.items.append(item)
        print(f"Pushed: {item}")
        
    def pop(self):
        if self.is_empty():
            return "Underflow: Stack is empty"
        popped = self.items.pop()
        print(f"Popped: {popped}")
        return popped
        
    def peek(self):
        if self.is_empty():
            return "Stack is empty"
        return self.items[-1]
        
    def size(self):
        return len(self.items)

# Initialize stack
stack = Stack()
stack.push("Apples")
stack.push("Bananas")
stack.push("Cherries")

print(f"Current Stack Size: {stack.size()}")
print(f"Top Element (Peek): {stack.peek()}")

stack.pop()
print(f"Stack after Pop: {stack.items}")

端子输出

Pushed: Apples
Pushed: Bananas
Pushed: Cherries
Current Stack Size: 3
Top Element (Peek): Cherries
Popped: Cherries
Stack after Pop: ['Apples', 'Bananas']

逐步实施

管理软件系统中的撤消功能
编译器中的语法分析和括号检查
在引擎中递归期间跟踪执行调用堆栈

常见问题解答

为什么对于 Stacks 来说，collections.deque 比普通列表更受欢迎？

虽然列表很方便，但它们实际上是动态数组。当它们调整大小时，内存重新分配可能需要 O(n) 时间。 deque 对象使用双向链表架构，保证 O(1) 的推送和弹出。

Python 中的栈会溢出吗？

Python 中使用列表数组的标准堆栈类将不断增长，直到耗尽所有可用的系统内存。然而，Python 中的递归堆栈有一个默认限制（通常为 1000），以防止无限循环导致解释器崩溃。