Python 栈指南

介绍

虽然一些数据结构是通用的并且可以在广泛的应用中使用，但其他数据结构是专门化的并且被设计用于处理特定问题。 一种这样的特殊结构，以其简单而显着的实用性而闻名，是 堆.

那么，什么是栈呢？ 从本质上讲，堆栈是一种线性数据结构，遵循 LIFO （后进先出）原则。 把它想象成自助餐厅里的一堆盘子； 你只拿最上面的盘子，当放置一个新盘子时，它会到达堆叠的顶部。

最后添加的元素是第一个要删除的元素

但是，为什么理解堆栈至关重要？ 多年来，堆栈已经在许多领域找到了应用，从您最喜欢的编程语言中的内存管理到 Web 浏览器中的后退按钮功能。 这种内在的简单性与其广泛的适用性相结合，使该堆栈成为开发人员工具库中不可或缺的工具。

在本指南中，我们将深入探讨堆栈背后的概念、它们的实现、用例等等。 我们将定义什么是堆栈、它们如何工作，然后我们将了解在 Python 中实现堆栈数据结构的两种最常见的方法。

堆栈数据结构的基本概念

从本质上讲，堆栈看似简单，但它所具有的细微差别使其在计算领域具有多种应用。 在深入研究其实现和实际用途之前，让我们确保对堆栈的核心概念有一个透彻的理解。

LIFO（后进先出）原则

LIFO 是堆栈背后的指导原则。 这意味着最后进入堆栈的项目是第一个离开的项目。 这一特性将堆栈与其他线性数据结构（例如队列）区分开来。

基本操作

每个数据结构都是由它支持的操作定义的。 对于堆栈来说，这些操作很简单但至关重要：

• 推 – 将一个元素添加到栈顶。 如果堆栈已满，则此操作可能会导致堆栈溢出。

• Pop – 删除并返回堆栈最顶层的元素。 如果堆栈为空，尝试弹出可能会导致堆栈下溢。

• 窥视（或顶部） – 观察最上面的元素而不删除它。 当您想要检查当前顶部元素而不更改堆栈状态时，此操作非常有用。

到现在为止，堆栈数据结构及其基本概念的重要性应该很明显了。 随着我们的前进，我们将深入研究其实现，阐明这些基本原则如何转化为实际代码。

如何在 Python 中从头开始实现堆栈

掌握了堆栈背后的基本原理后，是时候卷起袖子深入研究事物的实际方面了。 实现堆栈虽然简单，但可以通过多种方式实现。 在本节中，我们将探讨实现堆栈的两种主要方法 - 使用数组和链表。

使用数组实现堆栈

数组，是 连续的内存位置，提供了一种直观的方式来表示堆栈。 它们允许按索引访问元素的时间复杂度为 O(1)，从而确保快速推送、弹出和查看操作。 此外，数组可以提高内存效率，因为没有链表中的指针开销。

另一方面，传统数组具有固定大小，这意味着一旦初始化，它们就无法调整大小。 这可能会导致 堆栈溢出 如果没有监控。 这可以通过动态数组来克服（比如Python的 list），可以调整大小，但是这个操作成本相当高。

完成所有这些后，让我们开始在 Python 中使用数组实现我们的堆栈类。 首先，让我们创建一个类本身，其构造函数将堆栈的大小作为参数：

class Stack: def __init__(self, size): self.size = size self.stack = [None] * size self.top = -1

正如您所看到的，我们在类中存储了三个值。 这 size 是所需的堆栈大小， stack 是用于表示堆栈数据结构的实际数组，并且 top 是最后一个元素的索引 stack 数组（栈顶）。

从现在开始，我们将为每个基本堆栈操作创建并解释一种方法。 这些方法中的每一个都将包含在 Stack 我们刚刚创建的类。

让我们先从 push() 方法。 如前所述，入栈操作将一个元素添加到堆栈顶部。 首先，我们将检查堆栈是否还有空间供我们要添加的元素使用。 如果堆栈已满，我们将提高 Stack Overflow 例外。 否则，我们只需添加元素并调整 top 和 stack 因此：

