【Java/數據結構】隊列（Quque）

本博客將介紹隊列的相關知識，包括基于數組的普通隊列，基于鏈表的普通隊列，基于數組的雙端隊列，基于鏈表的雙端隊列，但不包括優先級隊列（PriorityQueue），此數據結構將單獨發一篇博客，那么，讓我們從基礎的隊列開始吧！

一.隊列概述

1.隊列概述

隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

可以把他想象成排隊買東西，先排隊先買。

特性：FIFO（First In First Out），先進先出。

Quque在Java集合框架中的位置如下：

雖然看起來很單一，但實際上隊列的實現相當豐富。

二.隊列的實現

我們要模擬實現是基于數組的循環隊列、基于鏈表的單端隊列、基于數組的雙端隊列、基于鏈表的雙端隊列。

1.源碼簡介

先看看源碼（可以直接看模擬實現）：
首先看看Queue接口：

繼承自collection接口，提供了一些隊列基本方法，

還有繼承自Queue的Deque接口：

接下來看看AbstractQueue：

接下來是基本實現類：

有ArrayQueue：

LinkedList，沒錯，LinkedList也可以被當成隊列來使用：

LinkedList是繼承自Deque的，除此之外，還有像PriorityQueue（優先級隊列）、BlockingDeque（雙端阻塞隊列）等我們暫且不討論。

2.基于數組的循環隊列

（1）原理

為什么會加上循環特性呢？

原因是普通非循環隊列重復使用會造成嚴重的內存浪費，而加上循環特性后，就可以避免這一情況了，請看如下情況：

1、2出隊，5、6、7、8入隊后：

由于使用的是邏輯刪除，所以1、2所占內存其實還在，反復增刪后（內存不足自動擴容），就會變成一個有效數據極少，所占內存極大的隊列，與是，改進成循環隊列：

還是這張圖，但是當我們進行4、5出隊，9、10、11、12入隊的操作后，就開始循環存儲：

有效區域為6~12，當繼續添加元素13~20后，判斷隊尾會追上隊頭時，容量不足，于是會先把所有數據復制到內存擴大的新數組，并從0下標按順序排列后才會繼續添加元素：

先復制：

再添加元素：?

通常我們會用size與capacity來記錄容量是否滿出，即size>=capacity時自動擴容。

在設計時，要特別注意%處的操作。

（2）基本結構

