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

undefined on Tenor

在之前的教學中，已經學會了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佇列，示意圖與程式碼如下。

示意圖

程式碼

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