def push(self, item): if self.top == self.size - 1: raise Exception("Stack Overflow") self.top += 1 self.stack[self.top] = item

现在，我们可以定义从堆栈顶部删除元素的方法 - pop() 方法。 在尝试删除元素之前，我们需要检查堆栈中是否有任何元素，因为尝试从空堆栈中弹出元素是没有意义的：

def pop(self): if self.top == -1: raise Exception("Stack Underflow") item = self.stack[self.top] self.top -= 1 return item

最后，我们可以定义 peek() 仅返回当前位于堆栈顶部的元素的值的方法：

def peek(self): if self.top == -1: raise Exception("Stack is empty") return self.stack[self.top]

就是这样！ 我们现在有一个类，它在 Python 中使用列表实现堆栈的行为。

使用链表实现堆栈

链表，是 动态数据结构，可以轻松增长和收缩，这有利于实现堆栈。 由于链表根据需要分配内存，因此堆栈可以动态增长和减少，而无需显式调整大小。 使用链表实现堆栈的另一个好处是入栈和出栈操作只需要简单的指针变化。 这样做的缺点是链表中的每个元素都有一个额外的指针，与数组相比会消耗更多的内存。

正如我们已经在 《Python 链表》 文章中，在实际链表之前我们需要实现的第一件事是单个节点的类：

class Node: def __init__(self, data): self.data = data self.next = None

此实现仅存储两点数据 - 存储在节点中的值（data）和对下一个节点的引用（next).

现在我们可以跳到实际的堆栈类本身。 构造函数与之前的构造函数略有不同。 它将只包含一个变量——对堆栈顶部节点的引用：

class Stack: def __init__(self): self.top = None

不出所料 push() 方法将一个新元素（在本例中为节点）添加到堆栈顶部：

def push(self, item): node = Node(item) if self.top: node.next = self.top self.top = node

pop() 方法检查堆栈中是否有元素，如果堆栈不为空，则删除最上面的元素：

def pop(self): if not self.top: raise Exception("Stack Underflow") item = self.top.data self.top = self.top.next return item

最后，该 peek() 方法只是从堆栈顶部读取元素的值（如果有的话）：

def peek(self): if not self.top: raise Exception("Stack is empty") return self.top.data

数组和链表之间的选择取决于应用程序的具体要求和约束。

如何使用 Python 的内置结构实现堆栈

对于许多开发人员来说，从头开始构建堆栈虽然具有教育意义，但可能不是在实际应用程序中使用堆栈的最有效方法。 幸运的是，许多流行的编程语言都配备了自然支持堆栈操作的内置数据结构和类。 在本节中，我们将探讨 Python 在这方面的产品。

Python 作为一种多功能且动态的语言，没有专用的堆栈类。 然而，它的内置数据结构，特别是列表和 deque 类 collections 模块，可以毫不费力地充当堆栈。

使用 Python 列表作为堆栈

Python 列表可以非常有效地模拟堆栈，因为它们的动态特性以及诸如 append() 和 pop().

• 推送操作 – 将元素添加到堆栈顶部就像使用 append() 方法：

  stack = []
  stack.append('A')
  stack.append('B')
  

• 流行操作 – 删除最上面的元素可以使用 pop() 不带任何参数的方法：

  top_element = stack.pop() 

• 窥视操作 可以使用负索引来访问顶部而不弹出：

  top_element = stack[-1] 

运用 双端队列 班级从 收藏 模块

deque （双端队列的缩写）类是堆栈实现的另一个多功能工具。 它针对两端的快速追加和弹出进行了优化，使其堆栈操作比列表稍微高效一些。

• 初始化:

  from collections import deque
  stack = deque()
  

• 推送操作 – 与列表类似， append() 使用方法：

  stack.append('A')
  stack.append('B')
  

• 流行操作 – 喜欢列表， pop() 方法完成这项工作：

  top_element = stack.pop() 

