下面我們就是用數(shù)組實現(xiàn)一個隊列速勇，Java代碼如下：

// 用數(shù)組實現(xiàn)的隊列
public class ArrayQueue {
  // 數(shù)組：items晌砾，數(shù)組大小：n
  private String[] items;
  private int n = 0;
  // head 表示隊頭下標(biāo)烦磁，tail 表示隊尾下標(biāo)
  private int head = 0;
  private int tail = 0;

  // 申請一個大小為 capacity 的數(shù)組
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入隊
  public boolean enqueue(String item) {
    // 如果 tail == n 表示隊列已經(jīng)滿了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出隊
  public String dequeue() {
    // 如果 head == tail 表示隊列為空
    if (head == tail) return null;
    // 為了讓其他語言的同學(xué)看的更加明確养匈，把 -- 操作放到單獨一行來寫了
    String ret = items[head];
    ++head;
    return ret;
  }
}

對于使用數(shù)組實現(xiàn)隊列相比使用實現(xiàn)棧要復(fù)雜一點，接下來我們一起理解一下實現(xiàn)的思路：
對于棧來說都伪，只需要一個棧頂指針就可以了呕乎。但是對于隊列來講，需要兩個指針：一個是head指針陨晶，指向隊頭猬仁，一個tail指針，指向隊尾先誉。

接下來湿刽，我們一起理解一下：
結(jié)合下圖，當(dāng)a,b,b,d依次入隊后褐耳，隊列中的head指針指向下標(biāo)為0的位置诈闺，tail指針指向下標(biāo)為4的位置。

image.png

當(dāng)我們調(diào)用兩次出隊的操作之后铃芦，隊列中head指針指向下標(biāo)為2的位置雅镊，tail指針不變

image.png

大家肯定發(fā)現(xiàn)了襟雷，隨著不停的入隊、出隊操作漓穿，head和tail都會持續(xù)往后移動嗤军。當(dāng)tail移到最右邊的時候，即使隊列中還有空閑空間晃危，也無法繼續(xù)往隊列里添加數(shù)據(jù)了叙赚。該如何解決呢？這就會用到我們之前文章中說過的僚饭，數(shù)組刪除操作會導(dǎo)致數(shù)據(jù)不連續(xù)的問題的解決方法了震叮，那就是數(shù)據(jù)搬移。但是每次出隊操作都會刪除數(shù)組下標(biāo)為0的元素鳍鸵，就要搬移整個隊列中的數(shù)據(jù)苇瓣，這樣出隊的時間復(fù)雜度就會從原來的O(1)變成O(n)。所以我們需要優(yōu)化一下偿乖，我們在出隊的時候不用搬移數(shù)據(jù)击罪。如果沒空間了，我們只需要在入隊的時候贪薪，在集中觸發(fā)一次數(shù)據(jù)搬移操作媳禁。借助這個思想，出隊的函數(shù)dequeue()保持不變画切，我們稍加改造一下入隊函數(shù)enqueue()的實現(xiàn)竣稽，就可以解決剛才的問題
Java代碼如下：

