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

  • 列表（List）
  • 双端队列（deque）
  • LifoQueue

使用列表实现

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() 方法逐个插入元素，这类似于 push() 方法。我们还使用 pop() 方法删除元素。pop() 方法返回列表的最后一个元素。

使用collection.deque实现

collection模块提供了deque类，用于创建Python的堆栈。deque的发音是“deck”，意思是“双端队列”。与列表相比，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([])

解释：

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

deque与列表的比较

列表将元素存储在紧邻的位置，并使用连续的内存。这对于许多操作（如索引列表）非常有效。例如 - 获取 list1[2] 的操作速度很快，因为Python知道特定元素的确切位置。连续的内存还使得切片在列表上很好地工作。

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

使用queue模块实现

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

以下是队列中可用的一些方法。

  • empty() - 如果队列为空，则返回True；否则返回False。
  • maxsize() - 此方法用于设置队列中允许的最大元素数。
  • get() - 返回并删除队列中的元素。有时队列可能为空，它会等待直到元素可用。
  • full() - 如果队列已满，则返回True。默认情况下，队列定义为maxsize = 0。在这种情况下，它不会返回True。
  • 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()方法是原子的，这意味着它们不会被其他线程中断。

我们可以使用LIFOqueue来构建多线程程序，而且我们知道LIFO代表什么 - 后进先出。它使用put()和gets()来添加和移除堆栈元素。

应该考虑哪种堆栈实现方法？

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

让我们澄清一下，如果我们在线程中使用堆栈，应该使用Lifoqueue，但要确保其在弹出和推入元素方面的性能。但如果您不使用线程，可以使用deque。

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

结论

我们已经简要介绍了堆栈及其实现。Python堆栈可以在实际程序中使用。我们可以根据需求选择实现方法。我们还介绍了在线程环境中使用Python堆栈的方法。

标签: Tkinter教程, Tkinter安装, Tkinter库, Tkinter入门, Tkinter学习, Tkinter入门教程, Tkinter, Tkinter进阶, Tkinter指南, Tkinter学习指南, Tkinter进阶教程, Tkinter编程