Python 中的栈

在本教程中，我们将学习栈的基本知识，并使用 Python 代码实现它。

什么是栈？

栈是一种线性数据结构，其中数据按对象叠加的方式排列。它以 LIFO（后进先出）的方式存储数据。数据存储的顺序与厨房里盘子一个叠一个的摆放方式类似。栈的一个简单例子是编辑器中的撤销功能。撤销功能基于我们最近进行的操作。

我们总是从盘子堆的顶部取走最后一个盘子。在栈中，新元素插入到一端，而元素只能从那一端移除。

我们可以在栈中执行两个操作——PUSH（入栈）和POP（出栈）。PUSH 操作是指添加元素，而POP 操作是指从栈中移除元素。

栈的方法

Python 提供了以下常用的栈方法。

• empty() - 如果栈为空，则返回 true。时间复杂度为 O(1)。
• size() - 返回栈的长度。时间复杂度为 O(1)。
• top() - 此方法返回栈中最后一个元素的地址。时间复杂度为 O(1)。
• push(g) - 此方法在栈的末尾添加元素 'g'。时间复杂度为 O(1)。
• pop() - 此方法移除栈顶元素。时间复杂度为 O(1)。

栈的实现

Python 提供了多种实现栈的方式。在本节中，我们将讨论使用 Python 及其模块实现栈。

我们有以下几种方法在 Python 中实现栈。

• 列表
• deque
• LifeQueue

使用列表实现

Python 列表可以用作栈。它使用 append() 方法将元素插入列表，而栈使用 push() 方法。列表还提供了 pop() 方法来移除最后一个元素，但列表存在一些缺点。随着列表的增长，它的速度会变慢。

列表将新元素紧挨着其他元素存储。如果列表增长超出当前内存块，Python 会分配一些新内存。这就是列表变慢的原因。让我们通过以下示例来理解——

输出

['x', 'y', 'z']

Elements poped from my_stack:
z
y
x  

my_stack after elements are poped:
[]
Traceback (most recent call last):
  File "C:/Users/DEVANSH SHARMA/PycharmProjects/Hello/Stack.py", line 21, in <module>
    print(my_stack.pop())
IndexError: pop from empty list

解释 -

在上面的代码中，我们定义了一个空列表。我们使用 append() 方法逐个插入元素。这相当于 push() 方法。我们也使用 pop() 方法移除了元素。pop() 方法返回列表的最后一个元素。

使用 collection.deque 实现

collection 模块提供了 deque 类，该类用于创建 Python 栈。deque 的发音是“deck”，意思是“双端队列”。与列表相比，deque 更受欢迎，因为它比列表执行 append 和 pop 操作更快。时间复杂度为 O(1)，而列表需要 O(n)。

让我们理解以下示例 -

示例

输出

Initial my_stack:
deque(['a', 'b', 'c'])
Elements poped from my_stack:
c
b
a
my_stack after elements are poped:
deque([])

说明

上面的代码与前面的示例几乎相同。但是，唯一的区别是我们从 collection 模块导入了 deque。

Deque 与 list 对比

列表将元素紧挨着存储，并使用连续的内存。这对于许多操作（如列表索引）来说非常高效。例如，获取 list1[2] 很快，因为 Python 知道特定元素的精确位置。连续内存也使切片操作在列表上效果很好。

列表在 append() 添加某些对象时比添加其他对象消耗更多时间。如果连续内存块已满，它将获取另一个内存块，这可能比正常的 append() 函数花费更长的时间。

使用 queue 模块实现

queue 模块有一个 LIFO 队列，与栈相同。通常，队列使用 put() 方法添加数据，并使用 get() 方法获取数据。

以下是一些在 queue 模块中可用的方法。

• empty() - 如果队列为空，则返回 true；否则返回 false。
• maxsize() - 此方法用于设置队列允许的最大元素数量。
• get() - 它返回并从队列中移除元素。有时队列可能是空的，它会等待直到有元素可用。
• full() - 如果队列已满，则返回 True。队列默认定义为 maxsize = 0。在这种情况下，它不会返回 True。
• put(item) - 它将元素添加到队列；如果队列已满，则等待直到有可用空间。
• put_nowait(item) - 它在不延迟的情况下将元素添加到队列。
• qsize() - 返回队列的大小。

让我们通过以下 queue 模块示例来理解。

示例 -

输出

0
Stack is Full:  False
Size of Stack:  3

Elements poped from the my_stack
z
y
x

Stack is Empty:  True

解释 -

在上面，我们导入了 queue 模块，这是一个 LIFOqueue。它的工作方式与栈相同，但此模块包含上面提到的一些附加函数。我们定义了一个带有 maxsize 的栈，这意味着它可以容纳最多五个值。

初始数组大小为零，我们使用 put() 方法向栈中推送了三个元素。现在，我们再次检查栈是否为空以及栈的大小。栈中有三个元素。我们使用 get() 方法弹出了一个元素。它首先移除最后添加的元素。在移除所有元素后，我们得到一个空栈。

Python 栈和线程

我们也可以在多线程程序中使用 Python 栈。这是一个高级主题，但并不常用，如果您对多线程不感兴趣，可以跳过本节。

在我们的程序中使用多线程时，列表和 deque 的行为不同。在多线程编程中使用列表可能很危险，因为它不是线程安全的。

另一方面，deque 稍微复杂一些，因为它的 append() 和 pop() 方法是原子性的，这意味着它们不会被其他线程中断。

我们可以使用 deque 构建多线程程序，但这可能会在未来导致一些复杂性。

现在的问题是，我们如何构建一个带有多线程的 Python 栈程序。

答案是我们可以使用 LIFOqueue，并且我们知道 LIFO 代表什么——后进先出。它使用 put() 和 get() 来添加和移除栈元素。

应该考虑哪种栈实现方式？

我们已经提到了在 Python 中实现栈的三种方法。上述方法各有优缺点。

让我们消除混淆：如果您在使用带有多线程的栈，您应该使用 Lifoqueue，但要确保其弹出和推送元素的性能。但如果您不使用多线程，请使用 deque。

我们也可以使用列表来实现栈，但列表可能会有潜在的内存重新分配问题。列表和 deque 在接口上是相同的，但 deque 没有内存分配问题。

结论

我们简要地定义了栈及其实现。Python 栈可以用于实际程序。我们可以根据我们的需求选择实现方法。我们还定义了带有多线程环境的 Python 栈。