【Java數據結構】詳解Stack與Queue（三）

🔒文章目錄：

1.????前言~🥳🎉🎉🎉

2. 隊列（Queue）

2.1隊列的概念?

2.2隊列的方法?

2.3隊列的使用?

2.4循環隊列

循環隊列的介紹

循環隊列圖

如何區分循環隊列是滿還是空?

數組下標循環技巧?

模擬實現循環隊列

3.雙端隊列(Deque)?

4.總結

1.????前言~🥳🎉🎉🎉

Hello, Hello~ 親愛的朋友們👋👋，這里是E綿綿呀????。

如果你喜歡這篇文章，請別吝嗇你的點贊????和收藏📖📖。如果你對我的內容感興趣，記得關注我👀👀以便不錯過每一篇精彩。

當然，如果在閱讀中發現任何問題或疑問，我非常歡迎你在評論區留言指正🗨?🗨?。讓我們共同努力，一起進步！

加油，一起CHIN UP！💪💪

🔗個人主頁：E綿綿的博客
📚所屬專欄：

1.?JAVA知識點專欄

? ? ?? ?深入探索JAVA的核心概念與技術細節

2.JAVA題目練習

? ? ? ??實戰演練，鞏固JAVA編程技能

3.c語言知識點專欄

? ? ? ? 揭示c語言的底層邏輯與高級特性

4.c語言題目練習

? ? ? ? 挑戰自我，提升c語言編程能力

📘 持續更新中，敬請期待????

借鑒文章：【Java---數據結構】隊列-CSDN博客?

2. 隊列（Queue）

2.1隊列的概念?

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

2.2隊列的方法?

常用的方法為以上三個方法，但總共有六個方法。

🍓入隊列：add()、offer()

相同：未超出容量，從隊尾壓入元素，返回壓入的那個元素。
區別：在超出容量時，add()方法會對拋出異常，offer()返回false
🍓出隊列：remove()、poll()

相同：容量大于0的時候，刪除并返回隊頭被刪除的那個元素。
區別：在容量為0的時候，remove()會拋出異常，poll()返回null
🍓獲取隊頭元素(不刪除)：element()、peek()

相同：容量大于0的時候，都返回隊頭元素。但是不刪除。
區別：容量為0的時候，element()會拋出異常，peek()返回null。

雖然有六個方法，但我們經常用的是 offer（），poll（），peek（）。知道這另外三個方法就行了

此外我們還需記住size（）和isEmpty（），這兩個方法之前就見過，想必不用多說了。

2.3隊列的使用?

由于隊列是接口，所以我們不能實例化Queue，要用Queue去接收實現了Queue接口的實例化對象。

隊列可以使用順序表或鏈表的結構來實現：

當用鏈表結構來實現時，我們用LinkedList去實例化對象，再用Queue去接收。（LinkedList實現了Queue接口，上圖有出現其關系）

當用順序表結構來實現時，我們用ArrayDeque去實例化對象，再用Queue去接收。

（ArrayDeque實現了Queue接口）

?當用鏈表結構實現隊列時，其使用代碼如下：

public class Test1 {public static void main(String[] args) {Queue<Integer> queue=new LinkedList<>();queue.offer(4);queue.offer(3);queue.offer(2);queue.offer(1);System.out.println(queue.peek());queue.poll();queue.poll();System.out.println(queue);}
}

當用順序表結構實現隊列時，其使用代碼如下：?

public class Test2 {public static void main(String[] args) {Queue<Integer> queue=new ArrayDeque<>();queue.offer(4);queue.offer(3);queue.offer(2);queue.offer(1);System.out.println(queue.peek());queue.poll();queue.poll();System.out.println(queue);}
}

注意：我們用println（）打印Queue對象時能以字符串的形式打印出其內部的所有成員值。

2.4循環隊列

循環隊列的介紹

當我們使用順序表實現隊列時，會存在一個問題：雖然順序表實現的隊列可以自動擴容，但其空間利用不充分：因為每次出隊都會浪費一個空間，為了解決這個問題，我們可以采用循環隊列。
循環隊列是一個特殊的隊列：其底層還是數組，但不能實現自動擴容。入隊時能夠重新從數組的尾部跳到數組頭部對已經出隊的空間重新利用，這樣就能夠保證數組的每一個空間都可以被利用。

?循環隊列圖

如果將隊列看做是一個循環，那么就可以看做是將數據存儲在一個圓環里。

那現在有一個問題，當隊列（數組）滿的時候，font = rear ，而空的時候也是font=rear。那該怎么判斷呢？

如何區分循環隊列是滿還是空?

1、定義一個變量size：記錄隊列元素個數。

每存放（入隊）一個元素size++，每刪除（出隊）一個元素size--。
當size的值與順序表的大小相等時，表示隊列已滿。
size值為0表示隊列為空。
2、使用一個boolean類型的成員變量flag進行標記，初始值為false。

