在之前的教學中，已經學會了Node和Linked List的實作，
用Python實現了單向鏈結串列Singly linked list、雙向鏈結串列Doubly linked list。
今天要承接之前打下的基礎，用雙向鏈結串列來實作Queue(佇列 或稱 隊列)。
定義
是一個線性長條狀的資料結構。
規定推入資料都是從尾端(Rear)進入，取出資料都必須在頭部(Front)取出。
(就像去餐廳吃飯，或者 排隊買東西，
新客人從隊伍的尾巴開始排隊，而商家從隊伍最前面的客人開始服務。)
也由於這項規定，Queue先天具有先進先出First-in First-out的這種特質。
支援的操作與介面
queue.enqueue(data)
推入一筆新資料data進入queue的尾端。
queue.front()
取得queue頭部目前的資料。
queue.dequeue()
取得queue頭部目前的資料，並且將此資料從queue移除。
len( queue )
取得queue的大小，也就是現在有幾筆資料存在queue裡。
queue.is_empty()
判斷stack是否為空。
優點
1.在尾巴新增資料是O(1) 常數時間。
2.在頭部取得資料是O(1) 常數時間。
3.在頭部移除資料是O(1) 常數時間。
4.可以根據需求動態延伸或縮短，有效利用記憶體空間。
缺點
1.不支援random acess，不支援Queue[ index ] 這種操作。
2.如果要取得內部的資料，必須先將頭部的資料依序移除。
Queue的class定義 與 建構子(初始化函式)
class Queue:
def __init__(self):
self.queue = LinkedList()
Queue常見的function實現
1.在queue尾巴插入新玩素
直接在queue尾巴放入新元素，對應的底層實作就是在尾巴串上新結點。
時間複雜度: O(1) 常數時間
def enqueue(self, data):
self.queue.insertAtTail(data)
return
2.讀取queue頭部玩素
直接返回queue頭部的元素，對應的底層實作就是在返回頭部結點的資料。
實作上有個細節需要留意，假如stack是空的，直接返回None即可。
時間複雜度: O(1) 常數時間
def front(self):
if self.queue.head is None:
return None
return self.queue.head.data
3.從queue頭部取出舊元素
直接返回並且移除queue頭部的元素，
對應的底層實作就是返回並且移除頭部結點的資料。
時間複雜度: O(1) 常數時間
def dequeue(self):
return self.queue.removeAtHead()
4.取得queue的長度
返回queue的長度，也代表queue內部資料的總數量。
對應的底層實作就是在返回串列的長度。
時間複雜度: O(1) 常數時間
def __len__(self):
return len(self.queue)
5.檢查queue是否為空
如果queue的長度為0，代表queue是空的，內部沒有任何資料。
時間複雜度: O(1) 常數時間
def is_empty(self):
return 0 == self.queue.size
完整的Queue實作和程式碼，
底層是Doubly Linked List雙向鏈結串列。
class Node:
def __init__(self, data):
# 儲存節點的資料
self.data = data
# 指向下一個節點，初始化為空 None
self.next = None
# 指向前一個節點，初始化為空 None
self.prev = None
class LinkedList:
def __init__(self):
# 頭部節點初始化為空
self.head = None
# 尾巴節點初始化為空
self.tail = None
# 串列長度初始化為0
self.size = 0
def insertAtHead(self,data):
new_node = Node(data)
self.size += 1
# If the list is empty
if self.tail is None:
self.head = new_node
self.tail = new_node
else:
# Update linkage
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
return
def insertAtTail(self, data):
new_node = Node(data)
self.size += 1
# If the list is empty
if self.head is None:
self.head = new_node
self.tail = new_node
else:
# Update linkage
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
return
def removeAtHead(self):
if self.head is None:
return
else:
self.size -= 1
oldHead = self.head
# Update linkage
if self.head == self.tail:
self.tail = None
self.head = None
else:
self.head = self.head.next
# Break linkage
oldHead.next = None
if self.head:
self.head.prev = None
return oldHead
def removeAtTail(self):
if self.tail is None:
return
else:
self.size -= 1
oldTail = self.tail
# Update linkage
if self.tail == self.head:
self.tail = None
self.head = None
else:
self.tail = self.tail.prev
# Break linkage
oldTail.prev = None
if self.tail:
self.tail.next = None
return oldTail
def traverse(self):
print("Forward traversal")
cur = self.head
while cur:
print(cur.data, end=' <-> ')
cur = cur.next
print("None")
print(f"Size of singly linked list: {self.size} \n", )
return
def backward_traverse(self):
print("Backward traversal")
cur = self.tail
while cur:
print(cur.data, end=' <-> ')
cur = cur.prev
print("None")
print(f"Size of singly linked list: {self.size} \n", )
return
def search(self, target):
cur = self.head
while cur:
if cur.data == target:
return cur
cur = cur.next
return None
def removeAfter(self, node):
self.size -= 1
removed = node.next
the_one_after_removal = node.next.next if node.next else None
# Update linkage
if the_one_after_removal:
the_one_after_removal.prev = node
node.next = the_one_after_removal
# Break linkage
if removed:
removed.next = None
removed.prev = None
return removed
def insertAfter(self, node, new_node):
self.size += 1
the_one_after_insertion = node.next
# Update linkage
node.next = new_node
new_node.prev = node
the_one_after_insertion.prev = new_node
new_node.next = the_one_after_insertion
return
def __contains__(self, item):
cur = self.head
while cur:
if cur.data == item:
return True
cur = cur.next
return False
def __len__(self):
return self.size
class Queue:
def __init__(self):
self.queue = LinkedList()
def enqueue(self, data):
self.queue.insertAtTail(data)
return
def dequeue(self):
return self.queue.removeAtHead()
def front(self):
if self.queue.head is None:
return None
return self.queue.head.data
def is_empty(self):
return 0 == self.queue.size
def __len__(self):
return len(self.queue)
def __contains__(self, item):
return item in self.queue
def traverse(self):
self.queue.traverse()
return
def test():
print(f"Empty queue\n")
queue = Queue()
for i in range(1, 5):
print(f"Push {i}...")
queue.enqueue(i)
print()
print(f"Is stack empty? {queue.is_empty()}")
print(f"Size of stack: { len(queue) } ")
print()
for i in range(1,6):
print(f"Is {i} in stack? = { i in queue}")
print()
queue.traverse()
for _ in range( len(queue) ):
print(f"Front of queue = {queue.front()}")
print(f"Dequeue {queue.front()} ...\n")
queue.dequeue()
print(f"Is stack empty? {queue.is_empty()}")
return
if __name__ == "__main__":
test()
測試輸出
Empty queue
Push 1...
Push 2...
Push 3...
Push 4...
Is stack empty? False
Size of stack: 4
Is 1 in stack? = True
Is 2 in stack? = True
Is 3 in stack? = True
Is 4 in stack? = True
Is 5 in stack? = False
Forward traversal
1 <-> 2 <-> 3 <-> 4 <-> None
Size of singly linked list: 4
Front of queue = 1
Dequeue 1 ...
Front of queue = 2
Dequeue 2 ...
Front of queue = 3
Dequeue 3 ...
Front of queue = 4
Dequeue 4 ...
Is stack empty? True
結語
這篇我們透過Linked List作為底層的輔助資料結構，來實現完整的Queue class 和 interface function。
讀者可以搭配先前的教學文章，一起復習相關的資料結構。
也可以和Stack做一個對照，比較兩者之間的相同和相異之處。
Queue相關的演算法練習題與詳解
應用題 用Queue實作Stack_Leetcode #225 Implement Stack using Queues
應用題 用Stack實作Queue_Leetcode #232 Implement Queue using Stacks
資料結構實作題 環狀佇列 Design Circular Queue Leetcode #622
