Python 中的栈

在本教程中，我们将学习栈的基础知识，并使用 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 栈。