在本教程中，我们将学习栈的基础知识，并使用 Python 代码实现它。
什么是栈？
栈是一种线性数据结构，其中数据被一个对象排列在另一个对象之上。它以后进先出的方式存储数据。数据以类似的顺序存储，因为盘子在厨房里一个接一个地排列。栈的简单示例是编辑器中的撤销功能。撤消功能适用于我们已经完成的最后一个事件。
我们总是从一堆盘子中挑选最后一个。在栈中，新元素插入在一端，元素只能从该端移除。
我们可以在栈中执行两个操作- PUSH 和 POP 。推送操作是当我们添加一个元素时，而弹出操作是当我们从栈中移除一个元素时。
栈方法
Python 提供了以下常用于栈的方法。
- 空()- 如果栈为空，则返回真。时间复杂度为 O(1)。
- size() - 返回栈的长度。时间复杂度为 O(1)。
- top() - 这个方法返回栈最后一个元素的地址。时间复杂度为 O(1)。
- push(g)—该方法在栈尾加入元素‘g’—时间复杂度为 O(1)。
- pop() - 此方法移除栈的最顶层元素。时间复杂度为 O(1)。
栈的实现
Python 提供了各种方法来实现栈。在本节中，我们将讨论使用 Python 及其模块实现栈。
我们可以通过以下方式在 Python 中实现栈。
- 目录
- 出列
- LifeQueue
使用列表实现
Python 列表可以用作栈。它使用 append() 方法将元素插入列表，其中栈使用 push() 方法。该列表还提供了 pop()方法来移除最后一个元素，但是该列表存在一些缺点。列表随着增长而变得缓慢。
列表将新元素存储在下一个元素中。如果列表变大，超出了一个内存块，Python 就会分配一些内存。这就是列表变得缓慢的原因。让我们理解下面的例子-
# initial empty stack
my_stack = []
# append() function to push
# element in the my_stack
my_stack.append('x')
my_stack.append('y')
my_stack.append('z')
print(my_stack)
# pop() function to pop
# element from my_stack in
# LIFO order
print('nElements poped from my_stack:')
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print('nmy_stack after elements are poped:')
print(my_stack)
输出:
['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() 方法逐个插入元素。那类似于推()的方法。我们还使用 pop() 方法移除了元素。 pop() 方法返回列表的最后一个元素。
使用 collection.deque 实现
collections模块提供了 deque 类，用于创建 Python 栈。德格发音为“甲板”，意思是“双头队列”。deque 比列表更受欢迎，因为它比列表执行追加和弹出操作更快。时间复杂度为 O(1)，其中列表取 O(n)。
让我们理解下面的例子-
例
from collections import deque
my_stack = deque()
# append() function is used to push
# element in the my_stack
my_stack.append('a')
my_stack.append('b')
my_stack.append('c')
print('Initial my_stack:')
print(my_stack)
# pop() function is used to pop
# element from my_stack in
# LIFO order
print('nElements poped from my_stack:')
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print('nmy_stack after elements are poped:')
print(my_stack)
输出:
Initial my_stack:
deque(['a', 'b', 'c'])
Elements poped from my_stack:
c
b
a
my_stack after elements are poped:
deque([])
说明:
上面的代码几乎与前面的例子相似。但是，唯一不同的是，我们已经从collections模块中导入了 deque。
双队列与列表
该列表将元素紧挨着存储，并使用连续的内存。这对于几个操作来说是最有效的，比如索引列表。例如-获取列表 1【2】很快，因为 Python 知道特定元素的确切位置。连续内存还允许切片在列表中很好地工作。
列表比其他对象消耗更多的时间来追加一些对象。如果连续内存块已满，它将获得另一个比正常的 append() 函数花费更长时间的块。
使用queue模块实现
queue模块有后进先出队列，与栈相同。通常，队列使用put()方法添加数据，使用方法获取数据。
下面是队列中可用的几种方法。
- 空()- 如果队列为空，返回真；否则返回 false。
- maxsize() - 此方法用于设置队列中允许的最大元素数量。
- get() - 它返回并从队列中移除元素。有时间。队列可以为空；它一直等到元素可用。
- 已满()- 如果队列已满，则返回真。默认情况下，队列被定义为 maxsize = 0。在这种情况下，它不会返回真。
- put(item) - 它将元素添加到队列中；如果队列已满，请等待直到空间可用。
- put_nowait(item) - 它不延迟地将元素添加到队列中。
- qsize() - 返回队列的大小。
让我们理解queue模块的以下示例。
示例-
# Implementing stack using the queue module
from queue import LifoQueue
# Initializing a my_stack stack with maxsize
my_stack = LifoQueue(maxsize = 5)
# qsize() display the number of elements
# in the my_stack
print(my_stack.qsize())
# put() function is used to push
# element in the my_stack
my_stack.put('x')
my_stack.put('y')
my_stack.put('z')
print("Stack is Full: ", my_stack.full())
print("Size of Stack: ", my_stack.qsize())
# To pop the element we used get() function
# from my_stack in
# LIFO order
print('nElements poped from the my_stack')
print(my_stack.get())
print(my_stack.get())
print(my_stack.get())
print("nStack is Empty: ", my_stack.empty())
输出:
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 栈的程序。
答案是我们可以使用后进先出队列，我们知道后进先出代表什么。它使用 put() 和get()来添加和移除栈元素。
栈的哪个实现应该考虑？
我们已经提到了三种在 Python 中实现栈的方法。以上方法各有利弊。
让我们消除困惑；我们使用的是带线程的栈，你应该使用 Lifoqueue ，但是要确保它的弹出和推送元素的性能。但是如果你不使用穿线，请使用德克尔。
我们也可以使用列表来实现栈，但是列表可能会有潜在的内存重新分配问题。列表和 de quee 在界面中是相同的，但是 de quee 没有内存分配问题。
结论
我们已经简单定义了栈及其实现。Python 栈可以用于现实生活中的程序。我们可以根据自己的需求选择实现方法。我们还定义了带有线程环境的 Python 栈。