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 棧。

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/237522.html