跳至主要内容

Python 栈:实现 LIFO 数据结构

了解 LIFO 原理,学习如何使用 Python 的 list、deque 和 LifoDeque 实现栈,并将其应用于撤销/重做系统或图遍历。
· 15分钟 阅读

使用 AI 探索

每当您按下Ctrl+Z撤销错误、点击浏览器的后退按钮,或观看递归函数逐步回退其结果时,您都在依赖栈。由于它们深深嵌入到您日常使用的软件中,您经常在不自觉的情况下与栈打交道。

在本文中,我们将看看什么是栈、栈背后的核心逻辑,比较使用 Python 内置库的不同实现策略,并将它们应用于解决算法问题。

我建议您参加我们关于n Writing Efficient Python Code 的课程,将数据结构知识与性能最佳实践结合起来,并随手备一份 Python Basics Cheat Sheet 以便快速查阅。 

什么是 Python 中的栈?

在看代码之前,理解使 Python 栈如此强大的概念基础非常重要。让我们看看栈背后的核心原理,并了解它与其他常见数据结构有何不同。

LIFO 数据结构

栈是一种遵循“后进先出”(LIFO)原则的线性数据结构。这意味着最近添加的元素总是最先被移除。可以把它想象成自助餐厅里的一摞盘子。您把新盘子放在最上面,拿盘子时也总是先拿最上面的。您不会从中间或底部抽盘子。访问完全受限于顶部。