大家好，我是曉星航。今天為大家?guī)淼氖?Java棧和隊(duì)列·下 的講解！😀

繼上一個(gè)講完的棧后，我們這次開始講解隊(duì)列！

2. 隊(duì)列(Queue)

2.1 概念

隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out) 入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾（Tail/Rear） 出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭（Head/Front）

在idea中看Queue(隊(duì)列的底層邏輯代碼)時(shí) 按下 alt + 7 可以查看它包含的所有方法：

2.2 實(shí)現(xiàn)

隊(duì)列也可以數(shù)組和鏈表的結(jié)構(gòu)實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率會(huì)比較低。

class Node {public int val;public Node next;public Node(int val) {this.val = val;}}
public class MyQueue {public Node head;public Node last;/*** 尾插法* @param val*/public void offer(int val) {Node node = new Node(val);if (head == null) {head = node;last = node;} else {last.next = node;last = last.next;}}public int poll() {if (isEmpty()) {throw new RuntimeException("隊(duì)列為空");}int oldVal = head.val;head = head.next;return oldVal;}public boolean isEmpty() {return this.head == null;}public int peek() {if (isEmpty()) {throw new RuntimeException("隊(duì)列為空");}return head.val;}}

下面為測試代碼：

public class TestDemo {public static void main(String[] args) {MyQueue queue = new MyQueue();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println(queue.peek());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());}

Queue中方法總結(jié)：
add 增加一個(gè)元索 如果隊(duì)列已滿，則拋出一個(gè)IIIegaISlabEepeplian異常
remove 移除并返回隊(duì)列頭部的元素 如果隊(duì)列為空，則拋出一個(gè)NoSuchElementException異常
element 返回隊(duì)列頭部的元素 如果隊(duì)列為空，則拋出一個(gè)NoSuchElementException異常
offer 添加一個(gè)元素并返回true 如果隊(duì)列已滿，則返回false
poll 移除并返問隊(duì)列頭部的元素 如果隊(duì)列為空，則返回null
peek 返回隊(duì)列頭部的元素 如果隊(duì)列為空，則返回null
put 添加一個(gè)元素 如果隊(duì)列滿，則阻塞
take 移除并返回隊(duì)列頭部的元素

2.3 相似方法的區(qū)別

1、add()和offer()區(qū)別:

add()和offer()都是向隊(duì)列中添加一個(gè)元素。一些隊(duì)列有大小限制，因此如果想在一個(gè)滿的隊(duì)列中加入一個(gè)新項(xiàng)，調(diào)用 add() 方法就會(huì)拋出一個(gè) unchecked 異常，而調(diào)用 offer() 方法會(huì)返回 false。因此就可以在程序中進(jìn)行有效的判斷！

2、poll()和remove()區(qū)別：

remove() 和 poll() 方法都是從隊(duì)列中刪除第一個(gè)元素。如果隊(duì)列元素為空，調(diào)用remove() 的行為與 Collection 接口的版本相似會(huì)拋出異常，但是新的 **poll() 方法在用空集合調(diào)用時(shí)只是返回 null。**因此新的方法更適合容易出現(xiàn)異常條件的情況。

3、element() 和 peek() 區(qū)別：

element() 和 peek() 用于在隊(duì)列的頭部查詢元素。與 remove() 方法類似，在隊(duì)列為空時(shí)， element() 拋出一個(gè)異常，而 peek() 返回 null。

2.4 循環(huán)隊(duì)列

實(shí)際中我們有時(shí)還會(huì)使用一種隊(duì)列叫循環(huán)隊(duì)列。如操作系統(tǒng)課程講解生產(chǎn)者消費(fèi)者模型時(shí)可以就會(huì)使用循環(huán)隊(duì)列。環(huán)形隊(duì)列通常使用數(shù)組實(shí)現(xiàn)。

數(shù)組下標(biāo)循環(huán)的小技巧

1. 1. 下標(biāo)最后再往后(offset 小于 array.length): index = (index + offset) % array.length

2. 下標(biāo)最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

如何區(qū)分空與滿

1. 通過添加 size 屬性記錄 使用size和數(shù)組長度比較，確定滿或者空

