詳細分析棧和隊列的數據結構的實現過程（Java 實現）
棧和隊列的數據結構的實現過程（Java 實現）
棧的數據結構的實現
棧的基礎知識回顧
-
棧是一種線性結構。
-
相比數組，棧對應的操作是數組的子集。
- 也就是棧可基於數組實現，可以將棧看成一種特殊的數組。
-
棧只能從一端添加元素，也只能從一端取出元素，這一端稱為棧頂。
-
棧是一種 後進先出 (LIFO: Last In First Out) 的數據結構。
棧的常見應用
-
撤銷（Undo）操作
-
程式調用的系統棧
基於數組的棧的實現
對於棧這種數據結構，實現起來是十分簡單的，這裡實現以下幾個操作：
-
入棧：void push(E element)
-
出棧: E pop()
-
查看棧頂元素: E peek()
-
獲取棧中元素個數: int getSize()
-
判斷棧是否為空: boolean: isEmpty()
對於程式碼的具體實現，可以讓其支援多態性。所以可以設計一個介面 Stack 定義上面這 5 個棧支援的操作，再設計一個類 ArrayStack 來實現這個介面。
對於 ArrayStack 這個類，實質上是基於之前實現的動態數組類 Array 來實現的一個數組棧。因為對於棧而言，棧對應的操作是數組的子集。可以把棧當成一個數組來看待。
對於 Array 類的具體實現過程，可查看另一篇 文章 。
具體程式碼設計
在編寫棧的具體程式碼之前，先往工程中導入之前實現的動態數組類 Array，該類程式碼可從之前的文章中查閱, 因為要基於該類來實現數組棧。
ArrayStack 類的實現:
因為在 Array 類中已經實現了很多操作數組的方法。所以對於 ArrayStack 類實現介面中的方法時，只需復用 Array 類中的方法即可。
基於 Array 類實現 ArrayStack 類也有一些好處：
和 Array 一樣擁有了動態伸縮容量的功能，我們不需要關心棧的容量是否夠用，因為容量會動態地進行擴大和縮小。
對於一些非法變數的判斷直接復用了 Array 類中的程式碼，不需要重複編寫。
同時，也可以為 ArrayStack 類添加一個介面中沒有的方法 getCapacity 提供給用戶獲取棧的容量。這個方法是這個類中特有的。
在實現 peek 方法之前，可以在 Array 類中擴展兩個新方法用於獲取數組末尾和數組首部的元素，方便在 ArrayStack 類和後續隊列的實現中直接復用。
/**
* 獲取數組的最後一個元素
*
* @return 返回數組的最後一個元素
*/
public E getLast() {
return get(size - 1);
}
/**
* 獲取數組的第一個元素
*
* @return 返回數組的第一個元素
*/
public E getFirst() {
return get(0);
}
Stack 介面類程式碼如下:
/**
* 定義棧的基本操作的介面
* 支援泛型
*
* @author 踏雪尋梅
* @date 2020/1/8 - 19:20
*/
public interface Stack<E> {
/**
* 獲取棧中元素個數
*
* @return 棧中如果有元素,返回棧中當前元素個數;棧中如果沒有元素返回 0
*/
int getSize();
/**
* 判斷棧是否為空
*
* @return 棧為空,返回 true;棧不為空,返回 false
*/
boolean isEmpty();
/**
* 入棧
* 將元素 element 壓入棧頂
*
* @param element 入棧的元素
*/
void push(E element);
/**
* 出棧
* 將當前棧頂元素出棧並返回
*
* @return 返回當前出棧的棧頂元素
*/
E pop();
/**
* 查看當前棧頂元素
*
* @return 返回當前的棧頂元素
*/
E peek();
}
ArrayStack 類程式碼實現如下：
/**
* 基於之前實現的動態數組類 Array 實現的數組棧類 ArrayStack
* 同樣支援泛型
*
* @author 踏雪尋梅
* @date 2020/1/8 - 19:26
*/
public class ArrayStack<E> implements Stack<E> {
/**
* 動態數組 array
* 基於 array 實現棧的操作
*/
private Array<E> array;
/**
* 構造函數
* 創建一個容量為 capacity 的數組棧
*
* @param capacity 要創建的棧的容量,由用戶指定
*/
public ArrayStack(int capacity) {
array = new Array<>(capacity);
}
/**
* 默認構造函數
* 創建一個默認容量的數組棧
*/
public ArrayStack() {
array = new Array<>();
}
@Override
public int getSize() {
// 復用 array 的 getSize() 方法即可
return array.getSize();
}
@Override
public boolean isEmpty() {
// 復用 array 的 isEmpty() 方法即可
return array.isEmpty();
}
/**
* 獲取棧的容量
* ArrayStack 特有的方法
*
* @return 返回棧的容量
*/
public int getCapacity() {
// 復用 array 的 getCapacity() 方法即可
return array.getCapacity();
}
@Override
public void push(E element) {
// 將數組的末尾作為棧頂,復用 array 的 addLast() 方法實現
array.addLast(element);
}
@Override
public E pop() {
// 將數組的末尾作為棧頂,復用 array 的 removeLast() 方法將棧頂元素出棧並返回
return array.removeLast();
}
@Override
public E peek() {
// 將數組的末尾作為棧頂,復用 array 的 getLast() 方法獲取棧頂元素
return array.getLast();
}
/**
* 重寫 toString 方法返回數組棧的資訊
*
* @return 返回數組棧的當前資訊
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append("ArrayStack: ");
result.append("size: ").append(array.getSize()).append(" ");
result.append("capacity: ").append(array.getCapacity()).append(" ");
result.append("bottom -> [ ");
for (int i = 0; i < array.getSize(); i++) {
result.append(array.get(i));
// 如果不是最後一個元素
if (i != array.getSize() - 1) {
result.append(", ");
}
}
result.append(" ] <- top");
return result.toString();
}
}
對於 toString 中的遍歷棧中元素，只是為了方便查看棧中是否如我們設計的一樣正確地添加了元素。
對於用戶而言，除了棧頂元素，其他的元素是不需要知道的，並且用戶也只能操作棧頂元素，不能操作除了棧頂元素之外的其他元素，這也是棧這個數據結構的特點。
測試:
/**
* 測試 ArrayStack
*
* @author 踏雪尋梅
* @date 2020/1/8 - 16:49
*/
public class Main {
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>();
for (int i = 0; i < 10; i++) {
// 入棧
stack.push(i);
// 列印入棧過程
System.out.println(stack);
}
// 進行一次出棧
stack.pop();
// 查看出棧後的狀態
System.out.println(stack);
// 查看當前棧頂元素
Integer topElement = stack.peek();
System.out.println("當前棧頂元素： " + topElement);
// 判斷棧是否為空
System.out.println("當前棧是否為空: " + stack.isEmpty());
}
}
測試結果:
基於數組的棧簡單的時間複雜度分析
對於實現的這 5 個操作，通過之前文章中對 Array 類的分析可以很快地得出他們的時間複雜度，分別如下：
-
void push(E element)：O(1) 均攤
- 復用了 array 的方法，所以可能觸發 resize 方法進行伸縮容量，所以時間複雜度是均攤的。
-
E pop()：O(1) 均攤
- 復用了 array 的方法，所以可能觸發 resize 方法進行伸縮容量，所以時間複雜度是均攤的。
-
E peek()：O(1)
-
int getSize()：O(1)
-
boolean isEmpty()：O(1)
關於棧的一個演算法應用：括弧匹配
題目描述:
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字元串，判斷字元串是否有效。
有效字元串需滿足：
左括弧必須用相同類型的右括弧閉合。
左括弧必須以正確的順序閉合。
注意空字元串可被認為是有效字元串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/valid-parentheses
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
題目分析
可使用棧來解決
思路：
- 逐一遍歷給定字元串中的括弧。
-
如果括弧是一個左括弧，就將其壓入棧中。
-
如果遇到右括弧，此時將棧頂的左括弧出棧查看是否可以和這個右括弧匹配。
-
如果可以匹配，則繼續剩餘的判斷。
- 如果所有括弧匹配成功後，那麼此時棧應該是空棧，說明給定字元串是有效的。
-
如果不可以匹配，則說明這個字元串是無效的。
-
-
通過以上分析可以得出：棧頂元素反映了在嵌套的層次關係中，最近的需要匹配的元素。
思路圖示:
-
有效的括弧字元串圖示
-
無效的括弧字元串圖示
題解程式碼:
-
方法一: 使用 java 的 util 包中內置的 Stack 類解決。
import java.util.Stack; /** * 括弧匹配解決方案 * 方法一：使用 java 的 util 包中內置的 Stack 類解決 * * @author 踏雪尋梅 * @date 2020/1/8 - 21:52 */ public class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); // 遍歷給定字元串 for (int i = 0; i < s.length(); i++) { // 查看括弧 char c = s.charAt(i); // 如果括弧是左括弧,入棧 if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { // 括弧是右括弧,查看是否和棧頂括弧相匹配 if (stack.isEmpty()) { // 如果此時棧是空的,說明前面沒有左括弧,字元串是右括弧開頭的,匹配失敗,字元串無效 return false; } // 棧非空,將當前棧頂括弧出棧保存到變數中進行匹配判斷 char topBracket = stack.pop(); // 匹配失敗的情況,以下情況若為發生則進行下一次循環依次判斷 if (c == ')' && topBracket != '(') { return false; } if (c == ']' && topBracket != '[') { return false; } if (c == '}' && topBracket != '{') { return false; } } } // for 循環結束後,如果棧中還有字元,說明有剩餘的左括弧未匹配,此時字元串無效,否則字元串有效 // 即 isEmpty() 返回 true 表示匹配成功;返回 false 表示匹配失敗 return stack.isEmpty(); } }-
提交結果
-
-
方法二：使用自己實現的 ArrayStack 類解決
需要注意的是要在 Solution 中添加自己實現的 Array 類、Stack 介面、ArrayStack 類作為內部類才能使用自己實現的數組棧來解決。
/** * 括弧匹配解決方案 * 方法二：使用自己實現的 ArrayStack 類解決 * * @author 踏雪尋梅 * @date 2020/1/8 - 22:25 */ public class Solution { public boolean isValid(String s) { Stack<Character> stack = new ArrayStack<>(); // 遍歷給定字元串 for (int i = 0; i < s.length(); i++) { // 查看括弧 char c = s.charAt(i); // 如果括弧是左括弧,入棧 if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { // 括弧是右括弧,查看是否和棧頂括弧相匹配 if (stack.isEmpty()) { // 如果此時棧是空的,說明前面沒有左括弧,字元串是右括弧開頭的,匹配失敗,字元串無效 return false; } // 棧非空,將當前棧頂括弧出棧保存到變數中進行匹配判斷 char topBracket = stack.pop(); // 匹配失敗的情況,以下情況若為發生則進行下一次循環依次判斷 if (c == ')' && topBracket != '(') { return false; } if (c == ']' && topBracket != '[') { return false; } if (c == '}' && topBracket != '{') { return false; } } } // for 循環結束後,如果棧中還有字元,說明有剩餘的左括弧未匹配,此時字元串無效,否則字元串有效 // 即 isEmpty() 返回 true 表示匹配成功;返回 false 表示匹配失敗 return stack.isEmpty(); } private class Array<E> { ...（該類中的程式碼此處省略） } private interface Stack<E> { ...（該類中的程式碼此處省略） } private class ArrayStack<E> implements Stack<E> { ...（該類中的程式碼此處省略） } }-
提交結果
-
隊列的數據結構的實現
隊列的基礎知識回顧
-
隊列也是一種線性結構。
-
相比數組，隊列對應的操作是數組的子集。
- 也就是說，隊列是可基於數組實現的，可以將隊列看成一個特殊的數組。
-
隊列只能從一端（隊尾）添加元素，只能從另一端（隊首）取出元素。
- 其實和現實生活中的排隊差不多，隊頭的人離去，新來的人排在隊尾。
-
隊列是一種先進先出 (FIFO：First In First Out) 的數據結構。
基於數組的隊列的實現
對於隊列這種數據結構，實現起來是十分簡單的，這裡實現以下幾個操作：
-
入隊：void enqueue(E element)
-
出隊: E dequeue()
-
查看隊首元素: E getFront()
-
獲取隊列元素個數: int getSize()
-
判斷隊列是否為空: boolean isEmpty()
對於程式碼的具體實現，和上面實現的棧一樣也可以讓實現的隊列支援多態性。所以在此設計一個介面 Queue 定義上面這 5 個隊列支援的操作，再設計一個類 ArrayQueue 來實現這個介面。
對於 ArrayQueue 這個類，實質上也是基於之前實現的動態數組類 Array 來實現的。
具體程式碼設計
在編寫數組隊列的具體程式碼之前，先往工程中導入之前實現的動態數組類 Array，因為要基於該類來實現數組隊列，不過在之前實現棧的時候已經導入過了。
Queue 介面類的實現:
/**
* 定義隊列的基本操作的介面
* 支援泛型
*
* @author 踏雪尋梅
* @date 2020/1/9 - 16:52
*/
public interface Queue<E> {
/**
* 獲取隊列中元素個數
*
* @return 隊列中如果有元素,返回隊列中當前元素個數;隊列中如果沒有元素返回 0
*/
int getSize();
/**
* 判斷隊列是否為空
*
* @return 隊列為空,返回 true;隊列不為空,返回 false
*/
boolean isEmpty();
/**
* 入隊
* 將元素 element 添加到隊尾
*
* @param element 入隊的元素
*/
void enqueue(E element);
/**
* 出隊
* 將隊首的元素出隊並返回
*
* @return 返回當前出隊的隊首的元素
*/
E dequeue();
/**
* 查看當前隊首元素
*
* @return 返回當前的隊首元素
*/
E getFront();
}
ArrayQueue 類的實現:
因為在 Array 類中已經實現了很多操作數組的方法。所以對於 ArrayQueue 類實現介面中的方法時，同樣只需要復用 Array 類中的方法即可。
同樣，基於 Array 類實現 ArrayQueue 類也有相對應的好處：
和 Array 一樣擁有了動態伸縮容量的功能，我們不需要關心隊列的容量是否夠用，因為容量會動態地進行擴大和縮小。
對於一些非法變數的判斷直接復用了 Array 類中的程式碼，不需要重複編寫。
同時，也可以為 ArrayQueue 類添加一個介面中沒有的方法 getCapacity 提供給用戶獲取隊列的容量。這個方法是這個類中特有的。
ArrayQueue 類程式碼實現如下：
/**
* 基於之前實現的動態數組類 Array 實現的數組隊列類 ArrayQueue
* 同樣支援泛型
*
* @author 踏雪尋梅
* @date 2020/1/10 - 18:17
*/
public class ArrayQueue<E> implements Queue<E> {
/**
* 動態數組 array
* 基於 array 實現隊列的操作
*/
private Array<E> array;
/**
* 構造函數
* 創建一個容量為 capacity 的數組隊列
*
* @param capacity 要創建的隊列的容量,由用戶指定
*/
public ArrayQueue(int capacity) {
array = new Array<>(capacity);
}
/**
* 默認構造函數
* 創建一個默認容量的數組隊列
*/
public ArrayQueue() {
array = new Array<>();
}
/**
* 獲取隊列的容量
* ArrayQueue 特有的方法
*
* @return 返回隊列的容量
*/
public int getCapacity() {
// 復用 array 的 getCapacity() 方法即可
return array.getCapacity();
}
@Override
public int getSize() {
// 復用 array 的 getSize() 方法即可
return array.getSize();
}
@Override
public boolean isEmpty() {
// 復用 array 的 isEmpty() 方法即可
return array.isEmpty();
}
@Override
public void enqueue(E element) {
// 將數組的末尾作為隊尾,復用 array 的 addLast() 方法實現
array.addLast(element);
}
@Override
public E dequeue() {
// 將數組的首部作為隊首,復用 array 的 removeFirst() 方法將隊首元素出隊並返回
return array.removeFirst();
}
@Override
public E getFront() {
// 復用 array 的 getFirst() 方法獲取隊首元素
return array.getFirst();
}
/**
* 重寫 toString 方法返回數組隊列的資訊
*
* @return 返回數組隊列的當前資訊
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append("ArrayQueue: ");
result.append("size: ").append(array.getSize()).append(" ");
result.append("capacity: ").append(array.getCapacity()).append(" ");
result.append("front -> [ ");
for (int i = 0; i < array.getSize(); i++) {
result.append(array.get(i));
// 如果不是最後一個元素
if (i != array.getSize() - 1) {
result.append(", ");
}
}
result.append(" ] <- tail");
return result.toString();
}
}
對於 toString 中的遍歷隊列中的元素，只是為了方便查看隊列中是否如我們設計的一樣正確地添加了元素。
對於用戶而言，除了隊首元素，其他的元素是不需要知道的，因為一般來說業務操作都是針對隊首元素的，剩餘的元素都在排隊等待中。並且用戶只能操作隊首元素和隊尾元素，從隊尾進入新數據從隊首離開老數據，不能操作除了隊首元素和隊尾元素之外的其他元素，這也是隊列這個數據結構的特點。
測試:
/**
* 測試 ArrayQueue
*/
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<>();
// 判斷隊列是否為空
System.out.println("當前隊列是否為空: " + queue.isEmpty());
for (int i = 0; i < 10; i++) {
// 入隊
queue.enqueue(i);
// 顯示入隊過程
System.out.println(queue);
// 每入隊 4 個元素就出隊一次
if (i % 4 == 3) {
// 出隊
queue.dequeue();
// 顯示出隊過程
System.out.println("\n" + queue + "\n");
}
}
// 判斷隊列是否為空
System.out.println("當前隊列是否為空: " + queue.isEmpty());
// 獲取隊首元素
Integer front = queue.getFront();
System.out.println("當前隊列隊首元素為: " + front);
}
測試結果:
基於數組的隊列的簡單時間複雜度分析
對於實現的這 5 個操作，通過之前的 Array 類的分析可以很快地得出他們的時間複雜度，分別如下：
-
void enqueue(E element)：O(1) 均攤
- 復用了 array 的方法，所以可能觸發 resize 方法進行伸縮容量，所以時間複雜度是均攤的。
-
E dequeue()：O(n)
-
在出隊的時候，當把隊首的元素移出去之後，剩下的元素都要往前移動一個位置。
-
所以，對於當前實現的基於數組的隊列，如果要放的數據量很大的話，比如 100 萬、1000 萬的數據量的時候，進行出隊操作的時候時間性能消耗會很大。
- 對於這種情況，可使用循環隊列來解決。
-
-
E getFront()：O(1)
-
int getSize()：O(1)
-
boolean isEmpty()：O(1)
循環隊列的實現
數組隊列出隊時的缺陷分析:
在前面的基於數組的實現中，隊列在出隊時剩餘的元素都會往前移動一個位置，如果數據量很大時進行出隊將會耗費很多的時間去移動元素。而如果不移動，前面就會存在沒有使用的數組空間。所以這是數組隊列存在的局限性。
數組隊列出隊圖示:
改進分析:
對於改進這一缺陷，可以使用兩個變數來記錄隊首和隊尾的位置，分別為 front、tail。
對於 front，指向的是隊列的第一個元素所在的位置，而 tail 指向的則是新元素入隊時應該要放置的位置。
這樣記錄後，當元素出隊後，只要維護 front 指向的位置就可以了，此時就不需要像之前那樣將所有元素都往前移動一個位置了，這樣時間複雜度就是 O(1) 級別的了。而當元素入隊時，只需要維護 tail 將其重新指向下一個元素入隊時應該要放置的位置即可。
所以循環隊列的實現思路可如下逐一分析:
-
初始時，隊列為空，front 和 tail 都指向 0，即 front == tail 表示隊列為空，元素個數 size 的值也為 0，表示當前元素個數為 0。
-
當元素入隊時，維護 tail 將其指向下一個元素入隊時應該要放置的位置，即當前隊尾元素的後一個位置。
-
當元素出隊時，維護 front 將其指向出隊後的隊列中的第一個元素。
-
當元素入隊到 tail 的值不能再加一且隊列空間未滿的時候，維護 tail 將其指向剩餘空間中的第一個位置，使隊列中的元素像處於一個環中一樣進行循環。
-
例如以下情況
-
此時可暫時得出元素入隊時更改 tail 的值的公式：
(tail + 1) % capacity
-
當 tail 的值再加一就等於 front 的值時，此時隊列還剩餘一個空間（此處這個剩餘的空間設計為不記在隊列容量中，是額外添加的），這時候表示隊列為滿，不能再入隊，即 (tail + 1) % (capacity + 1) == front 表示隊列滿（capacity + 1 == data.length）。
-
此時若再入隊，就會讓 front 和 tail 相等，由於front == tail 表示隊列為空，此時隊列又不為空，會產生矛盾。所以在循環隊列中額外添加一個空間用來判斷隊列是否已滿。具體過程如下圖所示：
-
綜上可總結出關於循環隊列的四個公式
-
front == tail 表示隊列為空。
-
(tail + 1) % data.length == front 表示隊列為滿。
- 或 (tail + 1) % (capacity + 1) == front
-
元素入隊時更改 tail 的值的公式：(tail + 1) % data.length。
-
因為已經設定了在隊列中額外添加一個空間用於判斷隊列是否已滿，所以更改 tail 時需要模的是隊列底層數組的長度，而不是模隊列的容量。可參照下圖理解：
-
-
同理，可得出元素出隊時更改 front 的值得公式：(front + 1) % data.length。
-
-
具體程式碼設計
程式碼實現:
通過以上分析，可設計循環隊列 LoopQueue 類的程式碼如下：
/**
* 循環隊列類 LoopQueue
* 支援泛型
*
* @author 踏雪尋梅
* @date 2020/1/10 - 21:35
*/
public class LoopQueue<E> implements Queue<E> {
/**
* 存放循環隊列元素的底層數組
*/
private E[] data;
/**
* 隊首索引
* 指向隊列隊首元素所在的索引
*/
private int front;
/**
* 隊尾索引
* 指向新元素入隊時應該要放置的索引
*/
private int tail;
/**
* 循環隊列當前元素個數
*/
private int size;
/**
* 構造函數
* 構建一個容量為 capacity 的循環隊列
*
* @param capacity 要創建的循環隊列的容量,由用戶指定
*/
public LoopQueue(int capacity) {
// 因為在循環隊列中額外添加了一個空間用來判斷隊列是否已滿,所以構建 data 時多加了一個空間
data = (E[]) new Object[capacity + 1];
// 循環隊列初始化
front = 0;
tail = 0;
size = 0;
}
/**
* 默認構造函數
* 構建一個容量為 10 的循環隊列
*/
public LoopQueue() {
this(10);
}
/**
* 獲取循環隊列的容量
*
* @return 返回循環隊列的容量
*/
public int getCapacity() {
// 因為在循環隊列中額外添加了一個空間用來判斷隊列是否已滿,所以返回時將數組長度的值減一
return data.length - 1;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
// front == tail 表示隊列為空,返回 true;否則返回 false
return front == tail;
}
/**
* 將循環隊列的容量更改為 newCapacity
*
* @param newCapacity 循環隊列的新容量
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
// 將 data 的所有元素按順序 (front ~ tail) 轉移到 newData 的 [0, size - 1] 處
for (int i = 0; i < size; i++) {
// 在將元素轉移到擴容後的空間時,兩個數組的 i 的值不一定對應
// 所以取 data 的數據時需要將 i 進行偏移：(i + front) % data.length
newData[i] = data[(i + front) % data.length];
}
// 將 data 指向擴容後的隊列
data = newData;
// 重新設定隊首、隊尾索引的值,因為上處將 data 的所有元素按順序 (front ~ tail) 轉移到 newData 的 [0, size - 1] 處
front = 0;
tail = size;
}
@Override
public void enqueue(E element) {
// 入隊前先查看隊列是否已滿,data.length <==> getCapacity() + 1
if ((tail + 1) % data.length == front) {
// 隊列滿時進行擴容
resize(getCapacity() * 2);
}
// 入隊
data[tail] = element;
// 維護 tail
tail = (tail + 1) % data.length;
// 維護 size
size++;
}
@Override
public E dequeue() {
// 出隊前查看隊列是否為空
if (isEmpty()) {
// 隊列為空,拋出一個非法參數異常說明空隊列不能出隊
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
}
// 保存出隊元素,以返回給用戶
E dequeueElement = data[front];
// 出隊
// 將原隊首元素置空,防止對象遊離
data[front] = null;
// 維護 front
front = (front + 1) % data.length;
size--;
// 當出隊到隊列元素個數少到一定程度時,進行減容
if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
resize(getCapacity() / 2);
}
// 返回出隊元素給用戶
return dequeueElement;
}
@Override
public E getFront() {
// 查看隊首元素前查看隊列是否為空
if (isEmpty()) {
// 隊列為空,拋出一個非法參數異常說明隊列是空隊列
throw new IllegalArgumentException("Queue is empty.");
}
// 返回隊首元素給用戶
return data[front];
}
/**
* 重寫 toString 方法返回循環隊列的資訊
*
* @return 返回循環隊列的當前資訊
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append(String.format("LoopQueue: size = %d, capacity = %d\n", size, getCapacity()));
result.append("front -> [ ");
for (int i = front; i != tail; i = (i + 1) % data.length) {
result.append(data[i]);
// 如果不是最後一個元素
if ((i + 1) % data.length != tail) {
result.append(", ");
}
}
result.append(" ] <- tail");
return result.toString();
}
}
測試:
/**
* 測試 LoopQueue
*/
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<>();
// 判斷隊列是否為空
System.out.println("當前隊列是否為空: " + queue.isEmpty());
for (int i = 0; i < 10; i++) {
// 入隊
queue.enqueue(i);
// 顯示入隊過程
System.out.println(queue);
// 每入隊 3 個元素就出隊一次
if (i % 3 == 2) {
// 出隊
queue.dequeue();
// 顯示出隊過程
System.out.println("\n" + queue + "\n");
}
}
// 判斷隊列是否為空
System.out.println("當前隊列是否為空: " + queue.isEmpty());
// 獲取隊首元素
Integer front = queue.getFront();
System.out.println("當前隊列隊首元素為: " + front);
}
測試結果:
對於循環隊列的程式碼，因為使用了 front 和 tail 指向隊首和隊尾，所以不好再復用 Array 類的程式碼，不過同樣的是底層依舊是基於泛型數組實現的，只不過使用了循環隊列的一些公式使其能循環存取數據，並且也和之前實現的 Array、ArrayStack、ArrayQueue 類一樣實現了動態伸縮容量的功能，讓用戶不再擔心容量夠不夠使用的問題。
循環隊列的簡單時間複雜度分析
對於循環隊列，因為使用了 front 來指向隊首，所以相比之前的數組隊列，可以很快的得出在出隊的時候的時間複雜度是 O(1) 級別的。
又因為在程式碼實現中同樣實現了自動伸縮容量，所以在入隊和出隊的時候可能會觸發 resize 方法進行擴大容量和減少容量，通過之前的 Array 類的分析，對於入隊和出隊時的時間複雜度 O(1) 同樣可以得出是均攤的。所以對於循環隊列中的 5 個基本操作，時間複雜度如下：
-
void enqueue(E element)：O(1) 均攤
-
E dequeue()：O(1) 均攤
-
E getFront()：O(1)
-
int getSize()：O(1)
-
boolean isEmpty()：O(1)
數組隊列和循環隊列間的比較
實現到此，棧和隊列的基本數據結構都實現完成了，最後再編寫一些程式碼來實際測試一下數組隊列和循環隊列之間的效率差異。
測試程式碼:
import java.util.Random;
/**
* 測試 ArrayQueue 和 LoopQueue 的效率差距
*
* @author 踏雪尋梅
* @date 2020/1/8 - 16:49
*/
public class Main {
public static void main(String[] args) {
// 測試數據量
int opCount = 100000;
// 測試數組隊列所需要的時間
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double arrayQueueTime = testQueue(arrayQueue, opCount);
System.out.println("arrayQueueTime: " + arrayQueueTime + " s.");
// 測試循環隊列所需要的時間
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double loopQueueTime = testQueue(loopQueue, opCount);
System.out.println("loopQueueTime: " + loopQueueTime + " s.");
// 計算兩者間的差距
double multiple = arrayQueueTime / loopQueueTime;
System.out.println("在這台機器上,對於 " + opCount + " 的數據量,loopQueue 用時比 arrayQueue 用時大約快 " + multiple + " 倍.");
}
/**
* 測試使用隊列 queue 運行 opCount 個 enqueue 和 dequeue 操作所需要的時間,單位: 秒
*
* @param queue 測試的隊列
* @param opCount 測試的數據量
* @return 返回整個測試過程所需要的時間,單位: 秒
*/
private static double testQueue(Queue<Integer> queue, int opCount) {
long startTime = System.nanoTime();
// 用於生成隨機數入隊
Random random = new Random();
// opCount 次 enqueue
for (int i = 0; i < opCount; i++) {
// 入隊
queue.enqueue(random.nextInt(Integer.MAX_VALUE));
}
// opCount 次 dequeue
for (int i = 0; i < opCount; i++) {
// 出隊
queue.dequeue();
}
long endTime = System.nanoTime();
// 將納秒單位的時間轉換為秒單位
return (endTime - startTime) / 1000000000.0;
}
}
在以上程式碼中：
-
對於數組隊列而言，入隊時單次操作是 O(1) 的，而 opCount 次入隊是 O(n) 的；出隊時單次操作是 O(n) 的，而 opCount 次出隊則是 O(n2) 的；所以對於整個 testQueue 方法，數組隊列的時間複雜度是 O(n2) 級別的。
-
對於循環隊列而言，入隊時和出隊時單次操作都是均攤複雜度 O(1) 的，所以 opCount 次入隊和出隊則是 O(n) 的，所以對於整個 testQueue 方法，循環隊列的時間複雜度是 O(n) 級別的。
-
所以，可以預估：隨著 n 的值越來越大，數組隊列的時間消耗會比循環隊列大許多。
測試結果:
最後，從結果中，可以看出循環隊列的入隊和出隊操作所用的時間消耗比數組隊列的快了很大的倍數。當然，隨著機器配置的不同，測試結果可能也會不同，但能夠驗證循環隊列比數組隊列快就可以了。
如有寫的不足的，請見諒，請大家多多指教。
