Java 棧和隊(duì)列的交互實(shí)現(xiàn)
隊(duì)列和棧的區(qū)別
棧和隊(duì)列都是常用的數(shù)據(jù)結(jié)構(gòu),它們的主要區(qū)別在于數(shù)據(jù)的插入和刪除順序。
棧 (Stack) 是一種后進(jìn)先出 (Last-In-First-Out, LIFO) 的數(shù)據(jù)結(jié)構(gòu),只允許在一端進(jìn)行插入和刪除操作,這一端稱為棧頂。新元素插入后成為新的棧頂,而刪除時(shí)也只能刪除棧頂元素。
隊(duì)列 (Queue) 是一種先進(jìn)先出 (First-In-First-Out, FIFO) 的數(shù)據(jù)結(jié)構(gòu),允許在兩端進(jìn)行插入和刪除操作,插入在隊(duì)尾,刪除在隊(duì)頭。新元素插入時(shí)成為新的隊(duì)尾,而刪除時(shí)也只能刪除隊(duì)頭元素。
一.用隊(duì)列模擬實(shí)現(xiàn)棧
1.void push(int x) 將元素 x 壓入棧頂。
2.int pop() 移除并返回棧頂元素。
3.int top() 返回棧頂元素。
4.boolean empty() 如果棧是空的,返回 true ;否則,返回 false 。
如上便是需要用隊(duì)列來實(shí)現(xiàn)棧的四個(gè)基本操作。
我們試想,實(shí)現(xiàn)這些棧的操作,一個(gè)隊(duì)列可以完成嗎?
顯然不可以,我們使用兩個(gè)隊(duì)列來實(shí)現(xiàn)棧的模擬
大體流程
1.入棧時(shí):
如果兩個(gè)都為空,那么想
1.1入棧
當(dāng)我們要放入18 25 35 48 這一串?dāng)?shù)字入棧時(shí),先放入18 25 35(放入時(shí)選擇的隊(duì)列是不為空的隊(duì)列),模擬入隊(duì)以及入棧時(shí)的狀況,如下圖
public void push(int x) { if(empty()){ queue1.offer(x); return; } if(!queue1.isEmpty()){ queue1.offer(x); }else { queue2.offer(x); } }
1.2出棧
此時(shí)如果我們要將35出棧時(shí),又該如何操作呢?此時(shí)我們就需要用到第二個(gè)隊(duì)列,將隊(duì)列一的前size-1個(gè)元素(也就是18 25)從隊(duì)列一中出隊(duì),放入隊(duì)列二中。此時(shí)隊(duì)列一中的元素為35,隊(duì)列二的元素為18 25 如下圖。
當(dāng)初棧完成時(shí),我們此時(shí)要將48入棧時(shí),又該放入哪個(gè)棧中呢?我們考慮棧的特點(diǎn)(先入后出),我們將再入棧的元素放到不為空的隊(duì)列中。
public int pop() { if(empty()){ return -1; } if(!queue1.isEmpty()){ int size = queue1.size(); for (int i = 0; i < size-1; i++) { queue2.offer(queue1.poll()); } return queue1.poll(); }else { int size = queue2.size(); for (int i = 0; i < size-1; i++) { queue1.offer(queue2.poll()); } return queue2.poll(); } }
1.3返回棧頂元素
在實(shí)現(xiàn)pop的基礎(chǔ)上,我們將聲明一個(gè)變量temp來儲(chǔ)存每次要移除的元素。
public int top() { if(empty()){ return -1; } if (!queue1.isEmpty()){ int temp = -1; int size = queue1.size(); for (int i = 0; i < size; i++) { temp = queue1.poll(); queue2.offer(temp); } return temp; }else { int size = queue2.size(); int temp = -1; for (int i = 0; i < size; i++) { temp = queue2.poll(); queue1.offer(temp); } return temp; } }
1.4判斷棧是否為空
當(dāng)隊(duì)列一和隊(duì)列二都為空時(shí),此時(shí)棧就為空。
public boolean empty() { return queue1.isEmpty()&&queue2.isEmpty(); }
二.用棧模擬實(shí)現(xiàn)隊(duì)列
我們也是用兩個(gè)棧來模擬實(shí)現(xiàn)隊(duì)列
2.1 入隊(duì)
我們將所有入隊(duì)的元素都放入棧一中,如下圖
public void push(int x) { stack1.push(x); }
2.2出隊(duì)
要出棧時(shí),如果棧二不為空,就出棧二中的元素,如果棧二為空,將棧一中的所有元素一次性的全部push到棧二中,此時(shí)就將入棧的元素全部倒轉(zhuǎn)過來了,(例如入棧時(shí)在棧中的入棧順序依次排序?yàn)?8 25 35,棧二中此時(shí)的元素入棧順序是35 25 18,出棧時(shí)就先出18,就完成了轉(zhuǎn)換)如下圖
public int pop() { if(empty()){ return -1; } if (stack2.isEmpty()){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.pop(); }
2.3peek
peek只是將出隊(duì)時(shí)的pop換成peek,就可以完成要求。
public int peek() { if(empty()){ return -1; } if (stack2.isEmpty()){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.peek(); }
2.4判斷隊(duì)列是否為空
如果棧一和棧二都為空時(shí),那么隊(duì)列就為空。
public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); }
三.完整代碼
3.1 隊(duì)列模擬實(shí)現(xiàn)棧
class MyStack { Queue<Integer> queue1 ; Queue<Integer> queue2 ; public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } public void push(int x) { if(empty()){ queue1.offer(x); return; } if(!queue1.isEmpty()){ queue1.offer(x); }else { queue2.offer(x); } } public int pop() { if(empty()){ return -1; } if(!queue1.isEmpty()){ int size = queue1.size(); for (int i = 0; i < size-1; i++) { queue2.offer(queue1.poll()); } return queue1.poll(); }else { int size = queue2.size(); for (int i = 0; i < size-1; i++) { queue1.offer(queue2.poll()); } return queue2.poll(); } } public int top() { if(empty()){ return -1; } if (!queue1.isEmpty()){ int temp = -1; int size = queue1.size(); for (int i = 0; i < size; i++) { temp = queue1.poll(); queue2.offer(temp); } return temp; }else { int size = queue2.size(); int temp = -1; for (int i = 0; i < size; i++) { temp = queue2.poll(); queue1.offer(temp); } return temp; } } public boolean empty() { return queue1.isEmpty()&&queue2.isEmpty(); } }
3.2棧模擬實(shí)現(xiàn)隊(duì)列
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.isEmpty()){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } public int peek() { if(empty()){ return -1; } if (stack2.isEmpty()){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.peek(); } public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } }
到此這篇關(guān)于Java 棧和隊(duì)列的交互實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java 棧和隊(duì)列交互內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- java 數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列
- java 數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的實(shí)例詳解
- Java深入了解數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列的詳解
- Java 棧和隊(duì)列的相互轉(zhuǎn)換詳解
- Java棧和基礎(chǔ)隊(duì)列的實(shí)現(xiàn)詳解
- 一起來學(xué)習(xí)Java的棧和隊(duì)列
- Java?棧與隊(duì)列實(shí)戰(zhàn)真題訓(xùn)練
- Java 棧與隊(duì)列超詳細(xì)分析講解
- Java使用跳轉(zhuǎn)結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列和棧流程詳解
- Java線性結(jié)構(gòu)中棧、隊(duì)列和串的基本概念和特點(diǎn)詳解
- Java常見的數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列詳解
相關(guān)文章
Eclipse/MyEclipse轉(zhuǎn)IntelliJ IDEA完全攻略(圖文)
這篇文章主要介紹了Eclipse/MyEclipse轉(zhuǎn)IntelliJ IDEA完全攻略(圖文),小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-01-01mybatis-generator自動(dòng)生成dao、mapping、bean配置操作
這篇文章主要介紹了mybatis-generator自動(dòng)生成dao、mapping、bean配置操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-08-08Java基于余弦方法實(shí)現(xiàn)的計(jì)算相似度算法示例
這篇文章主要介紹了Java基于余弦方法實(shí)現(xiàn)的計(jì)算相似度算法,簡單說明了余弦相似性的概念、原理并結(jié)合實(shí)例形式分析了java實(shí)現(xiàn)余弦相似性算法的相關(guān)操作技巧,需要的朋友可以參考下2017-08-08Java源碼解析阻塞隊(duì)列ArrayBlockingQueue介紹
今天小編就為大家分享一篇關(guān)于Java源碼解析阻塞隊(duì)列ArrayBlockingQueue介紹,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧2019-01-01java如何實(shí)現(xiàn)獲取客戶端ip地址的示例代碼
本文主要介紹了java如何實(shí)現(xiàn)獲取客戶端ip地址,主要包括java獲取客戶端ip地址工具類使用實(shí)例、應(yīng)用技巧,文中通過示例代碼介紹的非常詳細(xì),感興趣的小伙伴們可以參考一下2022-04-04