2. 使用標(biāo)志位flag，最開始falg = false，

   入隊(duì)列時(shí)，每放一個(gè)元素，falg就置為true

   出隊(duì)列時(shí)，每出一個(gè)元素，falg就置為false

   當(dāng)front和rear相遇時(shí)，falg為true則隊(duì)列為滿，falg為false則隊(duì)列為空。

3. 浪費(fèi)一個(gè)格子來區(qū)分空和滿，每次存放元素之前，都先檢查一下rear的下一個(gè)是不是front。如果是，那么就是滿的

空：frontNext == rear

滿：rearNext == front

3. 雙端隊(duì)列 (Deque)

3.1 概念

雙端隊(duì)列（deque）是指允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列，deque 是 “double ended queue” 的簡稱。那就說明元素可以從隊(duì)頭出隊(duì)和入隊(duì)，也可以從隊(duì)尾出隊(duì)和入隊(duì)。

雙端隊(duì)列的所有方法：

4.java中的棧和隊(duì)列

棧的方法：

普通隊(duì)列方法：

雙端隊(duì)列方法：

5. 棧和隊(duì)列面試題

1. 括號匹配問題。OJ鏈接

import java.util.Stack;
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if (ch == '(' || ch == '[' || ch == '{' ) {//如果是左括號直接入棧stack.push(ch);} else {//如果是右括號if (stack.empty()) {//右括號多System.out.println("右括號多！");return false;}char top = stack.peek();if (top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}') {//如果左括號和右括號匹配 則彈出這個(gè)左括號stack.pop();} else {//左右括號不匹配System.out.println("左右括號不匹配");return false;}}}if (!stack.empty()) {//左括號多System.out.println("左括號多！");return false;}return true;}
}

題目描述的很清楚，左右括號如果不匹配，無非是以下幾種情況：

1、左括號多余右括號

2、右括號多余左括號

3、左右括號順序不想匹配

在使用代碼將這幾種情況考慮完全后，便可輕易通過測試。

思路如下：

如果是左括號我們直接使其進(jìn)棧，如果是右括號我們先判斷右括號是否比左括號多，再看其是否相匹配，匹配則彈出相對應(yīng)的左括號繼續(xù)下一個(gè)括號的判斷，如果不匹配則返回不匹配錯(cuò)誤，在右括號全部判斷完畢后，我們判斷一下棧此時(shí)是否為空，如果為空則我們所有的括號都匹配成功即正確，如果不為空則是左括號比右括號要多，我們就返回false。

2. 用隊(duì)列實(shí)現(xiàn)棧。OJ鏈接

public class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()){qu2.offer(x);} else {qu1.offer(x);}}public int pop() {if (empty()) {return -1;}if (!qu1.isEmpty()) {int size = qu1.size();for (int i = 0; i < size - 1; i++) {int val = qu1.poll();qu2.offer(val);}return qu1.poll();}if (!qu2.isEmpty()) {int size = qu2.size();for (int i = 0; i < size - 1; i++) {int val = qu2.poll();qu1.offer(val);}return qu2.poll();}return -1;}public int top() {if (empty()) {return -1;}if (!qu1.isEmpty()) {int val = -1;int size = qu1.size();for (int i = 0; i < size; i++) {val = qu1.poll();qu2.offer(val);}return val;}if (!qu2.isEmpty()) {int val = -1;int size = qu2.size();for (int i = 0; i < size; i++) {val = qu2.poll();qu1.offer(val);}return val;}return -1;}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

1、入棧的時(shí)候，入到不為空的隊(duì)列，剛開始都為空指定入到一個(gè)隊(duì)列。

2、出棧的時(shí)候，找到不為空的隊(duì)列，出size-1個(gè)元素到另一個(gè)隊(duì)列，剩下這個(gè)元素就是出棧的元素。

注意：這里有一個(gè)小問題我們很容易疏忽，就是在使用top和pop方法進(jìn)行移動(dòng)時(shí)我們qu1和qu2中的元素個(gè)數(shù)時(shí)變化的，因此我們的qu1.size() qu2.size()也會(huì)跟著變化，為了避免這個(gè)情況，我們在for循環(huán)的外面自己定義一個(gè)Int size = qu1.size(); int size = qu2.size();在之后的for循環(huán)中我們只需要讓i小于size即可，此時(shí)的size就不是一個(gè)會(huì)變動(dòng)的值了。

3. 用棧實(shí)現(xiàn)隊(duì)列。OJ鏈接

