看完這篇你還不知道這些隊列，我這些圖白作了
- 2019 年 10 月 3 日
- 筆記
隊列（queue）是一種採用先進先出(FIFO)策略的抽象數據結構，即最先進隊列的數據元素，同樣要最先出隊列。隊列跟我們排隊買票一樣，先來排隊的肯定先買票，後來排隊的的後買到票。隊列如下圖所示：
隊列有兩個重要的概念，一個叫隊頭，一個叫隊尾，隊頭指向的是第一個元素，而隊尾指向的是最後一個元素。隊列跟棧一樣也是訪問受限制的，所以隊列也只有兩個主要的操作：入隊(enqueue)操作 和 出隊(dequeue)操作 。入隊操作就是將一個元素添加到隊尾，出隊操作就是從隊頭取出一個元素。
隊列的底層實現可以用數組和鏈表，基於數組實現的隊列叫作順序隊列，基於鏈表實現的隊列叫作鏈式隊列，下面我們分別用數組和鏈表來簡單的實現這兩種隊列。
基於數組的隊列
不管使用那種方式來實現隊列，都需要定義兩個指針分別指向隊頭和隊尾，本文中我們用head指向隊頭，tail指向隊尾，後面的示例中這將默認使用這個，有特殊的地方我會進行說明，先來看看順序隊列的入隊、出隊操作。
圖中可以看出，入隊時，隊尾往後移動，隊頭保持不變，出隊是隊頭往後移動，隊尾保持不變。入隊、出隊操作的邏輯都比較簡單，可能你有疑問的地方是：出隊時為什麼隊頭要往後移動而不是一直指向數組下標為0的位置？ 為什麼呢？如果我們保持隊頭一直指向數組下標為0的位置，那每次出隊操作後，後面的數據都需要往前挪一位，換句話說每次出隊操作都需要進行數據遷移，而數據遷移的代價比較大，每次數據遷移的時間複雜度為O(n)，這樣會極大的影響隊列的使用性能。如果我們出隊時，隊頭往後移動一位，這樣我們就避免每次出隊都進行數據遷移，我們只需要在只有在tail等於數組大小且head不等於0時，進行一次數據遷移，將已經出隊留下的空間繼續供入隊時使用。下圖是數據遷移的過程：
數據遷移時，從head位置開始的數據都需要往前移動head位，這樣就把出隊後的空間騰出來，供後續入隊操作使用。
基於數組的隊列實現程式碼：
/** * 基於數組的隊列 */ public class ArrayQueue { // 存放數據的數組 private String[] items; // 容器的大小 private int size = 0; // 第一個節點 private int head = 0; // 最後一個節點 private int tail = 0; // 構造函數 public ArrayQueue(int size){ this.size = size; items = new String[size]; } /** * 入隊操作 * @param data * @return */ public int enqueue(String data){ // 如果最後一個節點等於容器大小，說明隊列滿了 /** * 判斷隊列滿了的條件，tail = size,head = 0, */ if (tail == size && head == 0) return -1; /** * 如果tail = size，但是head != 0,說明前有數據刪除，隊列未滿，需要數據遷移 */ if (tail == size){ // head 後面的數據都需要往前遷移 head 位 for (int i= head;i< size;i++){ items[i-head] = items[i]; } // 將最後一個元素遷移 head 位 tail -=head; // 第一個元素指向 0 head = 0; } // 向隊列中添加元素 items[tail] = data; tail++; return 1; } /** * 出隊操作 * @return */ public String dequeue(){ // 第一個元素和最後一個元素相等時，隊列為空 if (head == tail) return null; String result = items[head]; // 第一個元素後移一次，這樣做的好處是在出隊時不需要數據遷移 head ++ ; return result; } }鏈式隊列
鏈式隊列實現起來相對順序隊列來說要簡單很多，我們先來看看鏈式隊列的入隊、出隊操作：
從圖中可以看出鏈式隊列入隊操作是將tail的next指向新增的節點，然後將tail指向新增的節點，出隊操作時，將head節點指向head.next節點。鏈式隊列與順序隊列比起來不需要進行數據的遷移，但是鏈式隊列增加了存儲成本。
基於鏈表的隊列實現程式碼
/** * 基於鏈表的隊列 */ public class LinkQueue { // 指向隊首 private Node head; // 指向隊尾 private Node tail; /** * 入隊操作 * @param data * @return */ public int enqueue(String data){ Node node = new Node(data,null); // 判斷隊列中是否有元素 if (tail == null) { tail = node; head = node; }else { tail.next = node; tail = node; } return 1; } /** * 出隊操作 * @return */ public String dequeue(){ if (head==null) return null; String data = head.data; head = head.next; // 取出元素後，頭指針為空，說明隊列中沒有元素，tail也需要製為空 if (head == null){ tail = null; } return data; } class Node{ private String data; private Node next; public Node(String data,Node node){ this.data = data; next = node; } } }循環隊列
循環隊列是對順序隊列的改進，因為順序隊列不可避免的數據遷移操作，數據遷移操作會導致隊列的性能下降，為了避免這個問題，將隊列改造成循環的，當tail到達數組的最大下標時，重新指回數組下標為0的位置，這樣就避免了數據遷移。先來看看循環隊列的出隊、入隊操作：
因為隊列是循環隊列，所以在進行入隊、出隊操作時，就不能像順序隊列那樣對tail、head進行簡單的加1操作，我們需要對tail、head加1後與數組的大小進行求余操作，來得出tail、head的值，這樣才能進行循環操作。循環隊列需要犧牲一個存儲空間，對於一個存儲空間為n的循環隊列來說只能存放n-1為數據，因為如果不犧牲一個存儲空間的話，當tail==head時，就有可能存在隊空或者隊滿的情況。
循環隊列的實現程式碼
/** * 環形隊列,不需要數據遷移，提高性能 */ public class CircularQueue { // 存放數據的數組 private String[] items; // 容器的大小 private int size = 0; // 第一個節點 private int head = 0; // 最後一個節點 private int tail = 0; // 構造函數 public CircularQueue(int size){ this.size = size; items = new String[size]; } /** * 入隊操作 * @param data * @return */ public int enqueue(String data){ /** * 判斷環形隊列滿了的條件，(tail+1)求余等於head */ if ((tail+1)%size == head) return -1; // 向隊列中添加元素 items[tail] = data; // 因為是環形隊列，所以下邊是數組長度的餘數 tail= (tail+1)%size; return 1; } /** * 出隊操作 * @return */ public String dequeue(){ // 第一個元素和最後一個元素相等時，隊列為空 if (head == tail) return null; String result = items[head]; // 因為是環形隊列，所以下邊是數組長度的餘數 head = (head+1)% size ; return result; } }雙端隊列
雙端隊列是一種隊頭、隊尾都可以進行入隊、出隊操作的隊列，雙端隊列採用雙向鏈表來實現，先來看一下雙端隊列的入隊、出隊操作：
可以從動態圖中看出，雙端隊列的每一端都是一個棧，都符合棧先進後出的特性，如果我們對雙端隊列進行禁止隊頭入隊和隊尾出隊操作的限制，雙端隊列又變成了一個鏈式隊列，雙端隊列是一種多功能的數據結構，我們可以使用它來提供隊列和棧兩種功能。
雙端隊列的實現程式碼
/** * 雙端隊列，使用雙向鏈表實現 */ public class DoubleEndsQueue { private static class Node { String item; Node next; Node prev; Node(Node prev, String element, Node next) { this.item = element; this.next = next; this.prev = prev; } } // 第一個節點 private Node first; // 最後一個節點 private Node last; /* * 在第一個節點前面入隊 */ public void enqueueFirst(String e) { final Node f = first; final Node newNode = new Node(null, e, f); // 第一個節點指向新節點 first = newNode; if (f == null) // 最後一個節點也指向該節點 last = newNode; else // 當前節點的前節點指向新節點 f.prev = newNode; } /** * 在最後一個元素後面入隊 * @param e */ public void enqueueLast(String e) { final Node l = last; final Node newNode = new Node(l, e, null); // 最後一個節點指向新節點 last = newNode; if (l == null) // 第一個節點指向新節點 first = newNode; else // 當前節點的下節點指向新節點 l.next = newNode; } /** * 從第一個節點出隊 * @return */ public String dequeueFirst() { if (first == null) return null; final Node f = first; String element = f.item; Node next = f.next; f.item = null; f.next = null; // 第一個節點指向當先節點的next節點 first = next; if (next == null) // 說明隊列為空 last = null; else next.prev = null; return element; } /** * 從最後節點出隊 * @return */ public String dequeueLast() { final Node l = last; if (last == null) return null; String element = l.item; Node prev = l.prev; l.item = null; l.prev = null; last = prev; if (prev == null) first = null; else prev.next = null; return element; } // 輸出隊列全部內容 public void displayAll() { while (first !=null){ System.out.print(first.item+" "); first = first.next; } System.out.println("==============="); } } 優先隊列
優先隊列為一種不必遵循隊列先進先出(FIFO)特性的特殊隊列，優先隊列跟普通隊列一樣都只有一個隊頭和一個隊尾並且也是從隊頭出隊，隊尾入隊，不過在優先隊列中，每次入隊時，都會按照入隊數據項的關鍵值進行排序(從大到小、從小到大)，這樣保證了關鍵字最小的或者最大的項始終在隊頭，出隊的時候優先順序最高的就最先出隊，這個就像我們醫院就醫一樣，急救的病人要比普通的病人先就診。一起來看看優先隊列的出隊、入隊操作：
在示例中，我們規定數值越小優先順序越高。我們每執行一次入隊操作時，小的元素都會靠近頭隊，在出隊的時候，元素小的也就先出隊。
優先隊列的程式碼實現
這裡使用的數組實現優先隊列，用數組實現主要原因是更好理解優先隊列的思想。一般都是使用堆來實現優先隊列，因為數組實現在插入的時候對數據的排序代價比較大。
/** * 優先隊列 */ public class PriorityQueue { // 存放數據的數組 private Integer[] items; // 容器的大小 private int size = 0; // 第一個節點 private int head = 0; // 構造函數 public PriorityQueue(int size){ this.size = size; items = new Integer[size]; } /** * 入隊操作 * @param data * @return */ public int enqueue(Integer data){ int j; if (head == 0){ items[head++] = data; } else { for (j=head-1;j>=0;j--){ // 將小的數往後排 if (data > items[j]){ items[j+1] = items[j]; }else { break; } } items[j+1] = data; head++; } return 1; } public Integer dequeue(){ return items[--head]; } }總結
- 隊列是一種遵循先進先出(FIFO)的數據結構
- 隊列可以使用數組和鏈表實現，數組實現叫作順序隊列，鏈表實現叫作鏈式隊列
- 循環隊列解決了順序隊列的數據遷移帶來的性能損耗的問題
- 雙端隊列是隊頭和隊尾都可以進行入隊、出隊操作的隊列
- 優先隊列是一種不必遵循先進先出規則的隊列，任意元素加入時，都會講優先順序最高的放入到隊頭
最後
打個小廣告，歡迎掃碼關注微信公眾號：「平頭哥的技術博文」，一起進步吧。
