資訊專欄INFORMATION COLUMN
摘要：解決方案二入隊都在中進行，用于隊列，同時保證所有元素都在一個棧里，且遵循以下約束入隊不管空與否，都將中的所有元素壓入中出隊若中不為空，則直接從中彈出元素若為空，則說明隊列為空，不能出隊。
聲明：碼字不易，轉(zhuǎn)載請注明出處，歡迎文章下方討論交流。
前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本篇文章介紹一個有趣的問題：用兩個棧實現(xiàn)一個隊列。這道題來自互聯(lián)網(wǎng)公司的算法面試，作為一道經(jīng)典的算法面試題，本文給出問題的解決思路和Java實現(xiàn)代碼。
前兩篇文章介紹了棧(stack)和隊列（queue）兩種特殊的數(shù)據(jù)結(jié)構(gòu)和他們特點，棧和隊列雖然是特點針鋒相對的，但有意思的是他們卻彼此相互聯(lián)系。
后進先出的棧如何才能實現(xiàn)先進先出的隊列呢？一般會用兩個棧來實現(xiàn)。首先定義兩個棧分別為stack1和stack2.
1.解決方案一：我們讓入隊的操作在stack1中完成，出隊的操作在stack2中完成，具體分析過程如下：
入隊： ①將所有元素直接向stack1中壓棧
出隊： ②將stack1中的所有元素依次出棧，③緊接著入棧到stack2中，④然后彈出stack2中的元素。
為清楚說明，用下圖解釋：
來回入隊、出隊比較麻煩，尤其是出隊比較麻煩，需要先將元素從stack1倒入stack2中，然后stack2彈出的元素又倒回到stack1中。有沒有更優(yōu)化的方案呢？以下方案2是改進之后的思路。
入隊都在stack1中進行，stack2用于隊列，同時保證所有元素都在一個棧里，且遵循以下約束：
入隊：不管stack1空與否，都將stack2中的所有元素壓入stack1中
出隊：若stack2中不為空，則直接從stack2中彈出元素；若stack2為空，則說明隊列為空，不能出隊。
方案2與方案1的區(qū)別在于，方案2中把倒回的操作放在了入隊中完成，使連續(xù)入隊、出隊的效率提高。有沒有更優(yōu)化的方案呢？以下對方案2改進，給出方案3.
3.解決方案三：入隊都在stack1中完成，出隊都在stack2中完成，且遵循以下約束：
入隊：直接把元素壓入stack1中；
出隊：若stack2中不為空，則直接彈出stack2中的元素；若stack2中為空，則將stack1中的所有元素倒入stack2中，然后彈出stack2的棧頂元素。同樣，若兩個棧都為空，則隊列為空隊，無法出隊。
方案3的特點是：入隊時非常簡單，而在出隊時，多數(shù)情況下可以直接通過彈出stack2完成。如果把stack1中的元素倒入stack2中，則一般不用每次都進行這樣的操作。最壞的情況就是出隊一個元素、入隊一個元素這樣的循環(huán)，導(dǎo)致每次出隊都需要轉(zhuǎn)移元素。
4.java代碼實現(xiàn)以下給出方案3的代碼實現(xiàn)：
public class Stacks2Queue {
private Stack stack1;
private Stack stack2;
private int maxLength;
public Stacks2Queue(int capacity){
maxLength = capacity;
stack1 = new Stack(capacity);
stack2 = new Stack(capacity);
}
/**
* 隊列入隊
* @param element 入隊元素
* @return 入隊成功？
*/
public boolean put(int element){
if(stack1.isFull() || maxLength == stack1.getSize()){
//此時stack1滿
return false;
}
stack1.push(element);
return true;
}
/**
* 隊列出隊
* @return 出隊的元素
*/
public int poll(){
if(!stack2.isEmpty()){
return stack2.pop();
}else{
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}return stack2.pop();
}
}
/**
* 求隊列長度
* @return 返回隊列長度
*/
public int getSize(){
return stack1.getSize()+stack2.getSize();
}
}
測試代碼如下：
public class Stack2QueueTest {
public static void main(String[] args) {
Stacks2Queue q = new Stacks2Queue(5);
q.put(1); //入隊元素 1
q.put(2); //入隊元素 2
System.out.println("出隊的元素為"+q.poll()); //出隊元素 打印1
System.out.println("此時隊列長度為"+q.getSize()); //返回1
q.put(3); //入隊元素 3
q.put(4); //入隊元素 4
System.out.println("出隊的元素為"+q.poll()); //出隊元素 打印2
System.out.println("出隊的元素為"+q.poll()); //出隊元素 打印3 本次出隊操作會把3和4兩個元素從stack1中倒入stack2中
}
}
注：以上代碼用到了堆和棧的代碼，請移步到前兩篇文章獲取Java數(shù)據(jù)結(jié)構(gòu)與算法——棧(stack)和Java數(shù)據(jù)結(jié)構(gòu)與算法——隊列（queue）
5.小結(jié)：
本文介紹了一個互聯(lián)網(wǎng)面試經(jīng)典問題如何用兩個棧實現(xiàn)隊列？并給出解決思路和java代碼實現(xiàn)，后續(xù)會給出其姊妹篇如何用兩個隊列實現(xiàn)棧？的問題。
歡迎下方討論提問,覺得文章對您有用，請收藏點個贊 ^_^
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/76361.html
摘要：基本解決方案按照上述的大體思路，我們給出解決方案入棧和出棧都在中完成，只作為臨時中轉(zhuǎn)空間。入棧入隊出棧除隊尾的元素外將其他所有元素出隊，再入隊中轉(zhuǎn)暫存，然后將中的元素出隊出棧。 聲明：碼字不易，轉(zhuǎn)載請注明出處，歡迎文章下方討論交流。 前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本篇介紹的是如何用兩個隊列實現(xiàn)棧的問題。這道題作為上一篇文章算法面試：棧實現(xiàn)隊列的方案的姊...
摘要：如問到是否使用某框架，實際是是問該框架的使用場景，有什么特點，和同類可框架對比一系列的問題。這兩個方向的區(qū)分點在于工作方向的側(cè)重點不同。 [TOC] 這是一份來自嗶哩嗶哩的Java面試Java面試 32個核心必考點完全解析（完） 課程預(yù)習(xí) 1.1 課程內(nèi)容分為三個模塊 基礎(chǔ)模塊： 技術(shù)崗位與面試 計算機基礎(chǔ) JVM原理 多線程 設(shè)計模式 數(shù)據(jù)結(jié)構(gòu)與算法 應(yīng)用模塊： 常用工具集 ...
摘要：題目編寫一個類，用兩個棧實現(xiàn)隊列，支持隊列的基本操作，，代碼實現(xiàn) 【題目】編寫一個類，用兩個棧實現(xiàn)隊列，支持隊列的基本操作（add，poll，peek） 代碼實現(xiàn) public class TwoStacksQueue { private Stack stackPush; private Stack stackPop; public TwoStacksQue...
摘要：總結(jié)的時間復(fù)雜度是，是空間是使用輔助棧來存儲最小值。項目就是為了解決配置繁瑣的問題，最大化的實現(xiàn)約定大于配置。 前言 只有光頭才能變強 Redis目前還在看，今天來分享一下我在秋招看過(遇到)的一些面試題(相對比較常見的) 0、final關(guān)鍵字 簡要說一下final關(guān)鍵字，final可以用來修飾什么？ 這題我是在真實的面試中遇到的，當時答得不太好，現(xiàn)在來整理一下吧。 final可以修飾...
閱讀 3138·2021-11-24 10:24
閱讀 2930·2021-11-11 16:54
閱讀 3066·2021-09-22 15:55
閱讀 2027·2019-08-30 15:44
閱讀 1901·2019-08-29 18:41
閱讀 2761·2019-08-29 13:43
閱讀 3053·2019-08-29 12:51
閱讀 1172·2019-08-26 12:19