   // 入隊操作，將 item 放入隊尾
  public boolean enqueue(String item) {
    // tail == n 表示隊列末尾沒有空間了
    if (tail == n) {
      // tail ==n && head==0霍弹，表示整個隊列都占滿了
      if (head == 0) return false;
      // 數(shù)據(jù)搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新 head 和 tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }

image.png

這種實現(xiàn)的過程中毫别，出隊的時間復(fù)雜度仍然是O(1)，但是入隊操作的時間復(fù)雜度還是O(1)么典格？我們可以根據(jù)之前的文章岛宦，自己分析一下。

接下來我們再來看一下基于鏈表的隊列實現(xiàn)方式：
基于鏈表的實現(xiàn)方式钝计，我們還是需要兩個指針：head指針和tail指針恋博，他們分別指向鏈表的第一個結(jié)點和最后一個結(jié)點。如下圖所示私恬，入隊時债沮，tail->next=new_node,tail=tail->next;出隊時head=head->next。示意圖如下：

image.png

循環(huán)隊列

剛才用數(shù)組實現(xiàn)隊列的時候本鸣，當(dāng)tail=n的時候疫衩，就會有數(shù)據(jù)搬移的操作，入隊操作的效率就會受到影響荣德，所以我們想用另一種方法解決這個問題闷煤。那就是循環(huán)隊列童芹，顧名思義，循環(huán)隊列就是一個環(huán)狀的鲤拿，就是將剛剛的數(shù)組的頭和尾連接到一起假褪，組成一個環(huán)形的隊列，可以參考下圖：

image.png

如上圖近顷，我們可以看見隊列的大小為8生音，head現(xiàn)在指向4的位置，tail指向7的位置窒升，如果現(xiàn)在有a缀遍，b兩個元素需要入隊，a就會放到7的位置饱须，而這時tail不更新為8域醇，而是更新為0，在將b放在下標(biāo)為0的位置上蓉媳，這樣就避免的數(shù)據(jù)搬移的操作譬挚。這種情況是很好理解的，但是編碼程度上會比非循環(huán)隊列難得多酪呻。關(guān)鍵的代碼就是需要正確的判斷隊滿和隊空的條件

image.png

在非循環(huán)隊列中殴瘦，我們判斷隊滿的條件是tail == n，隊空的條件是head == tail号杠。接下來我們總結(jié)一下循環(huán)隊列的隊滿和對空的判斷條件。
對空的判斷條件還是head == tail丰歌，但是隊滿的條件就不一樣了姨蟋，是(tail+1)%n = head
但是有一個問題，就是當(dāng)隊滿的時候立帖，上圖中tail指針位置是沒有存儲數(shù)據(jù)眼溶，所以循環(huán)隊列會浪費一個數(shù)據(jù)的存儲空間。
代碼如下：

public class CircularQueue {
  // 數(shù)組：items晓勇，數(shù)組大刑梅伞：n
  private String[] items;
  private int n = 0;
  // head 表示隊頭下標(biāo)，tail 表示隊尾下標(biāo)
  private int head = 0;
  private int tail = 0;

  // 申請一個大小為 capacity 的數(shù)組
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入隊
  public boolean enqueue(String item) {
    // 隊列滿了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出隊
  public String dequeue() {
    // 如果 head == tail 表示隊列為空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

阻塞隊列和并發(fā)隊列

隊列相關(guān)的知識基本上就是理論知識绑咱，平時的應(yīng)用開發(fā)上也很少會用上绰筛，因為隊列這種數(shù)據(jù)結(jié)構(gòu)很基礎(chǔ)。但是有一些特殊的隊列的應(yīng)用就比較廣泛了描融，比如阻塞隊列和并發(fā)隊列
阻塞隊列就是在隊列的基礎(chǔ)上添加了阻塞操作铝噩。解釋一下：就是當(dāng)隊空的時候，從隊頭取數(shù)據(jù)就會被阻塞窿克，因為當(dāng)前隊列中沒有數(shù)據(jù)可以取骏庸，所以需要等隊列中有數(shù)據(jù)了才能返回毛甲。當(dāng)隊滿的時候，入隊操作就會被阻塞具被，需要等隊列中有空閑位置后在進行入隊操作玻募，再返回。

image.png

上述的操作其實就是一個"生產(chǎn)者-消費者模型"一姿，所以我們可以使用阻塞隊列七咧，輕松實現(xiàn)一個"生產(chǎn)者-消費者模型"！

這種基于阻塞隊列實現(xiàn)的"生產(chǎn)者-消費者模型"啸蜜，可以有效的協(xié)調(diào)生產(chǎn)和消費的速度坑雅。當(dāng)生產(chǎn)者生產(chǎn)過快，消費者來不及消費的時候衬横，隊列就會滿裹粤，這時候就會阻塞隊列，等消費者消費了之后蜂林，在喚醒生產(chǎn)者遥诉。。噪叙。

不僅如此矮锈，基于阻塞隊列，我們還可以協(xié)調(diào)“生產(chǎn)者”和“消費者”的個數(shù)睁蕾，來提高數(shù)據(jù)處理效率苞笨。根據(jù)前面的例子我們可以考慮配置多個消費者，來應(yīng)對一個生產(chǎn)者子眶。

image.png

接下來一起了解一下瀑凝，多線程的情況下，會有多個線程同時操作隊列臭杰，這時候就會存在線程安全問題粤咪，那又如何保證線程安全呢？

線程安全的隊列我們又叫做并發(fā)隊列渴杆，最簡單的方法就是在入隊enqueue()和出隊dequeue()方法上面加鎖寥枝，但是鎖的力度大，并發(fā)度會降低磁奖，同一時刻只允許一個存或取的操作囊拜。實際上，基于數(shù)組的循環(huán)隊列比搭，利用CAS原子操作艾疟，可以實現(xiàn)非常高效的并發(fā)隊列。這也是循環(huán)隊列比鏈?zhǔn)疥犃袘?yīng)用更廣泛的原因。

解答開篇的問題蔽莱，如果線程池中沒有空閑的資源了弟疆，我們一般有兩種策略，第一：非阻塞處理方式盗冷，直接拒絕任務(wù)請求怠苔；第二：阻塞處理方式，將請求排隊仪糖，等有空閑線程時柑司，取出排隊的請求繼續(xù)處理。

那如何存儲排隊請求呢锅劝？
我們?yōu)榱斯教幚砻總€排隊的請求攒驰，先進者先服務(wù)，就會用到隊列這種數(shù)據(jù)結(jié)構(gòu)來存儲請求故爵。前面說過隊列又有兩種實現(xiàn)方式玻粪，基于鏈表的的實現(xiàn)方式和基于數(shù)組的實現(xiàn)方式。

二者又有什么區(qū)別呢诬垂？
基于鏈表的實現(xiàn)方式劲室，可以實現(xiàn)一個無限量的無界隊列，但是可能到時排隊的請求過多结窘，導(dǎo)致響應(yīng)時間過長很洋。所以針對響應(yīng)時間敏感的系統(tǒng)，用鏈表方式實現(xiàn)的隊列就不合適了隧枫。而基于數(shù)組實現(xiàn)的有界隊列喉磁，隊列有大小，所以線程池中排隊的請求超過隊列的大小時官脓，接下來的請求就會直接別拒絕线定，所以針對響應(yīng)時間敏感的系統(tǒng)，這種方式就相對合適了确买。不過，設(shè)置一個合理的隊列大小也是很有講究的纱皆。隊列太大導(dǎo)致等待的請求太多湾趾，隊列太小會導(dǎo)致無法充分利用系統(tǒng)資源、發(fā)揮最大性能派草。

隊列應(yīng)用除了前面說的在線程池請求排隊的場景之外搀缠，還可以應(yīng)用在任何有限資源池中，用于排隊請求近迁，比如數(shù)據(jù)庫連接池等實際上艺普，對于大部分資源有限的場景，當(dāng)沒有空閑資源時剿骨，基本上都可以通過“隊列”這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)請求排隊抗悍。