# 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. **實作選擇考量**：
- 如果佇列大小固定且可預期，使用陣列實作
- 如果佇列大小動態變化，使用鏈結串列實作
- 如果需要頻繁的插入 / 刪除，使用鏈結串列實作
Sign in with Wallet
Connect another wallet