Python 中的雙端隊列——帶示例的教程

如果您是 Python 開發人員，您可能聽說過雙端隊列或“雙端隊列”。它是一個強大的工具，可以提高應用程序的效率並加快其性能。

雙端隊列是一種專門的容器數據類型，可以從容器的兩端提供更快的追加和彈出操作。這使它成為實現隊列和堆棧的有價值的工具，它們是計算中常見的類似列表的數據類型。

它是一種低級且高度優化的數據結構，對各種應用程序非常有用。作為一名 Python 程序員，雙端隊列是您希望在您的武器庫中擁有的一種工具。

繼續閱讀以了解有關 Deques 的更多信息以及如何在Python 代碼中實現它們！

目錄

• 什麼是雙端隊列？
  • Python 雙端隊列的特性
  • 雙端隊列的應用
• 如何創建和初始化雙端隊列
  • 使用 deque() 函數
  • 用元素初始化雙端隊列
• 如何執行常見的雙端隊列操作
  • 向雙端隊列添加元素
  • 向雙端隊列添加多個數據元素
  • 從雙端隊列中刪除元素
  • 從雙端隊列中刪除所有元素
  • 訪問雙端隊列的元素
  • 修改雙端隊列的元素
• 如何將雙端隊列用作隊列
  • 使用 append() 和 popleft() 方法
  • 檢查雙端隊列是否為空
• 使用 Deque 作為堆棧
  • 使用 append() 和 pop() 方法
  • 檢查空雙端隊列對象
• 什麼是受限雙端隊列？
  • • 輸入限制雙端隊列
    • 輸出受限雙端隊列
• 讓我們總結一下

什麼是雙端隊列？

如果您是 Python 或一般計算機編程的新手，您可能想知道雙端隊列是什麼。Deque 代表“雙端隊列”，它是一種數據結構，允許您從隊列的兩端添加和刪除元素。

它類似於常規隊列，但增加了靈活性，能夠從隊列的前端和後端添加和刪除元素。這是可能的，因為 Python 的雙端隊列是作為雙向鍊錶實現的。

在 Python 中，雙端隊列是使用 collections 模塊實現的，它提供了一個雙端隊列類。此類提供了許多用於在雙端隊列中添加和刪除元素的方法。

它還為其他有用的操作提供函數，例如旋轉雙端隊列或完全清除它。

Python 雙端隊列的特性

與普通列表的附加和彈出操作具有 O(n) 時間複雜度不同，雙端隊列提供 O(1) 時間複雜度。這使得這些讀寫操作的速度和內存效率顯著提高。

以下是您應該了解的更多 Python 雙端隊列功能：

• 它是一個可變的數據結構。

• 它可以存儲多種數據類型，例如整數、元組、數組等。

• 它支持索引，但不支持切片操作。

• 它不支持就地排序

• 它支持常見的內置可迭代函數和操作，如in、sorted()、len()、reverse()等。

雙端隊列的應用

出於多種原因，雙端隊列很有用。例如，它們可用於實現隊列或堆棧，這兩者都是計算機科學中常見的數據結構。

它們還可用於高效地實時處理數據，例如在流式應用程序或需要快速訪問數據的系統中。

除了用於隊列和棧之外，雙端隊列還可以用於實現廣度優先搜索算法。它們對於維護較大序列中項目的滑動窗口也很有用。

如何創建和初始化雙端隊列

您可以使用 collections 模塊中的內置函數創建雙端隊列。讓我們仔細看看如何創建和填充此數據結構。

使用 deque() 函數

要在 Python 中創建雙端隊列，您可以使用collections 模塊中的內置deque()函數。此函數返回一個新的空 deque 對象，您可以使用它來實現雙端隊列。

下面是一個如何創建空雙端隊列對象的示例：

from collections import deque 

my_deque = deque() 

您還可以通過將可迭代對象（列表、元組等）傳遞給deque()函數來創建具有初始元素的雙端隊列。雙端隊列將使用可迭代對像中的元素從左到右進行初始化。

這是一個例子：

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

用元素初始化雙端隊列

您還可以使用各種方法用元素初始化一個空的雙端隊列。一種方法是使用append()和appendleft()方法分別從右側和左側向雙端隊列添加元素。

這是一個例子：

from collections import deque

#Initialize the empty deque
my_deque = deque()
print(my_deque)

#Add Values to the deque
my_deque.append(1) 
my_deque.append(2) 
my_deque.appendleft(3) 

print(my_deque)

運行此代碼後，雙端隊列將包含元素[3, 1, 2]。

用元素初始化雙端隊列的另一種方法是將元素列表傳遞給deque()函數。

這是一個例子：

from collections import deque

my_deque = deque([1, 2, 3]) 

運行此代碼將創建一個包含元素[1, 2, 3]的雙端隊列對象。

