🔗Python deque 與 Queue 相關的常用操作

更新於 發佈於 閱讀時間約 7 分鐘

在之前的教學中,已經學會了Node和Linked List的實作,

用Python實現了單向鏈結串列Singly linked list雙向鏈結串列Doubly linked list

並且用雙向鏈結串列來實作Queue(佇列 或稱 隊列)


今天要從Python 內建deque資料結構的角度切入,當作複習,
同時了解deque 與 FIFO Queue相關的function用法。


在Python中,collections.deque是一種兩端點皆可進出的雙端佇列
(double-ended queue),允許在兩端點高效地在O(1)常數時間內添加和刪除元素。

這使得deque非常適合實現FIFO Queue(FIFO代表First In First Out 先進先出)。


以下是有關deque和FIFO Queue相關的function操作教學及範例。


什麼是deque?

  • 定義deque是一種長度可伸縮的的長條鏈狀資料結構,
    支援從兩個端點添加或刪除元素,具有O(1)的常數時間複雜度。

deque 的基本操作

1.建立一個deque

from collections import deque

# 方法1: 建立一個空的deque
my_deque = deque()

# 方法2: 建立一個deque,並且以[1,2,3]最為初始值
my_deque = deque([1, 2, 3])
print(my_deque) # 輸出: deque([1, 2, 3])


2.新增元素

  • append():在右端點新增元素。
  • appendleft():在左端點新增元素。
my_deque.append(4)         # 在右端點新增4
my_deque.appendleft(0) # 在左端點新增0
print(my_deque) # 輸出: deque([0, 1, 2, 3, 4])


3.刪除元素

  • pop():從右端點刪除元素。
  • popleft():從左端點刪除元素。
my_deque.pop()             # 從右端點刪除元素4
print(my_deque) # 輸出: deque([0, 1, 2, 3])

my_deque.popleft() # 從左端點刪除元素0
print(my_deque) # 輸出: deque([1, 2, 3])


4.取得元素總數量

  • len():相當於 deque目前的長度,也就是元素總數量。
															# 目前deque = ([1, 2, 3]) 裡面總共有三個元素
print( len(my_deque) ) # 輸出: 3



FIFO Queue 佇列的實現

我們可以使用deque來實現一個FIFO Queue佇列,示意圖與程式碼如下。


示意圖

raw-image


程式碼

from collections import deque

class MyQueue:

# 建構子 ​
def __init__(self):
self.queue = deque()

# 在尾巴新增新資料
def enqueue(self, item):
self.queue.append(item)

# 從頭部取出舊資料
def dequeue(self):
if not self.is_empty():
return self.queue.popleft()
else:
raise IndexError("dequeue from an empty queue")

# 得到目前位在排頭的資料​
def peek(self):
if not self.is_empty():
return self.queue[0]
else:
raise IndexError("peek from an empty queue")

#​ 檢查佇列是否為空
def is_empty(self):
return len(self.queue) == 0

# 取得佇列目前的長度 = Queue 目前擁有的資料總數
def __len__(self):
return len(self.queue)


測試範例

queue = MyQueue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print("Dequeued element:", queue.dequeue() ) # 輸出: Dequeued element: 1
print("Front element:", queue.peek() ) # 輸出: Front element: 2
print("Is queue empty?", queue.is_empty() ) # 輸出: Is queue empty? False
print("Queue size:", len(queue) ) # 輸出: Queue size: 2, 此時quque = ([2, 3])

Reference

[1] collections — Container datatypes — Python 3.13.0 documentation

