---
# System prepended metadata

title: Data Structure / Queue
tags: [Data Structure]

---

# Data Structure / Queue

## 1. 基本概念

佇列（Queue）是一種遵循「先進先出」（First-In-First-Out, FIFO）原則的資料結構。就像排隊買電影票一樣，先到的人先被服務，後到的人需要等待前面的人完成後才能被服務。

在佇列中：
- 新元素永遠從尾端（Rear / Back）加入
- 移除元素永遠從前端（Front）進行
- 第一個被加入的元素會是第一個被取出的元素

## 2. 基本操作

- **`createQueue()`**：建立一個新的空佇列。
- **`enqueue()`**：將新元素加入佇列尾端。
- **`dequeue()`**：從佇列前端移除並回傳元素。
- **`peek()`**：查看佇列前端的元素但不移除。

## 3. 佇列的實作方式

### 3.1 使用陣列實作（Array-Based Implementation）

以下是使用陣列實作佇列的範例程式碼：

```java=
class QueueArrayBased {
    private int MAX_QUEUE = 50;
    private Object[] items;
    private int front, back, count;

    public QueueArrayBased() {
        items = new Object[MAX_QUEUE];
        front = 0;
        back = MAX_QUEUE - 1;
        count = 0;
    }

    // helper methods
    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == MAX_QUEUE;
    }

    // enqueue
    public void enqueue(Object newItem) throws QueueException {
        if (!isFull()) {
            back = (back + 1) % MAX_QUEUE;
            items[back] = newItem;
            count++;
        } else {
            throw new QueueException("Queue is full");
        }
    }

    // dequeue
    public Object dequeue() throws QueueException {
        if (!isEmpty()) {
            Object queueFront = items[front];
            front = (front + 1) % MAX_QUEUE;
            count--;
            return queueFront;
        } else {
            throw new QueueException("Queue is Empty");
        }
    }

    // peek
    public Object peek() throws QueueException {
        if (!isEmpty()) {
            return items[front];
        } else {
            throw new QueueException("Queue is Empty");
        }
    }

}

class QueueException extends Exception {
    public QueueException(String message) {
        super(message);
    }
}

public class DS {
    public static void main(String[] args) {
        QueueArrayBased queue = new QueueArrayBased();

        try {
            // Enqueue items
            queue.enqueue("Item 1");
            queue.enqueue("Item 2");
            queue.enqueue("Item 3");

            // Peek at the front item
            System.out.println("Front item: " + queue.peek());

            // Dequeue items
            System.out.println("Dequeued: " + queue.dequeue());
            System.out.println("Dequeued: " + queue.dequeue());

            // Peek again
            System.out.println("Front item after dequeues: " + queue.peek());

            // Dequeue the last item
            System.out.println("Dequeued: " + queue.dequeue());

            // Attempt to dequeue from empty queue
            System.out.println("Dequeued: " + queue.dequeue());

        } catch (QueueException e) {
            System.err.println("Queue operation error: " + e.getMessage());
        }
    }
}
```

### 3.2 使用鏈結串列實作（Linked List Implementation）

以下是使用循環鏈結串列實作佇列的範例：

```java=
class LinkedListBasedQueue {
    private class Node {
        Object item;
        Node next;

        Node(Object item) {
            this.item = item;
            this.next = null;
        }
    }

    private Node lastNode;

    public LinkedListBasedQueue() {
        lastNode = null;
    }

    // helper methods
    public boolean isEmpty() {
        return lastNode == null;
    }

    // enqueue
    public void enqueue(Object item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            newNode.next = newNode;
        } else {
            newNode.next = lastNode.next;
            lastNode.next = newNode;
        }

        lastNode = newNode;
    }

    // dequeue
    public Object dequeue() throws QueueException {
        if (!isEmpty()) {
            Node firstNode = lastNode.next;
            if (firstNode == lastNode) {
                lastNode = null;
            } else {
                lastNode.next = firstNode.next;
            }

            return firstNode.item;
        } else {
            throw new QueueException("Queue is Empty.");
        }
    }

    public Object peek() throws QueueException {
        if (!isEmpty()) {
            return lastNode.next.item;
        } else {
            throw new QueueException("Queue is Empty.");
        }
    }
}

class QueueException extends Exception {
    public QueueException(String message) {
        super(message);
    }
}

public class DS {
    public static void main(String[] args) {
        LinkedListBasedQueue queue = new LinkedListBasedQueue();

        try {
            // Enqueue items
            queue.enqueue("Item 1");
            queue.enqueue("Item 2");
            queue.enqueue("Item 3");

            // Peek at the front item
            System.out.println("Front item: " + queue.peek());

            // Dequeue items
            System.out.println("Dequeued: " + queue.dequeue());
            System.out.println("Dequeued: " + queue.dequeue());

            // Peek again
            System.out.println("Front item after dequeues: " + queue.peek());

            // Dequeue the last item
            System.out.println("Dequeued: " + queue.dequeue());

            // Attempt to dequeue from an empty queue
            System.out.println("Dequeued: " + queue.dequeue());

        } catch (QueueException e) {
            System.err.println("Queue operation error: " + e.getMessage());
        }
    }
}
```

