首先，題目都是出自leetcode的探索里的初級算法的課程。

嘿嘿，有心想學(xué)的請自行前往學(xué)習(xí)，光看是沒用的。

隊列：先入先出的數(shù)據(jù)結(jié)構(gòu)

show code

// "static void main" must be defined in a public class.
// java的入口函數(shù) static void main 必須定義在一個public類里

// 隊列實(shí)體
class MyQueue {
    // store elements
    // 存儲隊列內(nèi)容的List
    private List<Integer> data; 
    // a pointer to indicate the start position
    // 指向頭結(jié)點(diǎn)的標(biāo)識
    private int p_start;
    // 隊列實(shí)體的構(gòu)造函數(shù)，初始化list和p_start
    public MyQueue() {
        data = new ArrayList<Integer>();
        p_start = 0;
    }
    /** Insert an element into the queue. Return true if the operation is successful. */
    // 類中方法，添加一個元素。添加方法:data.add()，list的add方法向數(shù)組后面添加一個元素
    public boolean enQueue(int x) {
        data.add(x);
        return true;
    };
    /** Delete an element from the queue. Return true if the operation is successful. */
    // 移除一個元素
    // 首先通過isEmpty()方法，如果首元素大于等于list長度，判斷隊列為空
    // 對于隊列，p_start指向隊尾元素時=length-1，當(dāng)最后一個元素出列，p_start=length。>=為一種保險的寫法，我并未想出>的情景
    // 如果隊列非空，p_start自加。
    // 這里有個問題，list并未移除任何元素。以p_start元素判斷隊列是否清空。
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        // 是否可以在這里加入list的移除
        // list.remove(p_start);
        p_start++;
        return true;
    }
    /** Get the front item from the queue. */
    // 獲取隊列的首元素
    public int Front() {
        return data.get(p_start);
    }
    /** Checks whether the queue is empty or not. */
    // 判斷隊列是否為空
    public boolean isEmpty() {
        return p_start >= data.size();
    }     
};

public class Main {
    public static void main(String[] args) {
        // 初始化隊列
        MyQueue q = new MyQueue();
        q.enQueue(5);
        q.enQueue(3);
        // 隊列不為空，輸出首元素,這里應(yīng)該輸出5
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        // 移除5
        q.deQueue();
        // 輸出3
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        // 移除3
        q.deQueue();
        // if(false)
        // p_start = 2
        // data => [5,3]
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
    }
}

由此引出一個更高效的算法——循環(huán)隊列。

// 循環(huán)隊列——使用固定大小的數(shù)組和兩個指針來指示起始位置和結(jié)束位置。目的是重用我們之前提到的被浪費(fèi)的存儲。
// 思路：首先關(guān)鍵點(diǎn)有：
// 1、front和rear指針移動
// 問題：對于指定長度的數(shù)組，當(dāng)我們的下標(biāo)移動的時候必然會遇到下標(biāo)越界，此時理論上講超過數(shù)組范圍的下標(biāo)應(yīng)該移動到0號索引處
// 解決方法：進(jìn)行移動的時候,（front + 1） % queue.length就可獲得正確的下標(biāo)，rear同理
// 2、隊空與隊滿的判斷（思路是使用一個實(shí)際存儲長度標(biāo)識 size來參考判斷）
// 因?yàn)槲覀冇胹ize做判斷符號且數(shù)組長度加一以防止下標(biāo)指向空指針
// 所以判空 size == 0；判滿 size == length - 1。
// 3、入隊和出隊操作
// 入隊操作
// 入隊-》判斷隊滿-》入?yún)①x值-》rear后移-》size++
// 出隊操作
// 出隊-》判斷隊空-》front后移-》size--
// 4、返回隊首和隊尾索引
// 隊首很簡單：queue[front] 也可以 front == rear
// 隊尾很奇怪： queue[rear]會在某些情況下失效，舉個栗子：[1,2,3,null],length = 4,front = 0,rear = 3,size = 3,此時的rear-1;[1,2,3,4],length = 3,front = 1,rear = 0,size = 3,此時的rear - 1 = -1,顯然是不行的，此時隊尾應(yīng)該是4，所以使用（rear-1 + length） % length;

class MyCircularQueue {

