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