1、隊列
1.1 隊列的概念
隊列是一個特殊的線性表，只允許在一端（隊尾）進行插入數據操作，在另一端（對頭）進行刪除數據。隊列具有先進先出FIFO(First In First Out)的特性。
入隊：數據只能從隊尾進隊列? ? ? ?出隊：數據只能從對頭出隊列
即：隊尾進隊頭出
我們可以把隊列想象為一個排隊的隊伍，從隊尾開始排隊，排到了再從隊頭出隊：
1.2 隊列的設計
實現隊列，我們可以使用單鏈表、雙向鏈表、數組來實現。
- 單鏈表：我們可以使用last來作為標記尾結點的引用，入隊時采用尾插法，出隊時采用頭刪法，這樣出隊和入隊時的時間復雜度都可以達到O（1）。注意:入隊不可以采用頭插法，因為出隊時還需要找尾結點的前一個節點，時間復雜度必為O（n）。
- 雙向鏈表：因為具有next和prev域，頭插、尾插入隊都是可以的，都為O（1）。
- 數組：普通的數組實現隊列會產生很多空間的浪費，每當數據出隊時，front前面的空間就會被浪費掉。我們可以設計循環隊列來減少空間浪費。
接下來我們來聊一聊如何設計循環隊列。
?1.2.1 循環隊列
循環隊列又叫做環形隊列，通常是由數組實現的。
我們定義front和rear分別指向隊頭和隊尾，rear的位置就是入隊元素要插入的位置，起始時front和rear都在0下標處。
循環隊列就是將數組的兩端相連接，這樣即使有元素出隊，出隊元素的位置，rear指針也可以達到，能夠讓新元素入隊，減少空間的浪費。
當在rear為7下標時，進行入隊操作后（假設隊列不為滿），rear要來到0下標的位置，那么要進行的操作是：rear == （rear+1）% len
于是更新rear的操作為：rear == （rear+1）% len
如果基于以上的設計，那么循環隊列為空和隊列為滿時的條件均為：rear == front
那么對于循環隊列，該如何進行判空和判滿呢？我們給出改善設計：
判空：rear == front
判滿（三種方法）：
- 通過添加 size 屬性記錄（記錄元素個數，size == 數組長度時為滿）
- ?浪費一個位置，判斷rear的下一個是不是front。（front == （rear+1）% len時，說明隊列滿）
- ?使用標記（在有元素的地方定義boolean類型為true，沒有元素的地方定義為false，當front和rear相遇且boolean類型為true時，說明隊列滿）
1.2.2 實現循環隊列
我們通過一道OJ題來設計循環隊列。（使用浪費一個空間的方法來判滿）
. - 力扣（LeetCode）
?代碼：
class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {//題目要求我們k個位置均能存儲數據//因為我們使用浪費一個空間的方法來判滿，所以我們這里要開辟k+1個空間elem = new int[k + 1];}public boolean enQueue(int value) {if(isFull()) {//不滿時才能入隊return false;}//在rear位置插入數據，并更新rearelem[rear] = value;rear = (rear+1) % elem.length;return true;}public boolean deQueue() {if(isEmpty()) {//不空時才能出隊return false;}//直接更新front即可，新數據入隊會覆蓋front = (front+1) % elem.length;return true;}public int Front() {if(isEmpty()) {return -1;} //front指向的位置就是隊頭元素return elem[front];}public int Rear() {if(isEmpty()) {return -1;}//當rear == 0時，需要做特殊處理//其余rear-1下標就是隊尾元素的位置int index = rear == 0 ? elem.length - 1 : rear - 1;return elem[index];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear+1) % elem.length == front;}
}2、隊列Queue
在Java中，Queue是一個接口，底層是用鏈表來實現的：
注意：Queue是一個接口，在實例化時必須實例化實現Queue接口的類的對象。
2.1?Queue的方法
2.2、雙端隊列（Deque）
雙端隊列，元素可以在隊頭和隊尾任意插入和刪除元素，也就是說，元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。
Java給出的雙端隊列Deque也是一個接口（Queue的擴展接口），在實例化時必須實例化實現Deque接口的類的對象。
2.3 使用Queue和Deque
在Java中，有多個類實現了Queue和Deque，這里我們只談LinkedList和ArrayDeque。
我們可以使用LinkedList來實現隊列和雙端隊列，為鏈式實現，底層為鏈表。
也可以使用ArrayDeque來實現隊列和雙端隊列，為順序實現，底層為數組。
同時，LinkedList和ArrayDeque中也實現了集合類Stack中的方法（Deque接口中包含了Stack的方法，而LinkedList和ArrayDeque實現了Deque接口），所以我們也可以使用LinkedList和ArrayDeque來實現棧。
注意：只有Deque接口中包含了Stack的方法，Queue接口沒有包含。
也就是說，我們以后如果要構建棧、隊列、雙端隊列...都可以通過LinkedList和ArrayDeque來實現，其方法更加豐富。
3、面試OJ題
3.1 用隊列實現棧
. - 力扣（LeetCode）
3.1.1 思路分析
我們需要兩個隊列來模擬實現棧。
入棧：把數據放到不為空的隊列當中，如果兩個隊列都為空，則隨機放入即可。
出棧：兩個隊列必有一個為空，將不為空的隊列中的size-1個元素移到空隊列中，剩下的1個元素就是要模擬“出棧”的元素。
取棧頂元素：兩個隊列必有一個為空，將不為空的隊列中的全部元素移到空隊列中，并使用變量記錄每次進新隊列元素的數值，最后一次進隊的元素就是“棧頂”元素。
?3.1.2 代碼
class MyStack {Queue<Integer> qu1;Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}//模擬入棧：把元素放到不為空的隊列中public void push(int x) {if (empty()) {//兩個隊列都為空時 默認放到qu1中qu1.offer(x);} else if (qu1.isEmpty()) {qu2.offer(x);}else {qu1.offer(x);}}//將有元素的隊列中的size-1個元素導入進空隊列中//剩下的1個元素，就是要出棧的元素public int pop() {if (qu1.isEmpty()) {while (qu2.size() != 1) {int x = qu2.poll();qu1.offer(x);}return qu2.poll();}else {while (qu1.size() != 1) {int x = qu1.poll();qu2.offer(x);}return qu1.poll();}}//將有元素的隊列中的全部元素導入進空隊列中//并用變量記錄每一次導進的元素，最后一次導入的元素就是棧頂元素public int top() {int x = 0;if (qu1.isEmpty()) {while (!qu2.isEmpty()) {x = qu2.poll();qu1.offer(x);}return x;}else {while (!qu1.isEmpty()) {x = qu1.poll();qu2.offer(x);}return x;}}//當兩個隊列都為空時，說明棧為空public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}3.2 用棧實現隊列
. - 力扣（LeetCode）
3.2.1 思路分析
模擬入隊操作：“入隊”的元素全部放入第一個棧中
模擬出隊操作：
需要先判斷第2個棧為不為空，
1.如果未空，需要把第一個棧當中的所有元素都放到第二個棧中，彈出第二個棧當中的棧頂元素
2.如果不為空，直接彈出第二個棧當中的棧頂元素
也就是說第二個棧的棧頂元素，其實就是我們所模擬隊列的隊頭元素。
?3.2.2 代碼
class MyQueue {ArrayDeque<Integer> stack1;//"入隊"的元素統一放到stack1中ArrayDeque<Integer> stack2;//統一在stack2中出隊public MyQueue() {stack1 = new ArrayDeque<>();stack2 = new ArrayDeque<>();}public void push(int x) {stack1.push(x);//"入隊"的元素統一放到stack1中}public int pop() {if (stack2.isEmpty()) {//若stack2為空，則將stack1中的元素導入stack2中，// stack2的棧頂元素即為模擬出隊的“隊頭”元素while (!stack1.isEmpty()) {int x = stack1.pop();stack2.push(x);}return stack2.pop();}else {//若stack2不為空，其棧頂元素即為模擬出隊的“隊頭”元素return stack2.pop();}}public int peek() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {int x = stack1.pop();stack2.push(x);}return stack2.peek();}else {return stack2.peek();}}public boolean empty() {//當stack1和stack2均為空時，說明模擬的隊列為空return stack1.isEmpty() && stack2.isEmpty();}
}OK~本次博客到這里就結束了，
感謝大家的閱讀~歡迎大家在評論區交流問題~
如果博客出現錯誤可以提在評論區~
創作不易，請大家多多支持~
)
)
