在之前的教學中，已經學會了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