純數據結構Java實現(2/11)(棧與隊列)
- 2019 年 10 月 3 日
- 筆記
棧和隊列的應用非常多，但其起實現嘛，其實很少人關心。
雖然蘋果一直宣傳什麼最小年齡的編程者，它試圖把編程大眾化，弱智化，但真正的複雜問題，需要抽絲剝繭的時候，還是要 PRO 人士出場，所以知根知底，實在是必要之舉(而非無奈之舉)。
大門敞開，越往裡走越窄，競爭會越激烈。
棧
基本特性
就一條，FILO。但是用在其他複雜數據結構，比如樹，或者用在其他應用場景的時候，比如記錄調用過程中的變數及其狀態等，超有用。
應用舉例
比如 撤銷操作:
用戶每次的錄入都會入棧，被系統記錄，然後寫入文件；但是用戶撤銷，則是當前的操作出棧，此時上一次操作位於棧頂，也就相當於本次操作被取消了。
這裡始終 操作棧頂 即可。
比如 程式調用棧:
函數一調用就會入棧(因為這個函數可能內部還要調用別的函數)，函數調用返回時，出棧。
每次返回時不知道下一步執行誰？不會的，它會參考棧裡面記錄的調用鏈。
比如 括弧匹配 問題:
遇到左括弧(只要是左邊括弧)就入棧，碰到右邊括弧就比較，如果匹配，那麼就出棧。(不匹配直接返回false)
(抱歉，Python程式碼寫多了，老是忘記加上 ; 分號)
順序棧實現
定義好介面，然後內部封裝一個動態數組，實現介面的方法即可。
大概的介面，通用的方法就五個:
public interface Stack<E> { //介面中聲明相關方法即可 boolean isEmpty(); int getSize(); E pop(); E peek(); void push(E e); }然後實現程式碼如下:
// 真正的實現 import array.AdvanceDynamicArray; public class ArrayStack<E> implements Stack<E> { //底層實現是動態數組，所以內部直接引用動態數組就好了 AdvanceDynamicArray<E> array; public ArrayStack(int capacity) { array = new AdvanceDynamicArray<>(capacity); } public ArrayStack() { array = new AdvanceDynamicArray<>(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public int getSize() { return array.getSize(); } @Override public E pop() { return array.pop(); } @Override public E peek() { return array.getLast(); } @Override public void push(E e) { array.append(e); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Stack ["); for (int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if (i != array.getSize() - 1) { res.append(", "); } } res.append("]，top right"); return res.toString(); } }沒事兒簡單測試一下看看:
//測試一下棧 private static void test_stack_1() { ArrayStack<Integer> stack = new ArrayStack<>(); //默認內部動態數組容量 10 //推入 5 個元素 for(int i=0; i< 5; i++){ stack.push(i); System.out.println(stack); //每次入棧，列印一次 } System.out.println("---------"); stack.pop(); System.out.println(stack); } // 列印輸入結果如下: Stack [0]，top right Stack [0, 1]，top right Stack [0, 1, 2]，top right Stack [0, 1, 2, 3]，top right Stack [0, 1, 2, 3, 4]，top right --------- Stack [0, 1, 2, 3]，top right複雜度分析
基本都在末尾操作，所以基本都是 O(1)。
(push 和 pop 由於涉及到擴容和縮容，所以上面的 O(1) 其實是均攤的)
普通隊列
同樣是一個操作受限的容器
基本特性
感覺就一條 FILO 。
應用舉例
我接觸的用到的隊列，要麼是支援並發操作的並發隊列，由於加鎖，所以並發性並不是很好。
另外一種就是非同步任務隊列，即把工作加入隊列，由外部 IO 介面讀取(可能是多個執行緒，也可能是多路復用的讀)
哦，個人在廣度優先遍歷時用過。(需要統計相關目錄及其子目錄的各種各樣語言的程式碼量，此時把子目錄加入到隊列尾部，然後不斷出隊檢查當前目錄的文件)
順序隊列實現
- 定義好介面，底層實現用
動態數組完成介面中的方法 - 入隊
enqueue，出隊dequeue為核心 (不必擔心滿和空，因為一個在數組尾部操作，一個在數組頭部操作，空間夠不夠底層數組負責)
介面及其實現 如下:
//介面 public interface Queue<E> { boolean isEmpty(); int getSize(); E dequeue(); E getFront(); void enqueue(E e); } public class ArrayQueue<E> implements Queue<E> { private AdvanceDynamicArray<E> array; public ArrayQueue(int capacity) { array = new AdvanceDynamicArray<>(capacity); } public ArrayQueue() { array = new AdvanceDynamicArray<>(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public int getSize() { return array.getSize(); } @Override public E dequeue() { return array.popLeft(); } @Override public E getFront() { return array.getFirst(); } @Override public void enqueue(E e) { array.append(e); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue: ["); for(int i = 0; i< array.getSize(); i++) { res.append(array.get(i)); if(i != array.getSize() - 1) { res.append(", "); } } res.append("]，tail"); return res.toString(); } //測試看看 public static void main(String[] args) { ArrayQueue<Integer> queue = new ArrayQueue<>(); //放入元素 for(int i = 0; i< 10; i++) { queue.enqueue(i); System.out.println(queue); //放入一個元素，查看一次隊列 } //出棧試試 System.out.println("--------"); queue.dequeue(); System.out.println(queue); } }輸出結果:
Queue: [0]，tail Queue: [0, 1]，tail Queue: [0, 1, 2]，tail Queue: [0, 1, 2, 3]，tail Queue: [0, 1, 2, 3, 4]，tail Queue: [0, 1, 2, 3, 4, 5]，tail Queue: [0, 1, 2, 3, 4, 5, 6]，tail Queue: [0, 1, 2, 3, 4, 5, 6, 7]，tail Queue: [0, 1, 2, 3, 4, 5, 6, 7, 8]，tail Queue: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]，tail -------- Queue: [1, 2, 3, 4, 5, 6, 7, 8, 9]，tail複雜度分析
其實就是出隊的時候，從頭部出，涉及到移動(覆蓋元素)，所以為 O(n)
其他操作都只在尾部進行，所以都是 O(1)，其中尾部 enqueue 是均攤。總體來說，這個出隊的消耗時間太大了。如果要 底層實現不變，可以實現其他隊列，減少移動次數。
循環隊列
循環隊列是如何減少移動操作？
出隊一定要移動元素么？ 如果只移動記錄隊首的標記，這樣會不好好一點？
- 嘗試移動標記隊首、隊尾的標誌(索引)
循環隊列有一個非常重要的點，區分隊列滿、隊列空的條件:
- 隊列滿
(tail+1)%capacity == front - 隊列空
tail == front
人為的浪費一個空間，不存元素，和隊列空條件區分開。(否則隊列滿和空都能用 tail == front 來判斷，無法區分)
基本原理
其實也就是相對於普通隊列而言，支援其優化的理由在哪裡。
首先老規矩，front 肯定指向的是第一個元素，tail 肯定執行的是最後一個元素的後一個位置，大致如下圖:
也即是說，還是基於順序存儲的結構，新增兩個變數記錄隊首和隊尾的索引。
然後看一下 tail 和 front 都是怎麼變？ 一句話總結:
- 添加元素 tail++ ((tail+1)%capacity)
- 刪除元素 front++ ((front+1)%capacity)
在隊列中移動索引，front 或者 tail， 都要取模，以免越界。
細說，初始狀態，沒有元素，兩者都指向索引為 0 的位置，然後添加元素 tail++，不斷添加不斷++；當且僅在隊首出元素的時候，front++。
此時出隊就不需要移動元素覆蓋前面的了，直接移動索引 front 即可。然後就出現這樣的狀況:
發現前面有可用的空間，然後也還會出現這樣的狀態:
然後再往裡面扔一個元素試試，結果就循環了:
那再放一個呢？隊列滿了。
(因為前面說過認為的空出一個空間，讓隊列滿和隊列空區分開來)
這裡的擴容怎麼設計？需要修改底層動態數組么？
原始的動態數組方式，即使它擴容，也無法改變 front 和 tail 關係，所以不適用。
(且擴容拷貝的時候，也要考慮偏移，即取模問題)
具體實現
先把基於 Queue 介面把框架寫出來，然後填補 enqueue 和 dequeue 方法。
public class LoopQueue<E> implements Queue<E> { //內部自己維護一個數組 private E[] data; private int front, tail; //front 指向頭，tail 指向隊尾的下一個元素 private int size; //其實可以用通過 front, tail 實現，但複雜，容易出錯 public LoopQueue(int capacity){ data = (E[]) new Object[capacity+1]; //因為要故意浪費一個空間 front = tail = 0; size = 0; } public LoopQueue(){ data = (E[]) new Object[10+1]; //因為要故意浪費一個空間，默認存儲10個元素 front = tail = 0; size = 0; } //外部能感知的實際能存儲的 capacity public int getCapacity() { return data.length -1; //注意是 data.length 少一個 } //快捷方法，判斷隊列滿 -- 用戶不用關心，client始終可以放入 (因為會動態擴容) private boolean isFull() { //return (tail+1)%getCapacity() == front; return (tail+1)%data.length == front; //判斷隊列滿，用實際的 data.length 判斷 } @Override public boolean isEmpty() { //return size == 0; return front == tail; //特別注意隊列為空的條件 } @Override public int getSize() { return size; //專門有一個變數維護 } @Override public E getFront() { //但凡要取元素，都要看看是否為空 if(isEmpty()){ throw new IllegalArgumentException("隊列為空，不能出隊"); } return data[front]; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("Queue: size=%d, capacity=%dn", size, getCapacity())); res.append("front ["); /* for (int i = 0; i < size; i++) { res.append(data[i]); if (i != size - 1) { res.append(", "); } } */ //相對於 front 偏移的方式也是可以的 data[(i+front)%data.length] for (int i = front; i != tail; i = (i+1)%data.length) { res.append(data[i]); if ((i+1)%data.length != tail) { //不是最後一個元素之前的一個元素 res.append(", "); } } res.append("] tail"); return res.toString(); } // ---------------------- TODO @Override public E dequeue() { //TODO return null; } @Override public void enqueue(E e) { //TODO } }上面的遍歷方式也可以用取模偏移來寫。
然後實現遺留下來的兩個 TODO:
入隊，先看隊列是否為滿。
- 如果滿，則重新分配空間，此時新空間自然應該從 0 開始放元素:
@Override public void enqueue(E e) { //添加之前，先要看看隊列是否是滿的 if (isFull()) { //拋出異常 or 動態擴容(包括移動元素) resize(2 * getCapacity()); //當前實際佔用空間*2 } //入隊列 //data[tail++] = e; // tail++ 可能超過了 data.length data[tail] = e; tail = (tail + 1) % data.length; size++; } private void resize(int newCapacity) { //改變容量，然後移動元素，重置索引 E[] newData = (E[]) new Object[newCapacity + 1]; //複製: 把舊的元素，放入新的數組 //新數組的索引是從 0 -> size 的 for (int i = 0; i < size; i++) { //newData[i] = data[?]; newData[i] = data[(front + i) % data.length]; //索引移動，用的是data.length 判斷 } //重置索引 front = 0; tail = size; //實際個數是不變的 data = newData; //data.length 變化了，所以 getCapacity() 自然也變了 }出隊 操作，先看隊列是否為空:
- 如果為空，不返回或者拋出異常
@Override public E dequeue() { //先看看是否為空 if(isEmpty()){ throw new IllegalArgumentException("隊列為空，不能出隊"); } E ret = data[front]; //最好還是把 data[front] 處理一下 data[front] = null; front = (front+1)%data.length; size--; // 是否需要縮減容量 return ret; }其實還沒有完，如果一直出列，size 比 data.length 小太多，則有必要縮減容量。
即在出隊 dequeue 的程式碼中有必要添加 是否需要縮減容量 這一段:
@Override public E dequeue() { //先看看是否為空 if(isEmpty()){ throw new IllegalArgumentException("隊列為空，不能出隊"); } E ret = data[front]; //最好還是把 data[front] 處理一下 data[front] = null; front = (front+1)%data.length; size--; //縮減容量(lazy 縮減)，當實際存儲為 1/4 capacity時，capacity縮減為一半 if(size == getCapacity()/4 && getCapacity()/2 != 0) { resize(getCapacity()/2); //縮減後的容量不能為0 } return ret; }測試看看:
public static void main(String[] args) { LoopQueue<Integer> queue = new LoopQueue<>(); //默認實際存儲 10 個元素 //存儲 11 個元素看看 for(int i=0; i<11; i++){ queue.enqueue(i); System.out.println(queue); // 在 10 個元素滿的時候回擴容 } //出隊試試 System.out.println("------"); queue.dequeue(); System.out.println(queue); //出隊到只剩 5 個元素，即 20/4 時，縮減容量 queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); // 6, 7, 8, 9 10 System.out.println(queue); //此時容量變為 10 了 }運行結果:
Queue: size=1, capacity=10 front [0] tail Queue: size=2, capacity=10 front [0, 1] tail Queue: size=3, capacity=10 front [0, 1, 2] tail Queue: size=4, capacity=10 front [0, 1, 2, 3] tail Queue: size=5, capacity=10 front [0, 1, 2, 3, 4] tail Queue: size=6, capacity=10 front [0, 1, 2, 3, 4, 5] tail Queue: size=7, capacity=10 front [0, 1, 2, 3, 4, 5, 6] tail Queue: size=8, capacity=10 front [0, 1, 2, 3, 4, 5, 6, 7] tail Queue: size=9, capacity=10 front [0, 1, 2, 3, 4, 5, 6, 7, 8] tail Queue: size=10, capacity=10 front [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] tail Queue: size=11, capacity=20 front [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] tail ------ Queue: size=10, capacity=20 front [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] tail Queue: size=5, capacity=10 front [6, 7, 8, 9, 10] tail實現總結
- 開闢內部數組時，data.length 始終要比指定的
capacity多一個- 即便是 resize，也是
new Object[newCapacity + 1]
- 即便是 resize，也是
- 隊列空
front == tail，隊列滿(tail+1)%capacity == tail - 滿、空的判斷都要放在前面(enqueue, dequeue)
- 索引的移動都要取模，包括 tail 和 front
此時，出隊的複雜度也變為 O(1) 了(因為根本沒有移動元素)。
複雜度分析
還分析啥？因為普通隊列 dequeue 時要移動元素，O(n)，所以這裡才會拉扯一個循環隊列。
所以除了 dequeue 是均攤的 O(1) 以及 enqueue 均攤O(1)，其他操作都是 O(1)。
(鏈式存儲的部分，後續再補充進來)
如果有不正確的地方，歡迎批評指正。
以防萬一，我這裡還是把相關程式碼上傳到 gayhub 上了。