留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/10/11
林燃(創作小說家)
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/27
井字遊戲(OOXX)的遊戲描述 Tic Tac Toe(井字遊戲)是經典的雙人棋盤遊戲,在一個3x3的方格中進行。 每回合兩個玩家輪流選一個位置,先讓自己的符號(是 X 或 O)在 水平線、垂直線或對角線上連成一線的玩家宣告獲勝。
Thumbnail
2024/09/27
井字遊戲(OOXX)的遊戲描述 Tic Tac Toe(井字遊戲)是經典的雙人棋盤遊戲,在一個3x3的方格中進行。 每回合兩個玩家輪流選一個位置,先讓自己的符號(是 X 或 O)在 水平線、垂直線或對角線上連成一線的玩家宣告獲勝。
Thumbnail
2024/09/23
深入探討圖(Graph)的基本概念 及 最短路徑Shortest Path的尋找。 我們專注於廣度優先搜尋(BFS)演算法,以等權圖的最短路徑為例, 詳細說明如何利用BFS從起點擴散到終點,並且提供詳細的程式碼範例。 透過實作,讀者能夠更清楚理解圖論及BFS的應用,並體會水波紋擴散模型的重要性。
Thumbnail
2024/09/23
深入探討圖(Graph)的基本概念 及 最短路徑Shortest Path的尋找。 我們專注於廣度優先搜尋(BFS)演算法,以等權圖的最短路徑為例, 詳細說明如何利用BFS從起點擴散到終點,並且提供詳細的程式碼範例。 透過實作,讀者能夠更清楚理解圖論及BFS的應用,並體會水波紋擴散模型的重要性。
Thumbnail
2024/09/15
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
2024/09/15
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
看更多
你可能也想看
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
佇列(queue)是一種線性的資料結構,特色是從一端插入資料,另一端讀取資料,資料讀取完後就從佇列中移除。插入資料進佇列稱為enqueue,讀取資料稱為dequeue。因為每筆資料都是從佇列的一端進入,從另一段離開,這個過程稱之為先進先出(Firt In First Out)。
Thumbnail
佇列(queue)是一種線性的資料結構,特色是從一端插入資料,另一端讀取資料,資料讀取完後就從佇列中移除。插入資料進佇列稱為enqueue,讀取資料稱為dequeue。因為每筆資料都是從佇列的一端進入,從另一段離開,這個過程稱之為先進先出(Firt In First Out)。
Thumbnail
從Python 內建deque資料結構的角度切入, 同時了解deque 與 FIFO Queue相關的function用法。 collections.deque是一種兩端點皆可進出的雙端佇列 在兩端點高效地在O(1)常數時間內添加和刪除元素。 這使得deque非常適合實現FIFO Queue
Thumbnail
從Python 內建deque資料結構的角度切入, 同時了解deque 與 FIFO Queue相關的function用法。 collections.deque是一種兩端點皆可進出的雙端佇列 在兩端點高效地在O(1)常數時間內添加和刪除元素。 這使得deque非常適合實現FIFO Queue
Thumbnail
在資料結構與演算法裡, 最簡單的線性資料結構除了list之外就是linked list鏈結串列了。 Linked list又有分為單向Singly linked list 和雙向Doubly linked list 在這篇文章,會從最基礎的Singly linked list開始講起。 定義
Thumbnail
在資料結構與演算法裡, 最簡單的線性資料結構除了list之外就是linked list鏈結串列了。 Linked list又有分為單向Singly linked list 和雙向Doubly linked list 在這篇文章,會從最基礎的Singly linked list開始講起。 定義
Thumbnail
在Python中,queue是一個非常有用的模块。 它提供了多種佇列(queue)實現,用於在多線程環境中安全地交換信息或者數據。 佇列(queue)是一種先進先出(FIFO)的數據結構,允許在佇列的一端插入元素,另一端取出元素。(FIFO 是First In, First Out 的縮寫)
Thumbnail
在Python中,queue是一個非常有用的模块。 它提供了多種佇列(queue)實現,用於在多線程環境中安全地交換信息或者數據。 佇列(queue)是一種先進先出(FIFO)的數據結構,允許在佇列的一端插入元素,另一端取出元素。(FIFO 是First In, First Out 的縮寫)
Thumbnail
題目會給我們一組定義好的Stack 堆疊的介面,要求底層用兩個或一個Queue來實現。 也就是說,要求我們用一個或兩個FIFO的Queues去實作出一個LIFO的Stack
Thumbnail
題目會給我們一組定義好的Stack 堆疊的介面,要求底層用兩個或一個Queue來實現。 也就是說,要求我們用一個或兩個FIFO的Queues去實作出一個LIFO的Stack
Thumbnail
題目會給我們一組定義好的Queue 佇列的介面,要求底層用兩個stack來實現。 也就是說,要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue
Thumbnail
題目會給我們一組定義好的Queue 佇列的介面,要求底層用兩個stack來實現。 也就是說,要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News