    private int [] queue;
    private int front;
    private int rear;
    // 記錄實(shí)際隊列長度的數(shù)值
    private int size;
    
    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        queue = new int [k + 1];
        front = 0;
        rear = 0;
        size = 0;
    }
    
    /** Insert an element into the cir3W2WXcular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        // 尾元素進(jìn)1，如果超出數(shù)組長度，取mod（求余）
        queue[rear] = value;
        rear = (rear + 1) % queue.length;
        size++;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        // front移動，可不變更
        front = (front + 1) % queue.length;
        size--;
        return true;
    }
    
    /** Get the front item from the queue. */
    public int Front() {
        if (isEmpty()) return -1;
        return queue[front];
    }
    
    /** Get the last item from the queue. */
    public int Rear() {
        if (isEmpty()) return -1;
        return queue[(rear - 1 + queue.length) % queue.length];
    }
    
    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return size == queue.length - 1;
    }
}

應(yīng)用：

題目（數(shù)據(jù)流中的移動平均值）：
給定一個整數(shù)數(shù)據(jù)流和一個窗口大小，根據(jù)該滑動窗口的大小，計算其所有整數(shù)的移動平均值。

測試用例：
MovingAverage m = new MovingAverage(3); // size = 3
m.next(1) // 1  [1] average = 1/1
m.next(10) // (1 + 10) / 2 [1,10] average = (1+10)/2
m.next(3) // (1 + 10 + 3) / 3 [1,10,3] average = (1+10+3)/2
m.next(5) // (10 + 3 + 5) / 3 [10,3,5] average = (10+3+5)/2

若依次得到測定值(X1,X2,X3,...,Xn)時，按順序取一定個數(shù)所做的全部算術(shù)平均值。 例如(X1+X2+X3)/3,(X2+X3+X4)/3,(X3+X4+X5)/3,(X4+X5+X6)/3...等是移動平均值。

// 剛開始看這道題的時候，我去，我題目都沒看懂。。。
// 后來百度了下移動平均數(shù),然后又找了個題解看了下實(shí)現(xiàn)過程
class MovingAverage {
    // 這是初始化的窗口大小
    int size = 0;
    // 申明一個隊列，使用LinkedList初始化，這是collection中的隊列
    Queue<Integer> queue;
    // 使用sum提前記錄總數(shù)，方便取平均數(shù)
    // 注意這里最好定義為double類型，如果是整數(shù)不注意就會精度丟失
    double sum = 0;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        this.size = size;
        // 初始化隊列
        queue = new LinkedList<>();
    }
    
    public double next(int val) {
        // 入隊
        queue.offer(val);
        // 求和
        sum += val;
        // 如果超出屏幕
        if (queue.size() > size) {
            Integer head = queue.poll();
            sum -= head;
        }
        // 如果queue小于size ，取queue的長度
        return sum / queue.size();
    }
}

面對過現(xiàn)實(shí)才知道自己多渺小
我畢業(yè)也半年了，一個專升本文憑又因?yàn)樽约旱哪懬印㈦S遇而安的性格錯過了校招，進(jìn)了學(xué)長的一個公司。忙忙碌碌、松松垮垮，經(jīng)歷了一個多月的高強(qiáng)度加班，也經(jīng)歷了松懈的下班玩游戲、看小說、上班劃水。慢慢的自己也感覺到著急，回顧了自己的所學(xué)：android半吊子（垃圾碼農(nóng)水準(zhǔn)）、java半吊子（碼農(nóng)水準(zhǔn)）、vue半吊子（垃圾碼農(nóng)水準(zhǔn)）、flutter初學(xué)者（碼農(nóng)都算不上）。畢業(yè)一個月的時候，隔三差五的突然想學(xué)些什么，學(xué)了個把天又置之腦后。我的自制力本來垃圾，又沒一個目標(biāo)，渾渾噩噩下來一事無成。我不想這樣直到我失去沖勁、失去追求前進(jìn)的力氣。我現(xiàn)在在這定個目標(biāo)：以java工程師的身份進(jìn)到阿里，或許這是個永遠(yuǎn)吃不到的蘿卜，至少我有了明確的前進(jìn)目標(biāo)?！?020-3-12（感覺我心理這個日期已經(jīng)出問題了。。。）

后面如果有實(shí)際使用隊列的情景就加載下方——2020-3-12

我突然發(fā)現(xiàn)我之前的內(nèi)心好像出問題了，我完全不用這么糾結(jié)，以進(jìn)某廠為目標(biāo)有什么意思？在寫CRUD的路上，我覺得最求技術(shù)就行，了解感興趣的技術(shù)，了解想知道的知識，追求完成作品的樂趣，他不香么？結(jié)果不是必然，探索永無止境?！?020-3-31