數據結構與算法系列——隊列

什麼是隊列

隊列也是一種操作受限制的線性表，只允許在表的前端進行刪除，也就是出隊，而在表的後端進行插入，即入隊。

舉一個生活中常見的例子，我們經常會遇到排隊辦事，先來的排在前邊先辦理，後來的排在後邊，不允許插隊。先進先出，這就是典型的隊列。

隊列的實現

隊列的概念很容易理解，操作也比較簡單，很容易掌握。

跟棧一樣，隊列也能用數組和鏈表來實現，用數組實現的隊列叫順序隊列，用鏈表實現的隊列叫鏈式隊列。

下面我們先來看一下用數組的實現方式。

public class ArrayQueue {
 private String[] items;
 private int n = 0;
 private int head = 0;
 private int tail = 0;
 public ArrayQueue(int n){
 items = new String[n];
 this.n = n;
 }
 public boolean Enqueue(String item){
 if(tail == n){
 return false;
 } 

 items[tail++] = item;
 return true;
 }
 public String Dequeue(){
 if(head == tail){
 return null;
 }
 String item = items[head++];
 return item;
 }
}

隊列的數組實現比棧的實現稍微複雜一點點，隊列需要兩個指針，一個指向隊頭的 head 指針，一個指向隊尾的 tail 指針。同樣老辦法，我們用畫圖來更清楚的瞭解一下這個過程。

image.png

如果這個時候我們調用一次出隊，那麼 head 指針就指向 1 的位置，並把 0 的位置的元素移除出隊。如圖。

image.png

如果這個時候插入一個新的元素，那麼 tail 指針就指向 5 的位置，然後把新的元素放到 4 的位置。

image.png

我們通過圖可以看到，這種實現方法有一個缺點，那就是隨著我們不斷的入隊操作，等到 tail 指向最後一位的時候就沒有辦法接受新的元素入隊了，即使前邊有空閒的空間沒有元素。所以我們來優化一下我們的代碼，當 tail 等於數組的長度 n 的時候，這個時候如果再有新的元素入隊，我們就看數組前邊是不是有空閒的空間，如果有我們就把隊列的元素整體向前移動幾個單位。

public class ArrayQueue {
 private String[] items;
 private int n = 0;
 private int head = 0;
 private int tail = 0;
 public ArrayQueue(int n){
 items = new String[n];
 this.n = n;
 }
 public boolean Enqueue(String item){
 if(tail == n){
 if(head == 0){
 return false;
 }
 for (int i = head; i<tail> items[i-head] = items[I];
 }
 tail -= head;
 head = 0;
 }
 items[tail++] = item;
 return true;
 }
 public String Dequeue(){
 if(head == tail){
 return null;
 }
 String item = items[head++];
 return item;
 }
}
/<tail>

老辦法，畫圖來展示這一過程。

image.png

這樣就不會有空間的浪費了，但是還有個問題就是數組不能動態擴展，數組滿了之後就不能再入隊新的元素了，我們來再來修改一下讓數組支持動態擴展。當數組滿了的時候我們重新申請一個新的數組，長度為原數組的兩倍，然後把原數組的元素移到新數組裡，然後再進行入隊操作。

public class ArrayQueue {
 private String[] items;
 private int n = 0;
 private int head = 0;
 private int tail = 0;
 private String[] newItems;
 public ArrayQueue(int n){
 items = new String[n];
 this.n = n;
 }
 public boolean Enqueue(String item){
 if(tail == n){
 if(head == 0){
 newItems = new String[2*n];
 for (int i=0;i<tail> newItems[i] = items[I];
 }
 items = newItems;
 }else {
 for (int i = head; i < tail; i++) {
 items[i - head] = items[I];
 }
 tail -= head;
 head = 0;
 }
 }
 items[tail++] = item;
 return true;
 }
 public String Dequeue(){
 if(head == tail){
 return null;
 } 

 String item = items[head++];
 return item;
 }
}
/<tail>

同樣，上圖。

image.png

還有一種特殊的數組實現是循環隊列，當 tail == n 的時候我們不遷移數組的元素，而是去看數組下標為 0 的位置為不為空，如果為空的話我們直接入隊新的元素，tail 就等於 1 。我們來看一下代碼實現。

public class CycleArrayQueue {
 private String[] items;
 private int n;
 private int head = 0;
 private int tail = 0;
 public CycleArrayQueue(int n){
 items = new String[n];
 this.n = n;
 }
 public boolean Enqueue(String item){
 //數組滿了
 if((tail+1)%n == head)
 return false;
 items[tail] = item;
 tail = (tail+1)%n;
 return true;
 }
 public String Dequeue(){
 if(head == tail) return null;
 String str = items[head];
 head = (head+1)%n;
 return str;
 }
}

下邊我們來看一下隊列的鏈表實現，同樣我們需要兩個指針，head 指向鏈表第一個結點，tail 指向鏈表最後一個結點。入隊時 tail->next=new_node，tail=tail->next。出隊時 head=head->next。

public class ListNodeQueue {
 private ListNode head;
 private ListNode tail;
 public void Enqueue(String val){
 ListNode node = new ListNode(val, null);
 if(tail == null){
 head = node;
 tail = node;
 }else {
 tail.next = node;
 tail = tail.next;
 }
 }
 public String Dequeue(){
 if(head == null){
 return null; 

 }
 String string = head.val;
 head = head.next;
 if(head == null){
 tail = null;
 }
 return string;
 }
 class ListNode{
 private String val;
 private ListNode next;
 public ListNode(String x, ListNode next) {
 val = x;
 this.next = next;
 }
 public String GetValue() {
 return val;
 }
 }
}

隊列的應用

前邊將的都是一些基本的理論知識，那隊列在實際的項目中都在什麼情況下使用呢？阻塞隊列和併發隊列應用的比較廣泛。

• 阻塞隊列
• 阻塞隊列實際就是在隊列的基礎上加上了阻塞操作，當隊列為空時，出隊操作就會被阻塞，因為隊列裡沒有數據，直到隊列裡有數據之後才能返回；當隊列滿的時候，入隊操作就會被阻塞，直到隊列中有空閒的空間時再執行入隊操作。
• 我們可以用阻塞隊列很容易的實現一個”生產者-消費者“模型，這樣我們可以有效的控制生產和消費的速度。當生產者生產的過快時，隊列很快就滿了，這個時候生產者就阻塞等待，直到消費者消費了，生產者才會被喚醒繼續生產。反之消費者消費過快時也同樣被阻塞。不僅如此，我們還可以通過調整生產者和消費者的個數，來實現生產和消費的供需平衡。
• 併發隊列
• 在多線程應用中，多個線程同時操作隊列，就會存在線程安全問題，處理這個問題的隊列我們稱為併發隊列。最簡答的方法就是在入隊和出隊的時候加鎖，保證同時只有一個線程執行隊列的入隊或出隊，但是這樣以來就會大大降低線程的併發度。
• 我們可以用上邊提到的數組實現的循環隊列來解決這個問題，利用 CAS 的原子操作，可以實現非常高效的併發隊列。因此，循環隊列比鏈式隊列應用的更為廣泛。