🔗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
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
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
Thumbnail
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
Thumbnail
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
Thumbnail
Array 在記憶體中連續分配,而且元素類型是一樣的,長度不變 優點:讀取快,可以使用座標訪問 缺點:新增、刪除慢 記憶體: 📷 範例程式碼: ArrayList 不定長度,在記憶體中連續分配的,元素沒有類型限制,任何元素都是當成object處理,如果是值類型,會有裝箱的操作 優點:讀取快 缺點:
Thumbnail
Array 在記憶體中連續分配,而且元素類型是一樣的,長度不變 優點:讀取快,可以使用座標訪問 缺點:新增、刪除慢 記憶體: 📷 範例程式碼: ArrayList 不定長度,在記憶體中連續分配的,元素沒有類型限制,任何元素都是當成object處理,如果是值類型,會有裝箱的操作 優點:讀取快 缺點:
Thumbnail
陣列是Python語言的最基礎也最容易實作的資料結構,主要可以透過兩種方式在Python上實踐陣列,其中一種是靜態結構 - 串列(List),另一種則是動態結構 - 鏈結串列(Linked List)。 我們會依序介紹這兩種作法如何在Python上執行陣列的相關功能,並比較兩種方法之間的差異。
Thumbnail
陣列是Python語言的最基礎也最容易實作的資料結構,主要可以透過兩種方式在Python上實踐陣列,其中一種是靜態結構 - 串列(List),另一種則是動態結構 - 鏈結串列(Linked List)。 我們會依序介紹這兩種作法如何在Python上執行陣列的相關功能,並比較兩種方法之間的差異。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News