特性

先進(jìn)者先出蚜枢，這就是典型的“隊列”。

分類

循環(huán)隊列

• 定義：循環(huán)隊列针饥，顧名思義厂抽，它長得像一個環(huán)。原本數(shù)組是有頭有尾的丁眼，是一條直線】攴铮現(xiàn)在我們把首尾相連，扳成了一個環(huán)苞七。優(yōu)點：可以解決順序隊列中tail == null 出現(xiàn)數(shù)據(jù)搬移的問題藐守。

循環(huán)隊列

解釋：圖中這個隊列的大小為 8，當(dāng)前 head=4莽鸭，tail=7吗伤。當(dāng)有一個新的元素 a 入隊時，我們放入下標(biāo)為 7 的位置硫眨。但這個時候足淆，我們并不把 tail 更新為 8，而是將其在環(huán)中后移一位礁阁，到下標(biāo)為 0 的位置巧号。當(dāng)再有一個元素 b 入隊時，我們將 b 放入下標(biāo)為 0 的位置姥闭，然后 tail 加 1 更新為 1丹鸿，通過這樣的方法，我們成功避免了數(shù)據(jù)搬移操作棚品。

注意事項：

• 循環(huán)隊列實現(xiàn)需要：確定好隊空和隊滿的判定條件

1. 隊空的判斷條件是： head == tail
2. 隊滿的判斷條件是：(tail+1)%n=head

• 當(dāng)隊列滿時靠欢，圖中的 tail 指向的位置實際上是沒有存儲數(shù)據(jù)的廊敌。所以，循環(huán)隊列會浪費一個數(shù)組的存儲空間门怪。

  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;
    }
  }
  

阻塞隊列

定義：在隊列基礎(chǔ)上增加了阻塞操作肋殴。簡單來說，就是在隊列為空的時候坦弟，從隊頭取數(shù)據(jù)會被阻塞护锤。因為此時還沒有數(shù)據(jù)可取，直到隊列中有了數(shù)據(jù)才能返回酿傍；如果隊列已經(jīng)滿了烙懦，那么插入數(shù)據(jù)的操作就會被阻塞，直到隊列中有空閑位置后再插入數(shù)據(jù)拧粪，然后再返回修陡。

案例：基于阻塞隊列，輕松實現(xiàn)一個“生產(chǎn)者 - 消費者模型”可霎！

阻塞隊列

并發(fā)隊列

定義：線程安全的隊列我們叫作并發(fā)隊列。最簡單直接的實現(xiàn)方式是直接在 enqueue()宴杀、dequeue() 方法上加鎖癣朗，但是鎖粒度大并發(fā)度會比較低，同一時刻僅允許一個存或者取操作旺罢。實際上旷余，基于數(shù)組的循環(huán)隊列，利用 CAS 原子操作扁达，可以實現(xiàn)非常高效的并發(fā)隊列正卧。這也是循環(huán)隊列比鏈?zhǔn)疥犃袘?yīng)用更加廣泛的原因。

案例：Disruptor

小結(jié)

隊列最大的特點就是**先進(jìn)先出**跪解，主要的兩個操作是**入隊**和**出隊**炉旷。跟棧一樣，它既可以用數(shù)組來實現(xiàn)叉讥，也可以用鏈表來實現(xiàn)窘行。用數(shù)組實現(xiàn)的叫**順序隊列**，用鏈表實現(xiàn)的叫**鏈?zhǔn)疥犃?*图仓。特別是長得像一個環(huán)的**循環(huán)隊列**罐盔。在數(shù)組實現(xiàn)隊列的時候，會有數(shù)據(jù)搬移操作救崔，要想**解決數(shù)據(jù)搬移**的問題惶看，我們就需要像環(huán)一樣的循環(huán)隊列捏顺。

**循環(huán)隊列**是我們這節(jié)的重點。要想寫出沒有 bug 的循環(huán)隊列實現(xiàn)代碼纬黎，關(guān)鍵要**確定好隊空和隊滿的判定條件**幅骄，具體的代碼你要能寫出來。

**阻塞隊列**就是入隊莹桅、出隊操作可以阻塞昌执，**并發(fā)隊列**就是隊列的操作多線程安全。

案例：

用棧實現(xiàn)隊列