總體而言，在 Python 中創建和初始化雙端隊列非常簡單，可以使用內置的deque()函數完成。您也可以通過使用append()和appendleft()方法將元素添加到一個空雙端隊列來實現。

如何執行常見的雙端隊列操作

您可以在 Python 中對雙端隊列對象執行許多操作。讓我們看看一些更受歡迎的。

向雙端隊列添加元素

您可以使用append()和appendleft()方法將元素添加到Python雙端隊列。append ()方法將一個元素添加到雙端隊列的右端，而appendleft()方法將一個元素添加到雙端隊列的左端。

這是一個例子：

import collections 

# Create an empty deque 
my_deque = collections.deque() 

# Add elements to the deque 
my_deque.append(1) 
my_deque.appendleft(2) 
my_deque.append(3) 

print(my_deque) 

# Output: 
deque([2, 1, 3])

向雙端隊列添加多個數據元素

如果您不想將數據元素一個一個地添加到雙端隊列，您可以使用extend()或extendleft()函數加快該過程。這些函數接受一個可迭代對象並將可迭代對象的內容分別附加到雙端隊列的末尾或左端。

這是一個例子：

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

#Creating a tuple and list
cont = (11, 12, 13, 14)
full = [10,20,30]

#Extending the deque from the right
my_deque.extend(cont)
print(my_deque)

#Extending the deque from the left
my_deque.extendleft(full)
print(my_deque)

在上面的代碼中，extend()函數將連續元組中的多個值附加到雙端隊列的末尾。接下來，extendleft()函數將完整列表中的多個數據元素附加到雙端隊列的左端。

從雙端隊列中刪除元素

您可以使用pop()和popleft()方法從 Python 雙端隊列中刪除元素。pop ()方法移除並返回雙端隊列最右邊的元素，而popleft()方法移除並返回雙端隊列最左邊的元素。

這是一個例子：

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

#Remove elements from the deque 
my_deque.pop() 
my_deque.popleft() 

print(my_deque) 

# Output: deque([2, 3, 4])

您還可以使用remove()函數從雙端隊列中刪除特定值。該函數從雙端隊列中刪除第一次出現的指定值。

這是一個例子：

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 1, 4, 5]) 

#Remove elements from the deque 
my_deque.remove(1)

print(my_deque) 

# Output: deque([2, 1, 4, 5])

如果未找到該元素，Python 將返回ValueError。

從雙端隊列中刪除所有元素

要從雙端隊列中刪除所有元素並將其返回到空狀態，我們可以使用clear()函數。它是這樣工作的：

from collections import deque 

#Create a deque with some elements 
my_deque = deque([1, 2, 1, 4, 5]) 

#Remove all elements from the deque 
my_deque.clear()

print(my_deque) 

# Output: 
deque([])

訪問雙端隊列的元素

您可以使用索引運算符[]訪問 Python 雙端隊列的元素。您還可以在索引運算符中使用負值來從右側訪問雙端隊列元素。

對於最左邊的元素，索引從 0 開始，對於最右邊的元素，索引從 -1 開始。這是一個例子：

import collections 

# Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

# Access elements of the deque 
print(my_deque[0]) 
# Output: 1 

print(my_deque[-1]) 
# Output: 5 

修改雙端隊列的元素

您可以使用索引運算符“ [] ”和賦值運算符“ = ”修改 Python 雙端隊列的元素。這是一個例子：

from collections import deque

# Create a deque with some elements 
my_deque = deque([1, 2, 3, 4, 5]) 
print(my_deque)

# Modify elements of the deque 
my_deque[0] = 10 
my_deque[-1] = 50 

print(my_deque) 

在上面的代碼中，索引運算符將雙端隊列的第一個和最後一個元素分別更改為 10 和 50。

這些是您可以在 Python 中對雙端隊列對象執行的基本操作。通過這些操作，您可以高效地實現隊列、堆棧等各種數據結構。

如何將雙端隊列用作隊列

您可以在 Python 中使用雙端隊列來實現隊列數據結構。隊列是一種抽像數據類型，它以先進先出 (FIFO) 的方式運行。

這意味著您可以從隊列的一端追加新項目並從另一端推出舊項目。

解釋這一點的一個好方法是在商店排隊。通常，第一個到達的人會排在隊伍的最前面，並且會首先得到照顧。

新來的人必須排到隊伍的後面等待輪到他們。因此，第一個進來的將是第一個回答的，而最後一個進來的將是最後一個被注意到的。

下面介紹如何使用雙端隊列來實現隊列。

使用 append() 和 popleft() 方法

要將雙端隊列用作隊列，可以使用append()方法將元素添加到雙端隊列的右端。此外，您可以使用popleft()方法從雙端隊列的左端刪除元素。

