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