class MyQueue {
        //題意要求使用兩個棧(先進(jìn)后出)來實現(xiàn)隊列（先進(jìn)先出）诈泼，思路：設(shè)置一個入隊棧懂拾，一個出隊棧，如果有數(shù)據(jù)過來铐达，保存到入堆棧中岖赋，如果有需要去除數(shù)據(jù)，則從出隊棧取出瓮孙，出隊棧如果沒有數(shù)據(jù)唐断，將入堆棧中的數(shù)據(jù)一次壓入出隊棧中棧(PS：此操作通過將入隊棧的數(shù)據(jù)搬移到出隊棧實現(xiàn)了將先先進(jìn)先出的特性)
    private Stack<Integer> enqueue = new Stack<>();
    private Stack<Integer> dequeue = new Stack<>();

    /** Initialize your data structure here. */
    public MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        enqueue.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(!dequeue.isEmpty()){
            return dequeue.pop();
        }
        if(enqueue.isEmpty()){
            return 0;
        }else{
            while(!enqueue.isEmpty()){
                dequeue.push(enqueue.pop());
            }
            return dequeue.pop();
        }
    }
    
    /** Get the front element. */
    public int peek() {
        if(!dequeue.isEmpty()){
            return dequeue.peek();
        }
        if(enqueue.isEmpty()){
            return 0;
        }else{
            while(!enqueue.isEmpty()){
                dequeue.push(enqueue.pop());
            }
            return dequeue.peek();
        }
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return enqueue.isEmpty() && dequeue.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

推薦結(jié)果打散

題目：存在一個推薦視頻v和圖片p的系統(tǒng)，現(xiàn)在需要對推薦系統(tǒng)結(jié)果進(jìn)行打散杭抠，要求圖片p的結(jié)果每n個里面出現(xiàn)一次脸甘，并且保證圖片最早出現(xiàn)的位置不變，圖片之前的相對位置不變偏灿。

案例1：v_0,v_1,v_2,p_3,p_4,p_5,v_6,p_7,v_8,v_9;要求：每3個里面存著一個圖片丹诀，最后不滿足的圖片刪掉；
v_0,v_1,v_2,p_3,v_6,v_8,p_4,v_9

class Solution{
  /**
     * 推薦結(jié)果打散
     * //分析：根據(jù)題意要求：視頻和圖片原來相對先后順序保持不變,所以選擇隊列這種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)翁垂；
     * 1铆遭、如果原集合中開始是視頻則，直接添加到返回結(jié)果沿猜；
     * 2枚荣、如果遇到圖片則按照規(guī)則--即每maxInterval中添加一個圖片；
     *
     * @param videoAndPicList 圖片和視頻混合集合
     * @param maxInterval     最大間隔
     * @return
     */
    public static List<String> getRecommendenResult(List<String> videoAndPicList, int maxInterval) {
        List<String> result = new ArrayList<>();

        //邊界條件
        if(videoAndPicList == null || videoAndPicList.isEmpty()){
            return result;
        }

        //定義兩個隊列
        Deque<String> videoDeque = new LinkedList<>();
        Deque<String> picDeque = new LinkedList<>();


        int index = 0;
        int size = videoAndPicList.size();

        //如果原集合中開始是視頻則啼肩，直接添加到返回結(jié)果
        while(index < size && isVidieo(videoAndPicList.get(index))){
            result.add(videoAndPicList.get(index));
            index++;
        }

        //將混合結(jié)果拆分到相應(yīng)的隊列中
        for (int i = index; i < size; i++) {
            String clip = videoAndPicList.get(i);
            if(isVidieo(clip)){
                videoDeque.add(clip);
            }else {
                picDeque.add(clip);
            }
        }

        int current = result.size();

        while(!videoDeque.isEmpty() && !picDeque.isEmpty()){
            if(current < maxInterval){
                result.add(videoDeque.poll());
                current++;

            }else {
                result.add(picDeque.poll());
                current = 0;
            }
        }

        while(!videoDeque.isEmpty()){
            result.add(videoDeque.poll());
        }

        if(current >= maxInterval && !picDeque.isEmpty()){
            result.add(picDeque.poll());
        }

        return result;
    }

    /**
     * 判斷是否為視頻
     *
     * @param clip
     * @return
     */
    private static boolean isVidieo(String clip) {
        if(clip.indexOf("v") != -1){
            return true;
        }
        return false;
    }
}