這是在 Python 中實現隊列的一種非常有效的方法。這是一個例子：

from collections import deque 

queue = deque() 
queue.append(1) 
queue.append(2) 
queue.append(3) 

print(queue) 
# Output: deque([1, 2, 3]) 

x = queue.popleft() 
print(x) 
# Output: 1 

print(queue) 
# Output: deque([2, 3]) 

如您所見，append()方法將元素添加到雙端隊列的右端，而popleft()方法從雙端隊列的左端移除元素。

這正是我們在隊列實現中所需要的。

檢查雙端隊列是否為空

要檢查雙端隊列是否為空，可以使用not運算符。這是一個例子：

from collections import deque 

queue = deque() 
if not queue: 
   print("Queue is empty") 
else: 
   print("Queue is not empty") 

這將輸出“ Queue is empty ”，因為雙端隊列是空的。如果向雙端隊列添加元素，它將不再為空。

總之，在 Python 中使用雙端隊列作為隊列是非常高效且易於實現的。

使用 Deque 作為堆棧

就像隊列一樣，堆棧是可用於組織數據的抽像數據類型的另一個示例。與隊列不同，堆棧以後進先出 (LIFO) 方式運行。

這意味著進入雙端隊列的最後一個元素將是第一個出來的元素。以下是如何使用底層數據結構實現它。

使用 append() 和 pop() 方法

將 Deque 用作堆棧時，可以使用append()方法將元素添加到堆棧的頂部。此方法將元素添加到雙端隊列的右端。

同樣，您可以使用pop()方法從堆棧頂部移除元素。此方法刪除並返回雙端隊列最右邊的元素。

例如，假設您有一個名為“ my_stack ”的雙端隊列，並且您想要將一個元素添加到堆棧的頂部。您可以使用以下代碼：

 my_stack.append(5) 

這會將元素 5 添加到堆棧的頂部。

如果你想從棧中移除棧頂元素，你可以使用 pop() 方法：`

bal = my_stack.pop() 

print(bal)
# Output: 5

這將刪除並返回雙端隊列最右邊的元素，在本例中為 5。

檢查空雙端隊列對象

您可以使用布爾運算符“ not ”檢查雙端隊列堆棧是否為空。如果雙端隊列為空，“ not my_deque ”將返回True。否則，它將返回False。

例如，假設您有一個名為“ my_deque ”的雙端隊列堆棧，您想要檢查它是否為空。您可以使用以下代碼：

if not my_deque: 
   print("The deque is empty") 

else: 
   print("The deque is not empty") 

如果雙端隊列是空的，這將打印“雙端隊列是空的”。如果它不為空，輸出將是“雙端隊列不為空”。

將 Deque 作為堆棧使用時，跟踪堆棧是否為空很重要。如果您嘗試從空堆棧中彈出一個元素，您將得到一個IndexError。

什麼是受限雙端隊列？

受限雙端隊列是雙端隊列，對雙端隊列兩端的數據追加和彈出操作有一些限制。有兩種主要類型的受限雙端隊列；輸入受限雙端隊列和輸出受限雙端隊列

讓我們看看它們：

輸入限制雙端隊列

輸入受限的雙端隊列允許您從雙端隊列的兩端彈出或刪除數據元素。但是，您只能從雙端隊列的一端插入數據元素。

這在具有內存限制的應用程序中非常有用。您可以使用它按時間順序添加數據元素，同時保留從雙端隊列的任何一端丟棄數據的能力。

輸出受限雙端隊列

輸出受限雙端隊列允許您從雙端隊列的兩端插入數據。但是，您只能從稱為前端的雙端隊列的一端刪除項目。

輸出受限的雙端隊列在需要實現 FIFO 數據結構但仍希望從兩端追加數據的功能時非常有用。

讓我們總結一下

到目前為止，您應該對 Python 中的 deque 模塊以及如何使用它來實現高效的隊列和堆棧有了很好的理解。

雙端隊列是一種多功能數據結構，與傳統列表相比具有許多優勢。當涉及到內存高效的追加和彈出操作時，這些優勢是顯而易見的。

當您需要實現堆棧或雙端隊列時，它們也是一個不錯的選擇。使用雙端隊列的一些主要好處包括：

• 雙端隊列兩端的高效 O(1) 追加和彈出操作

• 快速 O(1) 訪問雙端隊列的第一個和最後一個元素

• 對線程安全的原子操作的內置支持

• 在雙端隊列中插入、移除和旋轉元素的靈活方法

總的來說，deque 模塊是一個強大的工具，可以幫助您編寫更高效和可維護的 Python 代碼。無論您是在處理小型腳本還是大型項目，雙端隊列絕對值得考慮作為傳統列表或其他數據結構的替代品！

準備好了解更多關於 Python 的信息，請查看下面的播放列表