public class MyQueue {private int[] queue;   // 存儲元素的數組private int front;     // 隊頭指針private int size;      // 當前元素數量private int capacity;  // 當前隊列容量private static final int DEFAULT_CAPACITY = 10;// 初始化隊列public MyQueue() {this.capacity = DEFAULT_CAPACITY;this.queue = new int[capacity];this.front = 0;this.size = 0;}......

說明：隊尾指針為 rear = (front + size) % capacity ，可以通過計算求得，不需要定義一個。

或者定義 rear，不定義size，都可以，此處隊尾指針表示的是隊尾元素的下一個節點，方便插入。

（3）擴容

// 隊列擴容
private void resize(int newCapacity) {int[] newArray = new int[newCapacity];// 將舊數組元素按順序復制到新數組頭部for (int i = 0; i < size; i++) {newArray[i] = queue[(front + i) % capacity];}queue = newArray;front = 0;       // 重置隊頭指針capacity = newCapacity; // 更新容量
}

（4）enqueue（入隊）

// 入隊操作（支持自動擴容）
public void enqueue(int item) {// 隊列已滿時觸發擴容if (isFull()) {resize(capacity * 2); // 容量翻倍}int rear = (front + size) % capacity;queue[rear] = item;size++;
}

（5）dequeue（出隊）

// 出隊操作
public int dequeue() {if (isEmpty()) {throw new IllegalStateException("隊列為空，無法出隊");}int item = queue[front];front = (front + 1) % capacity;size--;return item;
}

（6）peek（查看隊頭）

// 查看隊頭元素
public int peek() {if (isEmpty()) {throw new IllegalStateException("隊列為空");}return queue[front];
}

（7）其他

// 判斷隊列是否為空
public boolean isEmpty() {return size == 0;
}// 判斷隊列是否已滿
public boolean isFull() {return size == capacity;
}// 獲取當前隊列容量（測試用）
public int getCapacity() {return capacity;
}

（8）完整實現及測試代碼

為了測試，初始容量改為3：

public class MyQueue {private int[] queue;   // 存儲元素的數組private int front;     // 隊頭指針private int size;      // 當前元素數量private int capacity;  // 當前隊列容量（不再是final）private static final int DEFAULT_CAPACITY = 3;// 初始化隊列public MyQueue() {this.capacity = DEFAULT_CAPACITY;this.queue = new int[capacity];this.front = 0;this.size = 0;}// 入隊操作（支持自動擴容）public void enqueue(int item) {// 隊列已滿時觸發擴容if (isFull()) {resize(capacity * 2); // 容量翻倍}int rear = (front + size) % capacity;queue[rear] = item;size++;}// 出隊操作public int dequeue() {if (isEmpty()) {throw new IllegalStateException("隊列為空，無法出隊");}int item = queue[front];front = (front + 1) % capacity;size--;return item;}// 查看隊頭元素public int peek() {if (isEmpty()) {throw new IllegalStateException("隊列為空");}return queue[front];}// 隊列擴容private void resize(int newCapacity) {int[] newArray = new int[newCapacity];// 將舊數組元素按順序復制到新數組頭部for (int i = 0; i < size; i++) {newArray[i] = queue[(front + i) % capacity];}queue = newArray;front = 0;       // 重置隊頭指針capacity = newCapacity; // 更新容量}// 判斷隊列是否為空public boolean isEmpty() {return size == 0;}// 判斷隊列是否已滿public boolean isFull() {return size == capacity;}// 獲取當前隊列容量（測試用）public int getCapacity() {return capacity;}// 測試代碼public static void main(String[] args) {MyQueue queue = new MyQueue();// 初始容量3queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);System.out.println("當前容量: " + queue.getCapacity()); // 3// 觸發擴容到6queue.enqueue(40);System.out.println("擴容后容量: " + queue.getCapacity()); // 6// 繼續填充測試queue.enqueue(50);queue.enqueue(60);queue.enqueue(70); // 再次觸發擴容到12System.out.println("再次擴容后容量: " + queue.getCapacity()); // 12// 驗證出隊順序System.out.print("出隊順序: ");while (!queue.isEmpty()) {System.out.print(queue.dequeue() + " "); // 10 20 30 40 50 60 70}}
}

3.基于鏈表的單端隊列

（1）原理

由于我們只對頭尾進行操作，所以我們可以用鏈表來實現，頭刪對應出隊，尾差對應入隊。

由于鏈式結構的存在，不必擔心內存不足與內存浪費，當然，一般情況下，由于創建多個對象節點，其效率不如數組實現高。

（2）實現

由于與鏈表類似，我們直接給出完整實現及測試用例：
?

public class LinkedListQueue {// 鏈表節點定義private static class Node {int data;Node next;Node(int data) {this.data = data;this.next = null;}}private Node front; // 隊頭指針（出隊位置）private Node rear;  // 隊尾指針（入隊位置）private int size;   // 隊列元素數量public LinkedListQueue() {front = null;rear = null;size = 0;}// 入隊操作（尾插）public void enqueue(int item) {Node newNode = new Node(item);if (isEmpty()) {// 隊列為空時，front和rear都指向新節點front = newNode;rear = newNode;} else {// 非空時，將新節點鏈接到隊尾，并更新rearrear.next = newNode;rear = newNode;}size++;}// 出隊操作（頭刪）public int dequeue() {if (isEmpty()) {throw new IllegalStateException("隊列為空，無法出隊");}int item = front.data;front = front.next; // 移動隊頭指針size--;// 如果出隊后隊列為空，需要同時更新rear為nullif (isEmpty()) {rear = null;}return item;}// 查看隊頭元素public int peek() {if (isEmpty()) {throw new IllegalStateException("隊列為空");}return front.data;}// 判斷隊列是否為空public boolean isEmpty() {return front == null;}// 獲取隊列元素數量public int size() {return size;}// 測試代碼public static void main(String[] args) {LinkedListQueue queue = new LinkedListQueue();// 入隊測試queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);System.out.println("入隊后隊列大小: " + queue.size()); // 3// 查看隊頭System.out.println("當前隊頭: " + queue.peek()); // 10// 出隊測試System.out.println("出隊: " + queue.dequeue()); // 10System.out.println("出隊: " + queue.dequeue()); // 20System.out.println("出隊后剩余大小: " + queue.size()); // 1// 再次入隊queue.enqueue(40);System.out.println("新隊尾元素: " + queue.rear.data); // 40// 清空隊列測試System.out.println("出隊: " + queue.dequeue()); // 30System.out.println("出隊: " + queue.dequeue()); // 40System.out.println("隊列是否為空: " + queue.isEmpty()); // true// 測試空隊列異常try {queue.dequeue();} catch (IllegalStateException e) {System.out.println("異常捕獲: " + e.getMessage()); // 隊列為空，無法出隊}}
}

4.雙端隊列

（1）原理

雙端隊列（deque）是指允許兩端都可以進行入隊和出隊操作的隊列，deque 是 “double ended queue” 的簡稱。那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。

其兩端都可出入的特性給了Deque很大的靈活性，使其基本代替了Stack，成為棧的主要實現類。

其也是實現滑動窗口的首選數據結構。

由于實現基本同上，我們直接給出實現及測試用例。

（2）基于數組的雙端隊列

public class MyArrayDeque {private int[] data;private int front;   // 隊頭指針private int size;    // 當前元素數量private int capacity; // 當前容量private static final int DEFAULT_CAPACITY = 8;// 初始化隊列（默認容量8）public MyArrayDeque() {this(DEFAULT_CAPACITY);}public MyArrayDeque(int initialCapacity) {capacity = initialCapacity;data = new int[capacity];front = 0;size = 0;}// 隊頭插入元素public void addFirst(int item) {if (isFull()) resize(capacity * 2);front = (front - 1 + capacity) % capacity; // 向前移動隊頭指針data[front] = item;size++;}// 隊尾插入元素public void addLast(int item) {if (isFull()) resize(capacity * 2);int rear = (front + size) % capacity;data[rear] = item;size++;}// 移除隊頭元素public int removeFirst() {if (isEmpty()) throw new IllegalStateException("Deque is empty");int item = data[front];front = (front + 1) % capacity;size--;return item;}// 移除隊尾元素public int removeLast() {if (isEmpty()) throw new IllegalStateException("Deque is empty");int rear = (front + size - 1) % capacity;int item = data[rear];size--;return item;}// 查看隊頭元素public int peekFirst() {if (isEmpty()) throw new IllegalStateException("Deque is empty");return data[front];}// 查看隊尾元素public int peekLast() {if (isEmpty()) throw new IllegalStateException("Deque is empty");return data[(front + size - 1) % capacity];}// 動態擴容private void resize(int newCapacity) {int[] newData = new int[newCapacity];// 將元素按順序復制到新數組頭部for (int i = 0; i < size; i++) {newData[i] = data[(front + i) % capacity];}data = newData;capacity = newCapacity;front = 0; // 重置隊頭指針}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == capacity;}public int size() {return size;}// 測試代碼public static void main(String[] args) {MyArrayDeque deque = new MyArrayDeque(3);// 隊頭插入deque.addFirst(10);deque.addFirst(20);deque.addFirst(30); // 觸發擴容到6// 隊尾插入deque.addLast(40);deque.addLast(50);deque.addLast(60); // 再次觸發擴容到12// 驗證順序System.out.println("隊頭移除: " + deque.removeFirst()); // 30System.out.println("隊尾移除: " + deque.removeLast());   // 60System.out.println("當前隊頭: " + deque.peekFirst());    // 20System.out.println("當前隊尾: " + deque.peekLast());     // 50}
}

（3）基于鏈表的雙端隊列

public class LinkedDeque {// 雙向鏈表節點定義private static class Node {int data;Node prev;Node next;Node(int data) {this.data = data;this.prev = null;this.next = null;}}private Node front;  // 隊頭指針private Node rear;   // 隊尾指針private int size;    // 隊列元素數量public LinkedDeque() {front = null;rear = null;size = 0;}// 隊頭插入元素public void addFirst(int item) {Node newNode = new Node(item);if (isEmpty()) {// 隊列為空時，front和rear都指向新節點front = rear = newNode;} else {// 將新節點鏈接到當前隊頭前newNode.next = front;front.prev = newNode;front = newNode; // 更新隊頭指針}size++;}// 隊尾插入元素public void addLast(int item) {Node newNode = new Node(item);if (isEmpty()) {front = rear = newNode;} else {// 將新節點鏈接到當前隊尾后rear.next = newNode;newNode.prev = rear;rear = newNode; // 更新隊尾指針}size++;}// 移除隊頭元素public int removeFirst() {if (isEmpty()) {throw new IllegalStateException("隊列為空，無法移除");}int item = front.data;if (front == rear) {// 只有一個元素時，移除后隊列為空front = rear = null;} else {front = front.next;front.prev = null; // 斷開舊隊頭鏈接}size--;return item;}// 移除隊尾元素public int removeLast() {if (isEmpty()) {throw new IllegalStateException("隊列為空，無法移除");}int item = rear.data;if (front == rear) {front = rear = null;} else {rear = rear.prev;rear.next = null; // 斷開舊隊尾鏈接}size--;return item;}// 查看隊頭元素public int peekFirst() {if (isEmpty()) {throw new IllegalStateException("隊列為空");}return front.data;}// 查看隊尾元素public int peekLast() {if (isEmpty()) {throw new IllegalStateException("隊列為空");}return rear.data;}public boolean isEmpty() {return size == 0;}public int size() {return size;}// 打印隊列內容（測試用）public void display() {Node current = front;System.out.print("隊列內容: ");while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();}// 測試代碼public static void main(String[] args) {LinkedDeque deque = new LinkedDeque();// 隊頭插入測試deque.addFirst(10);deque.addFirst(20);deque.display(); // 隊列內容: 20 10// 隊尾插入測試deque.addLast(30);deque.addLast(40);deque.display(); // 隊列內容: 20 10 30 40// 移除測試System.out.println("移除隊頭: " + deque.removeFirst()); // 20System.out.println("移除隊尾: " + deque.removeLast());  // 40deque.display(); // 隊列內容: 10 30// 邊界測試deque.removeFirst();deque.removeLast();System.out.println("隊列是否為空: " + deque.isEmpty()); // true// 異常測試try {deque.removeFirst();} catch (IllegalStateException e) {System.out.println("異常捕獲: " + e.getMessage());}}
}