• 窥视操作 – 方法与列表相同：

  top_element = stack[-1] 

何时使用哪个？

虽然列表和双端队列都可以用作堆栈，但如果您主要将该结构用作堆栈（从一端追加和弹出），则 deque 由于其优化，速度可能会稍快一些。 然而，对于大多数实际目的，除非处理性能关键的应用程序，Python 的列表应该足够了。

潜在的堆栈相关问题以及如何克服它们

虽然堆栈像任何其他数据结构一样具有令人难以置信的通用性和高效性，但它们也不能避免潜在的陷阱。 在使用堆栈时必须认识到这些挑战并制定解决这些挑战的策略。 在本节中，我们将深入探讨一些常见的堆栈相关问题，并探索解决这些问题的方法。

堆栈溢出

当尝试将元素推入已达到其最大容量的堆栈时，就会发生这种情况。 在堆栈大小固定的环境中（例如在某些低级编程场景或递归函数调用中），这尤其是一个问题。

如果您使用基于数组的堆栈，请考虑切换到动态数组或链表实现，它们会自行调整大小。 防止堆栈溢出的另一个步骤是持续监视堆栈的大小，特别是在压入操作之前，并针对堆栈溢出提供明确的错误消息或提示。

如果由于过多的递归调用而导致堆栈溢出，请考虑迭代解决方案或在环境允许的情况下增加递归限制。

堆栈下溢

当尝试从空堆栈中弹出元素时会发生这种情况。 为了防止这种情况发生，请在执行弹出或查看操作之前始终检查堆栈是否为空。 返回清晰的错误消息或优雅地处理下溢，而不会导致程序崩溃。

在可接受的环境中，请考虑在从空堆栈弹出时返回一个特殊值以表示操作无效。

内存限制

在内存受限的环境中，即使动态调整堆栈大小（例如基于链表的堆栈），如果堆栈变得太大，也可能会导致内存耗尽。 因此，请密切关注应用程序的整体内存使用情况和堆栈的增长。 也许对堆栈的大小引入软上限。

线程安全问题

在多线程环境中，不同线程对共享堆栈的同时操作可能会导致数据不一致或意外行为。 此问题的潜在解决方案可能是：

• 互斥体和锁 – 使用互斥体（互斥对象）或锁来确保在给定时间只有一个线程可以对堆栈执行操作。
• 原子操作 – 如果环境支持，则利用原子操作来确保推送和弹出操作期间的数据一致性。
• 线程局部堆栈 – 在每个线程都需要其堆栈的情况下，请考虑使用线程本地存储为每个线程提供单独的堆栈实例。

虽然堆栈确实很强大，但了解其潜在问题并积极实施解决方案将确保应用程序的健壮和无错误。 认识到这些陷阱就成功了一半，另一半就是采用最佳实践来有效解决这些问题。

结论

尽管堆栈看似简单，但却是计算世界中许多基本操作的基础。 从解析复杂的数学表达式到管理函数调用，它们的用途广泛且重要。 当我们了解了这种数据结构的来龙去脉时，很明显它的优势不仅在于它的效率，还在于它的多功能性。

然而，与所有工具一样，其有效性取决于其使用方式。 只需确保您彻底了解其原理、潜在陷阱和最佳实践，以确保您能够利用堆栈的真正力量。 无论您是从头开始实现还是利用 Python 等语言的内置工具，这些数据结构的谨慎应用将使您的解决方案与众不同。

• SEO 支持的内容和 PR 分发。 今天得到放大。
• PlatoData.Network 垂直生成人工智能。 赋予自己力量。 访问这里。
• 柏拉图爱流。 Web3 智能。 知识放大。 访问这里。
• 柏拉图ESG。 碳， 清洁科技, 能源， 环境， 太阳能， 废物管理。 访问这里。
• 柏拉图健康。 生物技术和临床试验情报。 访问这里。
• Sumber: https://stackabuse.com/guide-to-stacks-in-python/