Queue

last update: 2025-06-09

Queue 是一種先進先出（FIFO, First In First Out）的資料結構，常用於模擬排隊或任務排程的場景。每個元素依照加入的順序被處理，最先加入的元素最先被移除。

---

一、Queue 的組成與限制

屬性	說明
head	指向佇列最前端的節點（即將被移除的元素）
tail	指向佇列最後端的節點（最後加入的元素）
size	當前佇列中的元素數量
max_size	佇列可容納的最大元素數量（可選）

---

二、基本節點結構（Python 範例）

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

---

三、Queue 操作

1. 加入元素（enqueue）

def enqueue(self, value):
    if self.has_space():
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
    else:
        print("Queue is full!")

2. 移除元素（dequeue）

def dequeue(self):
    if self.size > 0:
        value = self.head.value
        self.head = self.head.next
        self.size -= 1
        if self.size == 0:
            self.tail = None
        return value
    else:
        print("Queue is empty!")

3. 查看最前端元素（peek）

def peek(self):
    if self.size > 0:
        return self.head.value
    else:
        print("Queue is empty!")

---

四、輔助方法與屬性

def get_size(self):
    return self.size

def has_space(self):
    return self.max_size is None or self.size < self.max_size

def is_empty(self):
    return self.size == 0

---

五、Queue 特性

• 先進先出（FIFO）：最早加入的元素最早被移除

• 空間彈性：可設置最大容量限制 max_size

• 適用場景：排隊處理、任務排程、印表機任務佇列等

---

六、Queue vs Stack 比較

特性	Queue	Stack
操作順序	FIFO（先進先出）	LIFO（後進先出）
插入端	尾端	頂端
移除端	前端	頂端
適用場景	排隊、廣度優先搜尋	遞迴、深度優先搜尋

---

Queue 是基礎但實用的資料結構，常用於需要「順序處理」的場景。在實作時，可以用陣列、串列、或雙端佇列等結構實現，若需擴展可進一步學習 circular queue、priority queue 等變形。