Java成神之路：第三帖—-數據結構與演算法之隊列
數據結構與演算法–隊列
今天掉了兩根頭髮，摸掉的，記得 別亂摸，很珍貴的！！
什麼是隊列？
1）隊列是一個有序列表，可以用數組或是鏈表來實現
2）遵循 先入先出 的原則。即：先存入隊列的數據，要先取出。後存入的要後取出
3）示意圖：（使用數組模擬隊列示意圖）
rear表示的是隊列尾，front表示的是隊列首，front值等於-1，表示隊列數據首的前一位（用數組模擬隊列，數組的下標第一個為0，用-1表示數據首的前一位），rear的值為-1，在這裡我認為是為了和front保持一致，這樣rear == front，表示數組為空！
用數組模擬隊列的思路
隊列本身是有序列表，若使用數組的結構來存儲隊列的數據，則隊列數組的聲明如下圖，其中 max Size是該隊列的最大容量，因為隊列的輸出、輸入是分別從前後端來處理，因此需要兩個變數 front及rear分別記錄隊列前後端的下標，front會隨著數據輸出而改變，而rear則是隨著數據輸入而改變，還是這個圖嘻嘻~
** 當我們將數據存入隊列時稱為」addQueue」，addQueue的處理需要有兩個步驟：
- 將尾指針往後移：
rear+1，當front == rear隊列表示為空 （PS：數組頭和數組尾在一起，能不空嗎） - 若尾指針rear小於隊列的最大下標 maxSize-1，則將數據存入rear所指的數組元素中，否則無法存入數據
reaI == maxSize-1此時表示隊列滿 - 話不多說，上程式碼：**
package com.yishuai.queue;
public class ArrayQueueDemo {
public static void main(String[] args) {
//數據測試
ArrayQueue arrayQueue = new ArrayQueue(3);
}
}
class ArrayQueue {
private int maxSize;//最大容量
private int front;//隊列頭
private int rear;//隊列尾
private int[] arr;//存放數據的數組，模擬隊列
//隊列初始化
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
front = -1;//指向隊列的首部，分析出front指向隊列頭的前一個位置
rear = -1;//指向隊列的尾部，指向隊列尾部的最後一個數據
}
//判斷隊列是否滿
public boolean isFull() {
return rear == maxSize - 1;
}
//判斷隊列是否空
public boolean isEmpty() {
return rear == front;
}
//將數據添加到隊列
public void addQueue(int data) {
//如果隊列已經滿了，就不能再添加數據進入
if (isFull()) {
System.out.println("隊列已經滿了");
return;
}
rear++; //數據增加，隊列尾的下標增加，隊列頭不變
arr[rear] = data;
}
//將數據從隊列中取出
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("隊列為空，沒有數據可取");
}
front++;
return arr[front];
}
//展示出隊列中的所有數據
public void showQueue() {
if (isEmpty()) {
System.out.println("隊列為空，沒有數據哦~");
}
for (int data : arr) {
System.out.print(data + "\t");
}
}
}
新的問題
因為此時的隊列，採取的是一個鏈式的，也就意味著，當前面的數據被取出的時候，即使此時隊列已經不是滿的了，但是隊列尾還是和maxSize – 1一樣大，數據在插入的時候，仍然還是會顯示：隊列已經滿啦~，此時我們如果想要解決這個問題，我們要使用： 環形隊列
循環隊列
有兩種方法（坑了我幾個小時）：
第一種：
聲明：font為頭部第一個數據，rear為尾部最後一個數據的下一個位置
- 當
font == rear的時候，隊列為空（這個沒問題吧？） - 初始：
font == rear == 0,此時隊列為空，當數據進入的時候，rear開始往後走，也就是+1 - 假如
maxSize=5，放入四個數據，也就是rear往後走了四步之後，rear=4了，數組有五個位置，但是裡面只有四個數據，最後一個空的數據還沒有放入，此時，假如rear再往前走一步，rear=5，但是數組的下標是從0開始的，也就是說，（0,1,2,3,4）這裡就是五個單元格，到頂了 - 所以
rear到5的時候，只能往回走，也就是說，rear=4之後，不是rear=5，而是rear=0，此時font也等於0，font == rear了，刺激吧？ - 前面說
font == rear時，隊列為空，但是現在說font == rear時，隊列又是為滿的，哪裡出錯了嗎？大部分人是不是和我一樣的思想（也可能是我自戀），你沒錯，兩個都是對的，所以呢，單純的依靠font和rear已經不能滿足判斷的條件了，我的方法是再加入一個count計數，從0開始，加一個數據，count++，取一個數據，count--。count會在【0，5】之間變動，當font == rear且count=0時，隊列為空，當font == rear且count=5時，隊列為滿，至於有效數據的個數，直接看count的值即可，這是第一種方法（我感覺比第二種好）！！
第二種（我和室友討論了一個多小時，吐槽吐槽）
PS：重點來了！！！
這種方法有一個單元格是空的！！！假如最大空間為5，只能放入4個數據，還有一個空間，留著種水稻（粗口不斷！），竟然不把空間用完，這也太浪費了，我看了3遍，想著應該不會這麼傻吧，空間都不用完，家裡有礦啊，還以為是自己哪裡沒弄懂，搞了一遍又一遍，和室友討論了很久，也沒得出結論，最後翻書解決了（不賣書，別私聊找我問哈），重複一遍，有一個空間是空的！！一直都是！！
這種方法，意思是：
聲明：font為頭部第一個數據，rear為尾部最後一個數據的下一個位置
- 當
font == rear的時候，隊列為空（這個沒問題吧？沒問題吧？） - 假如
maxSize = 5，什麼時候滿了呢？當rear跑到4的時候就滿了，也就是rear == 4，裡面就四個數據，還有一個空間呢，重複：種水稻了（空的），所以（rear+1）% maxSize == font時，就滿了（%是取餘數，也叫取模，/是取商），rear+1什麼意思？補上種水稻的那個空，然後再對maxSize取模，為什麼取模？因為可能正好是和font同一圈，也有可能已經和font相差一圈了，所以要做取模操作。 - 那麼有多少有效數據呢？可以直接看隊列的長度，也就是 |rear-font|（取絕對值，問我為什麼的先去面壁，再評論我給你回復），所以就可以寫成這樣
(rear+maxSize-font)%maxSize,
更新結束了，我頭髮又掉了兩根，啊啊啊！！！
不點個贊再走，你對得起我頭髮嗎，對得起嗎？