## 4. 特殊類型的佇列

### 4.1 循環佇列（Circular Queue）

循環佇列使用固定大小的陣列，但是以循環方式使用空間。當到達陣列尾端時，下一個元素會被放置在陣列開始的位置（如果該位置為空）。

```java=
public class CircularQueue {
    private Object[] queue;
    private int front, rear;
    private boolean flag;  // 用於判斷佇列是否已滿
    private int size;

    public CircularQueue(int size) {
        this.size = size;
        queue = new Object[size];
        front = rear = 0;
        flag = false;
    }

    public void enqueue(Object item) throws QueueException {
        if (flag) {
            throw new QueueException("佇列已滿");
        }
        queue[rear] = item;
        rear = (rear + 1) % size;
        if (rear == front) {
            flag = true;
        }
    }

    public Object dequeue() throws QueueException {
        if (rear == front && !flag) {
            throw new QueueException("佇列為空");
        }
        Object item = queue[front];
        front = (front + 1) % size;
        flag = false;
        return item;
    }
}

class QueueException extends Exception {
    public QueueException(String message) {
        super(message);
    }
}
```

### 4.2 雙向佇列（Double-ended Queue，Deque）

雙向佇列允許在佇列的兩端（前端和後端）都進行插入和刪除操作，提供了較高的靈活性。請直接參考程式碼中的函數：

```java=
public class Deque<T> {
    private class Node {
        T data;
        Node prev;
        Node next;
        
        Node(T data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }
    
    private Node front;
    private Node rear;
    private int size;
    
    public Deque() {
        front = rear = null;
        size = 0;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    // 從前端加入元素
    public void addFirst(T item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            newNode.next = front;
            front.prev = newNode;
            front = newNode;
        }
        size++;
    }
    
    // 從後端加入元素
    public void addLast(T item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            newNode.prev = rear;
            rear = newNode;
        }
        size++;
    }
    
    // 從前端移除元素
    public T removeFirst() throws DequeException {
        if (isEmpty()) {
            throw new DequeException("雙向佇列為空");
        }
        T data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        } else {
            front.prev = null;
        }
        size--;
        return data;
    }
    
    // 從後端移除元素
    public T removeLast() throws DequeException {
        if (isEmpty()) {
            throw new DequeException("雙向佇列為空");
        }
        T data = rear.data;
        rear = rear.prev;
        if (rear == null) {
            front = null;
        } else {
            rear.next = null;
        }
        size--;
        return data;
    }
    
    // 查看前端元素
    public T getFirst() throws DequeException {
        if (isEmpty()) {
            throw new DequeException("雙向佇列為空");
        }
        return front.data;
    }
    
    // 查看後端元素
    public T getLast() throws DequeException {
        if (isEmpty()) {
            throw new DequeException("雙向佇列為空");
        }
        return rear.data;
    }
}

// customize Exception
class DequeException extends Exception {
    public DequeException(String message) {
        super(message);
    }
}
```

### 4.3 優先佇列（Priority Queue）

優先佇列中的元素都會被賦予優先次序。具有較高優先權的元素會比優先權較低的元素先被處理，即使它是後來才加入佇列的。

#### 4.3.1 特點
1. 元素都具有優先權值
2. 取出元素時會選擇優先權最高的
3. 相同優先權的元素按照先進先出原則處理
4. 常用堆積（Heap）資料結構來實作

以下是使用最小堆積（Min Heap）實作優先佇列的範例：

