目錄
- 堆疊和佇列的資料結構的實作程序（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）
鏈接：https://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 = https://www.cnblogs.com/txxunmei/p/(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 的值越來越大，陣列佇列的時間消耗會比回圈佇列大許多，
測驗結果:
最后，從結果中，可以看出回圈佇列的入隊和出隊操作所用的時間消耗比陣列佇列的快了很大的倍數，當然，隨著機器配置的不同，測驗結果可能也會不同，但能夠驗證回圈佇列比陣列佇列快就可以了，
如有寫的不足的，請見諒，請大家多多指教，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143968.html
標籤：其他