class MyQueue {public Stack<Integer> stack1;public Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if (empty()) {return -1;}if (stack2.empty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if (empty()) {return -1;}if (stack2.empty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

思路：1、入隊(duì)的時(shí)候，統(tǒng)一入到第1個(gè)棧

2、出隊(duì)的時(shí)候，同一出第2個(gè)棧里面的元素，如果第2個(gè)為空，那么把第一個(gè)棧里面所有的元素，全部倒過來，然后再出棧頂?shù)脑亍?/p>

4. 實(shí)現(xiàn)一個(gè)最小棧。OJ鏈接

class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if (!minStack.empty()) {int top = minStack.peek();//比較 小于等于的話 也要放進(jìn)來if (val <= top) {minStack.push(val);}} else {minStack.push(val);}}public void pop() {int popVal = stack.pop();if (!minStack.empty()) {int top = minStack.peek();if (top == popVal) {minStack.pop();}}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

思路：這里我們采取了使用兩個(gè)棧(一個(gè)普通棧 一個(gè)最小棧)來比較的方法，例如我們在push元素時(shí)，普通棧我們是直接放進(jìn)去的，而最小棧我們則是通過比較，如果要放的元素比我們最小棧棧頂?shù)脑匦』虻扔谖覀儽阍谧钚Ｒ卜湃胍环荨?/p>

在pop彈出棧頂元素時(shí)我們同樣是直接彈出普通棧的棧頂元素，然后比較這個(gè)彈出的元素和最小棧棧頂元素的大小是否相等，如果相等我們則還需要再pop一次最小棧的棧頂元素。

top方法和我們stack棧中的peek方法一樣，我們直接返回stack的peek方法即可。

getMin方法是返回棧中最小元素，我們這里有兩個(gè)棧，而最小棧的原理就是將最小的元素通過壓棧(頭插)的方式進(jìn)入最小棧，因此我們最小棧的最小值永遠(yuǎn)是棧頂?shù)脑?#xff0c;我們直接返回最小棧的棧頂元素即可。

5. 設(shè)計(jì)循環(huán)隊(duì)列。OJ鏈接

class MyCircularQueue {public int[] elem;public int front;//隊(duì)頭下標(biāo)public int rear;//隊(duì)尾下標(biāo)public MyCircularQueue(int k) {this.elem = new int[k + 1];}/*** 入隊(duì)操作* @param value* @return*/public boolean enQueue(int value) {if (isFull()) {return false;}this.elem[rear] = value;//rear++;rear = (rear + 1) % elem.length;return true;}/*** 出隊(duì)操作* @return*/public boolean deQueue() {if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}/*** 得到隊(duì)頭元素* @return*/public int Front() {if (isEmpty()) {return -1;}return elem[front];}public int Rear() {if (isEmpty()) {return -1;}int index = -1;if (rear == 0) {index = elem.length - 1;} else {index = rear - 1;}return elem[index];}public boolean isEmpty() {return front == rear;}public boolean isFull() {//rear的下一個(gè)是frontif ((this.rear + 1) % elem.length == front) {return true;}return false;}
}

解答思路：我們這里的數(shù)組元素為k個(gè)，但是所能用的位置只有k-1個(gè)，為了滿足題目要求我們將數(shù)組大小改為了k+1，故我們所能用的元素變?yōu)榱薻個(gè)。這里因?yàn)槲覀兪茄h(huán)隊(duì)列，因此當(dāng)數(shù)組為空時(shí)，或者數(shù)組占滿時(shí)我們的front和rear是相等的，為了避免數(shù)組占滿，而要計(jì)算rear要循環(huán)回我們的首元素地址0時(shí)，我們采取了rear = (rear + 1) % elem.length的操作，如果rear的下標(biāo)已經(jīng)時(shí)數(shù)組下標(biāo)的最大值，再加1就會(huì)自動(dòng)歸為首元素的下標(biāo)0。

感謝各位讀者的閱讀，本文章有任何錯(cuò)誤都可以在評論區(qū)發(fā)表你們的意見，我會(huì)對文章進(jìn)行改正的。如果本文章對你有幫助請動(dòng)一動(dòng)你們敏捷的小手點(diǎn)一點(diǎn)贊，你的每一次鼓勵(lì)都是作者創(chuàng)作的動(dòng)力哦！😘