```java=
import java.util.ArrayList;

class PriorityQueue<T extends Comparable<T>> {
    private class PQNode implements Comparable<PQNode> {
        T data;
        int priority;

        PQNode(T data, int priority) {
            this.data = data;
            this.priority = priority;
        }

        @Override
        public int compareTo(PQNode other) {
            return this.priority - other.priority;
        }
    }

    private ArrayList<PQNode> heap;

    public PriorityQueue() {
        heap = new ArrayList<>();
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }

    // 加入具有優先權的元素
    public void enqueue(T item, int priority) {
        PQNode newNode = new PQNode(item, priority);
        heap.add(newNode);
        siftUp(heap.size() - 1);
    }

    // 取出優先權最高的元素
    public T dequeue() throws PriorityQueueException {
        if (isEmpty()) {
            throw new PriorityQueueException("優先佇列為空");
        }

        T result = heap.get(0).data;
        int lastIdx = heap.size() - 1;
        heap.set(0, heap.get(lastIdx));
        heap.remove(lastIdx);

        if (!isEmpty()) {
            siftDown(0);
        }

        return result;
    }

    // 向上調整堆積
    private void siftUp(int index) {
        while (index > 0) {
            int parentIdx = (index - 1) / 2;
            if (heap.get(index).compareTo(heap.get(parentIdx)) < 0) {
                swap(index, parentIdx);
                index = parentIdx;
            } else {
                break;
            }
        }
    }

    // 向下調整堆積
    private void siftDown(int index) {
        int size = heap.size();
        while (true) {
            int smallest = index;
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;

            if (leftChild < size && heap.get(leftChild).compareTo(heap.get(smallest)) < 0) {
                smallest = leftChild;
            }
            if (rightChild < size && heap.get(rightChild).compareTo(heap.get(smallest)) < 0) {
                smallest = rightChild;
            }

            if (smallest == index) {
                break;
            }

            swap(index, smallest);
            index = smallest;
        }
    }

    private void swap(int i, int j) {
        PQNode temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
}

// customize Exception
class PriorityQueueException extends Exception {
    public PriorityQueueException(String message) {
        super(message);
    }
}
```

#### 4.3.2 優先佇列的應用場景

1. **作業系統處理**
   - 處理程序排程
   - 中斷處理
   - 資源分配
2. **網路流量管理**
   - 封包優先權處理
   - QoS（服務品質）保證
3. **演算法應用**
   - Dijkstra 最短路徑演算法
   - Prim 最小生成樹演算法
   - 赫夫曼編碼
4. **即時系統**
   - 任務排程
   - 即時事件處理

---

#### 所以泥在 Main Class 裡面就可以醬：

```java=
public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<>();
        
        // 加入具有不同優先權的工作
        pq.enqueue("列印文件", 3);
        pq.enqueue("系統更新", 1);    // 較高優先權
        pq.enqueue("備份資料", 2);
        
        try {
            // 優先處理優先權較高的工作
            System.out.println("處理工作: " + pq.dequeue());  // 輸出：系統更新
            System.out.println("處理工作: " + pq.dequeue());  // 輸出：備份資料
            System.out.println("處理工作: " + pq.dequeue());  // 輸出：列印文件
        } catch (PriorityQueueException e) {
            System.out.println("錯誤：" + e.getMessage());
        }
    }
}
```

## 5. 佇列的應用

1. **作業系統工作排程**：
   - 處理具有相同優先權的工作
   - 印表機列印佇列（Printer Spooling）
2. **系統模擬**：
   - 事件驅動模擬（Event-driven Simulation）
   - 時間驅動模擬（Time-driven Simulation）
3. **緩衝區管理**：
   - 輸入/輸出緩衝
   - 資料流處理
4. **演算法應用**：
   - 圖形走訪中的廣度優先搜尋（Breadth-First Search）
   - 樹狀結構的層次走訪（Tree's Level-Order Traversal）

## 6. 效能考量

1. **空間使用效率**：
   - 陣列實作：固定大小，可能造成空間浪費
   - 鏈結串列實作：動態分配空間，較有彈性
2. **時間複雜度**：
   - Enqueue 操作：O(1)
   - Dequeue 操作：O(1)
   - **`isEmpty()`**：O(1)
3. **實作選擇考量**：
   - 如果佇列大小固定且可預期，使用陣列實作
   - 如果佇列大小動態變化，使用鏈結串列實作
   - 如果需要頻繁的插入 / 刪除，使用鏈結串列實作