每次入隊時將flag的值置為true，出隊將flag的值置為false，
當rear == front && flag == true表示隊列已滿。
當rear == front && flag == false表示隊列為空。
3、浪費一個空間。

每次存放元素之前都先檢查一下rear的下一個下標與 front 是否相等（也可以使用格式進行判斷：（rear+1）% array.length 是否與 front 相等）
如果rear的下一個下標與 front 相等則表示隊列已滿。
如果rear == front則表示隊列為空。

這樣就導致其中必有一個空間存放不了值，相當于浪費了一個空間去使隊列為空的標志和隊列已滿的標志有區別，從而使其能夠判斷出來。

數組下標循環技巧?

?同理在出隊時，front 也會出現這種情況，所以使用方式：front = (front+1)%elem.length;

?模擬實現循環隊列

📌題目描述：

設計你的循環隊列實現。 循環隊列是一種線性數據結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環。它也被稱為“環形緩沖器”。
循環隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環隊列，我們能使用這些空間去存儲新的值。

你的實現應該支持如下操作：

MyCircularQueue(k): 構造器，設置隊列長度為 k 。
Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。
enQueue(value): 向循環隊列插入一個元素。如果成功插入則返回真。
deQueue(): 從循環隊列中刪除一個元素。如果成功刪除則返回真。
isEmpty(): 檢查循環隊列是否為空。
isFull(): 檢查循環隊列是否已滿。

📋題目示例?：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 設置長度為 3
circularQueue.enQueue(1); ?// 返回 true
circularQueue.enQueue(2); ?// 返回 true
circularQueue.enQueue(3); ?// 返回 true
circularQueue.enQueue(4); ?// 返回 false，隊列已滿
circularQueue.Rear(); ?// 返回 3
circularQueue.isFull(); ?// 返回 true
circularQueue.deQueue(); ?// 返回 true
circularQueue.enQueue(4); ?// 返回 true
circularQueue.Rear(); ?// 返回 4

💥注意：

? 代碼示例：

class MyCircularQueue {Integer[] elements;int font;int rear;public MyCircularQueue(int k) {elements =new Integer[k+1];}public boolean enQueue(int value) {if(isFull())return false;else {elements[rear] = value;rear = (rear + 1) % elements.length;return true;}}public boolean deQueue() {if(isEmpty())return false;else{elements[font]=null;font=(font+1)%elements.length;return true;}}public int Front() {if (isEmpty())return -1;elsereturn elements[font];}public int Rear() {if(isEmpty())return -1;else{if(rear==0)return elements[elements.length-1];return elements[rear-1];}}public boolean isEmpty() {if(rear==font)return true;elsereturn false;}public boolean isFull() {if((rear+1)%elements.length==font)return true;elsereturn false;}
}

該題鏈接：循環隊列的模擬實現

3.雙端隊列(Deque)?

雙端隊列（deque）是指允許兩端都可以進行入隊和出隊操作的隊列，deque 是 “double ended queue” 的簡稱。

將隊列的兩端分別稱為前端和后端，兩端都可以入隊和出隊。所以雙端隊列既能夠當隊列使用，也能當棧使用。（重點這句話）

Java底層是使用LinkedList或ArrayDeque來實現雙端隊列(Deque)的，前面講過，隊列（Queue）也是使用LinkedList或ArrayDeque來實現的。（使用LinkedList是用鏈式結構去實現雙端隊列，使用ArrayDeque是用順序結構去實現雙端隊列）

對于Deque的方法，我們常見的依舊是offerFirst，offerLast，pollFirst，pollLast，peekFirst，peekLast。其他的六個方法知道就行。?

除此之外我們也還需記住size（）和isEmpty（）。

?當用鏈表結構實現雙端隊列時，其使用代碼如下：

public class Test3 {public static void main(String[] args) {Deque<Integer> deque= new  LinkedList<>();deque.offerLast(4);deque.offerFirst(3);deque.offerFirst(5);deque.offerLast(6);System.out.println(deque.peekLast());//6System.out.println(deque.peekFirst());//5deque.pollLast();deque.pollFirst();System.out.println(deque.peekLast());//4System.out.println(deque.peekFirst());//3}
}

?當用順序表結構實現雙端隊列時，其使用代碼如下：

public class Test4 {public static void main(String[] args) {Deque<Integer> deque= new ArrayDeque<>();deque.offerLast(4);deque.offerFirst(3);deque.offerFirst(5);deque.offerLast(6);System.out.println(deque.peekLast());//6System.out.println(deque.peekFirst());//5deque.pollLast();deque.pollFirst();System.out.println(deque.peekLast());//4System.out.println(deque.peekFirst());//3
}
}