Java數(shù)據(jù)結(jié)構(gòu)之隊列與OJ題
什么是隊列？
隊列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進(jìn)先出FIFO(First In First Out)
入隊列：進(jìn)行插入操作的一端稱為隊尾！
出隊列：進(jìn)行刪除操作的一 端稱為隊頭！
隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)， 出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低。
初識Queue
認(rèn)識一下Queue
如圖可見，Queue本質(zhì)上是一個接口，被Deque(雙端隊列)繼承，被LinkedList實現(xiàn)，所以Queue底層是通過鏈表來實現(xiàn)的，而Queue是不能實例化對象的， 所以我們想使用隊列，則需要new一個LinkedeList對象，實現(xiàn)向上轉(zhuǎn)型，這樣就可以使用Queue中的方法了：
add 和 offer 都是入隊列，這兩個區(qū)別是當(dāng)使用add時，一些隊列有大小限制，如果想在一個滿的隊列中加入新的元素時，調(diào)用 add() 方法就會拋出一個 unchecked 異常，而調(diào)用 offer() 方法會返回 false。因此就可以在程序中進(jìn)行有效的判斷！
簡單使用下Queue
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek()); //獲取對頭元素 -> 1
System.out.println(queue.poll()); //出隊頭元素 -> 1
System.out.println(queue.peek()); //獲取對頭元素 -> 2
System.out.println(queue.isEmpty()); //判斷隊列是否為null -> false
queue.clear(); //清空隊列
System.out.println(queue.isEmpty()); //判斷隊列是否為null -> true
}
模擬實現(xiàn)Queue
構(gòu)造方法和成員屬性
public class MyQueue {
private class Node {
private int val; //數(shù)據(jù)域
private Node next; //指針域名
private Node(int val) {
this.val = val;
}
}
//隊頭入，隊尾出
private Node head; //隊頭引用
private Node last; //隊尾引用
private int size; //隊列有效數(shù)據(jù)個數(shù)
}offer 方法
// 隊尾入隊列
public boolean offer(int val) {
Node newNode = new Node(val);
// 如果是第一次入隊列
if (this.head == null) {
this.head = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = this.last.next;
}
this.size++;
return true;
}poll 方法
// 隊頭出隊列
public int poll() {
Node node = this.head;
// 如果隊列為null
if (this.head == null) {
throw new MyQueueIsEmptyException("隊列為空！");
} else {
this.head = this.head.next;
}
this.size--;
return node.val;
}peek 方法
// 取隊頭元素
public int peek() {
// 如果隊列為null
if (this.head == null) {
throw new MyQueueIsEmptyException("隊列為空！");
}
else {
return this.head.val;
}
}至于size和empty方法，就交給各位小伙伴實現(xiàn)了，由于有了前面鏈表的基礎(chǔ)，隊列實現(xiàn)起來是比較簡單的，所以更多希望閱讀文章的初學(xué)者能下來多自己手寫以下，畫畫圖。
隊列相關(guān)的OJ題
設(shè)計循環(huán)隊列 (來源:LeetCode 難度:中等)
題目：設(shè)計你的循環(huán)隊列實現(xiàn)。 循環(huán)隊列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。它也被稱為“環(huán)形緩沖器”。
循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環(huán)隊列，我們能使用這些空間去存儲新的值。
你的實現(xiàn)應(yīng)該支持如下操作：
MyCircularQueue(k): 構(gòu)造器，設(shè)置隊列長度為 k 。
Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。
enQueue(value): 向循環(huán)隊列插入一個元素。如果成功插入則返回真。
deQueue(): 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
isEmpty(): 檢查循環(huán)隊列是否為空。
isFull(): 檢查循環(huán)隊列是否已滿。
解題思路：對于這道題來說，我們有很多種解題思路，但我們要注意一點(diǎn)，如何區(qū)分隊列為空和隊列滿的情況？這里可以添加size屬性記錄，也可使用標(biāo)記，也可也空一個位置出來區(qū)分，那么今天我們就空一個位置，那么如何區(qū)分隊列空和隊列滿呢？見下圖：
對于循環(huán)隊列的實現(xiàn)我們采用的時數(shù)組方案，有front和rear分別存儲隊頭下標(biāo)和隊尾元素的后一個下標(biāo)。至于更多需要注意細(xì)節(jié)的地方，比如修正front和rear的位置時，在代碼中有對應(yīng)的注釋，查看即可：
public class MyCircularQueue {
private int array[]; //存放數(shù)據(jù)的數(shù)組
private int front; // 隊頭下標(biāo)
private int rear; // 隊尾下標(biāo)
public MyCircularQueue(int k) {
this.array = new int[k + 1]; //因為我們要浪費(fèi)一個空間，所以需要多開辟一個空間
}
// 入隊列
public boolean enQueue(int value) {
// 如果隊列滿的情況
if (isFull()) {
return false;
}
// 沒有滿就往隊尾入元素
this.array[this.rear] = value;
// rear往前走一步，需要空出一個位置，所以當(dāng)rear走到length-1時，需要修正下rear
this.rear = (this.rear + 1) % this.array.length;
return true;
}
// 出隊列
public boolean deQueue() {
// 如果隊列為null的情況
if (isEmpty()) {
return false;
}
// 從隊頭出隊列，需要修正隊頭的位置
this.front = (this.front + 1) % this.array.length;
return true;
}
// 取隊頭元素
public int Front() {
// 如果隊列為null的情況
if (isEmpty()) {
return -1;
}
return this.array[this.front]; //返回隊頭元素
}
// 取隊尾元素
public int Rear() {
// 如果隊列為null的情況
if (isEmpty()) {
return -1;
}
// 如果rear為0的情況，我們需要特殊處理
int index = this.rear == 0 ? this.array.length - 1 : this.rear - 1;
return this.array[index]; //返回隊尾元素
}
// 判斷隊列是否為空
public boolean isEmpty() {
// 當(dāng)front和rear相遇了，則表示隊列中沒有元素
return this.front == this.rear;
}
// 判斷隊列是否滿了
public boolean isFull() {
// 因為我們會浪費(fèi)一個空間，所以rear+1等于front就滿了
// 但是我們要rear防止越界，所以要進(jìn)行修正：(this.rear + 1) % this.array.length
return (this.rear + 1) % this.array.length == this.front;
}
}
用隊列實現(xiàn)棧 (來源:LeetCode 難度:簡單)
題目：請你僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
實現(xiàn) MyStack 類：
void push(int x) 將元素 x 壓入棧頂。
int pop() 移除并返回棧頂元素。
int top() 返回棧頂元素。
boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。
解題思路：這道題的解題思路并不難，我們只需要定義兩個隊列，入棧的時候往不為null的隊列入，出棧的時候先將不為空的隊列的size()-1個元素全部放到為空的隊列中，剩余最后一個元素直接出棧即可，由于取棧頂元素不用刪除元素，所以剩余的最后一個元素還要放入另一個隊列中，至于更詳細(xì)的內(nèi)容可以配合下面代碼和注釋閱讀：
class MyStack {
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack() {
this.qu1 = new LinkedList<>();
this.qu2 = new LinkedList<>();
}
public void push(int x) {
// 兩個隊列都為null的情況
if (this.qu1.isEmpty() && this.qu2.isEmpty()) {
this.qu1.offer(x);
return;
}
// 哪個隊列不為null往哪個隊列中入元素
if (!this.qu1.isEmpty()) {
this.qu1.offer(x);
} else {
this.qu2.offer(x);
}
}
public int pop() {
// 如果兩個隊列都為空的情況下，就不能出隊操作
if (empty()) {
return -1;
}
// 先將不為空的隊列的size-1個元素全部放到為空的隊列中
if (!this.qu1.isEmpty()) {
while (qu1.size() - 1 != 0) {
qu2.offer(qu1.poll());
}
return qu1.poll(); //返回最后一個元素
} else {
while (qu2.size() - 1 != 0) {
qu1.offer(qu2.poll());
}
return qu2.poll(); //返回最后一個元素
}
}
public int top() {
// 如果隊列為null
if (empty()) {
return -1;
}
int ret = 0; //保留剩余最后一個棧頂元素的變量
// 先將不為空的隊列的size-1個元素全部放到為空的隊列中
if (!this.qu1.isEmpty()) {
while (qu1.size() - 1 != 0) {
qu2.offer(qu1.poll());
}
ret = qu1.peek();
qu2.offer(qu1.poll());
} else {
while (qu2.size() - 1 != 0) {
qu1.offer(qu2.poll());
}
ret = qu2.peek();
qu1.offer(qu2.poll()); //取棧頂元素不能刪除掉，還得入另一個隊列中去
}
return ret;
}
public boolean empty() {
return this.qu1.isEmpty() && this.qu2.isEmpty(); //兩個隊列都為空，棧才為空
}
}
用棧實現(xiàn)隊列 (來源:LeetCode 難度:簡單)
題目：請你僅使用兩個棧實現(xiàn)先入先出隊列。隊列應(yīng)當(dāng)支持一般隊列支持的所有操作（push、pop、peek、empty）。
實現(xiàn) MyQueue 類：
void push(int x) 將元素 x 推到隊列的末尾
int pop() 從隊列的開頭移除并返回元素
int peek() 返回隊列開頭的元素
boolean empty() 如果隊列為空，返回 true ；否則，返回 false
解題思路：這道題我們可以這樣做，定義兩個棧，分別是pushStack和popStack，入隊統(tǒng)一都入到pushStack棧中，出隊頭元素都從popStack中出，如果popStack是空的情況，就先將pushStack棧中所有的元素放入popStack中，再出棧頂元素。 至于判斷隊列是否為空，需要滿足 pushStack和popStack都為空，隊列才為空！
class MyQueue {
private Stack<Integer> pushStack;
private Stack<Integer> popStack;
public MyQueue() {
this.pushStack = new Stack<>();
this.popStack = new Stack<>();
}
public void push(int x) {
// 入隊列都在pushStack中
this.pushStack.push(x);
}
public int pop() {
// 出隊列都從popStack出
if (popStack.empty()) {
// 把pushStack棧中的元素都放到popStack棧中
while (!pushStack.empty()) {
popStack.push(pushStack.pop());
}
}
if (!popStack.empty()) {
return popStack.pop();
} else {
return -1;
}
}
public int peek() {
// 取隊頭元素都從popStack中取
if (popStack.empty()) {
// 把pushStack棧中的元素都放到popStack棧中
while (!pushStack.empty()) {
popStack.push(pushStack.pop());
}
}
if (!popStack.empty()) {
return popStack.peek();
} else {
return -1;
}
}
public boolean empty() {
return pushStack.empty() && popStack.empty();
}
}
最小棧 (來源:LeetCode 難度:中等)
題目：設(shè)計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。
實現(xiàn) MinStack 類:
MinStack() 初始化堆棧對象。
void push(int val) 將元素val推入堆棧。
void pop() 刪除堆棧頂部的元素。
int top() 獲取堆棧頂部的元素。
int getMin() 獲取堆棧中的最小元素。
解題思路：這道題一看就需要用到兩個棧，一個棧入數(shù)據(jù)，一個棧始終壓入最小值，如何操作呢？這里我們可以定義兩個棧，分別是stack和minStack，入棧的時候入stack這個棧，如果是第一次入棧，則當(dāng)前入棧元素為最小值，同時也需要入minStack棧中，如果后續(xù)入棧元素小于或等于minStack棧頂元素，則也需要入minStack棧，如果比minStack棧頂元素大，則不需要入minStack棧了，出棧的時候，判斷stack棧如果與minStack棧元素相等，則minStack也要出棧頂元素！
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
this.stack = new Stack<>();
this.minStack = new Stack<>();
}
public void push(int val) {
// 如果stack為null，表示第一次入棧，
// 此時入棧的元素也是此時棧中最小值，也要入minStack棧
if (this.stack.isEmpty()) {
this.stack.push(val);
this.minStack.push(val);
return;
}
this.stack.push(val);
// 如果stack棧頂元素小于等于minStack棧頂元素，則也需要入minStack棧中
if (this.stack.peek() <= this.minStack.peek()) {
this.minStack.push(val);
}
}
// 出棧
public void pop() {
if (this.stack.isEmpty()) {
return;
}
// 如果出棧元素與minStack元素相等，minStack也要出棧
if (this.stack.pop().equals(this.minStack.peek())) {
this.minStack.pop();
}
}
// 取棧頂元素
public int top() {
if (this.stack.isEmpty()) {
return -1;
} else {
return this.stack.peek();
}
}
// 取棧中最小元素
public int getMin() {
if (this.stack.isEmpty()) {
return -1;
} else {
return this.minStack.peek();
}
}
}
到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)之隊列與OJ題的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu) 隊列與OJ題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了JAVA設(shè)計模式之裝飾模式的的相關(guān)資料，文中示例代碼非常詳細(xì)，供大家參考和學(xué)習(xí)，感興趣的朋友可以了解下2021-11-11
這篇文章主要介紹了使用log4j MDC實現(xiàn)日志追蹤方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
詳解如何在低版本的Spring中快速實現(xiàn)類似自動配置的功能
這篇文章主要介紹了詳解如何在低版本的Spring中快速實現(xiàn)類似自動配置的功能，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-05-05
這篇文章主要介紹了基于jdk1.8的Java源碼詳解 Integer，Integer是int的Warpper類，是面向?qū)ο蟮募碠OP的對象類型，,需要的朋友可以參考下2019-06-06
數(shù)組是有序的元素序列，若將有限個類型相同的變量的集合命名，那么這個名稱為數(shù)組名。本文通過代碼示例詳細(xì)介紹了Java數(shù)組的定義和使用，對學(xué)習(xí)或工作有一定的幫助，需要的小伙伴歡迎閱讀2023-04-04
一個線程在未正常結(jié)束之前, 被強(qiáng)制終止是很危險的事情. 因為它可能帶來完全預(yù)料不到的嚴(yán)重后果比如會帶著自己所持有的鎖而永遠(yuǎn)的休眠，遲遲不歸還鎖等。 所以你看到Thread.suspend, Thread.stop等方法都被Deprecated了2023-02-02
亂碼問題是大家在日常開發(fā)過程中經(jīng)常會遇到的問題,由于各自環(huán)境的不同,解決起來也費(fèi)時費(fèi)力,本文主要介紹一般性亂碼問題的解決方法與步驟,開發(fā)工具采用Eclipse+Tomcat,統(tǒng)一設(shè)置項目編碼UTF-8為例,感興趣的朋友跟隨小編一起看看吧2023-08-08
這篇文章主要介紹了SpringBoot請求響應(yīng)的相關(guān)操作,本文通過示例代碼給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2024-06-06
logback的DuplicateMessageFilter日志過濾操作源碼解讀
這篇文章主要為大家介紹了logback的DuplicateMessageFilter日志過濾操作源碼解讀，有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-11-11
在本篇內(nèi)容里小編個總結(jié)了Java編程中的4種代碼塊相關(guān)的知識點(diǎn)，有興趣的朋友們可以學(xué)習(xí)下。2021-06-06