Python中的栈

Python中的栈

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

什么是栈

栈是一种线性数据结构，其中的数据按照一层层地排列。它以LIFO（后进先出）的方式存储数据。数据的存储顺序与厨房里的盘子一样，一个盘子放在另一个盘子上面。一个简单的栈的示例是编辑器中的”撤销”功能。撤销功能是基于我们最后完成的事件进行操作的。

我们总是从栈的最后一个盘子开始取。在栈中，新元素被插入到一端，只能从同一端删除元素。

我们可以对栈执行两个操作 – 推入（PUSH） 和 弹出（POP） 。推入操作是添加元素，而弹出操作是从栈中删除元素。

栈的方法

Python提供了一些常用于栈的方法。

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

栈的实现

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

我们可以用以下方法在Python中实现栈。

• 列表（List）
• 双端队列（deque）
• 优先队列（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() 方法逐个插入元素，这与 push() 方法类似。我们还使用 pop() 方法删除元素。 pop() 方法返回列表的最后一个元素。

使用collection.deque实现

collection模块提供了deque类，用于创建Python 堆栈 。deque的发音为”deck”，意思是”double-ended queue”，即双端队列。与列表相比，deque更适合用于执行append和pop操作，因为它的性能更好。时间复杂度为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与list的区别

list将元素存储在彼此相邻的位置，并使用连续的内存。这对于诸如索引列表之类的操作非常有效。例如 – 获取 list1[2] 是快速的，因为Python知道特定元素的确切位置。连续的内存还使得切片在列表上运行良好。

list比其他一些对象在 append() 上消耗更多时间。如果连续内存块已满，则会获取另一个块，这可能花费比正常 append() 函数更长的时间。

使用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()方法是原子性的，这意味着它们不会被其他线程中断。

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

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

答案是我们可以使用 LIFOqueue ，而我们知道LIFO代表的是后进先出。它使用put()和get()来添加和删除堆栈元素。

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

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

让我们澄清混淆；如果我们在线程中使用堆栈，您应该使用 Lifoqueue ，但要确保它在弹出和推入元素时的性能。但是，如果您不使用线程，请使用 deque 。

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

结论

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