算法面試：隊列實現(xiàn)棧的方案

dabai 發(fā)布于2019-08-16 11:06 / 1144人閱讀

摘要：基本解決方案按照上述的大體思路，我們給出解決方案入棧和出棧都在中完成，只作為臨時中轉(zhuǎn)空間。入棧入隊出棧除隊尾的元素外將其他所有元素出隊，再入隊中轉(zhuǎn)暫存，然后將中的元素出隊出棧。

聲明：碼字不易，轉(zhuǎn)載請注明出處，歡迎文章下方討論交流。

前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本篇介紹的是如何用兩個隊列實現(xiàn)棧的問題。這道題作為上一篇文章算法面試：棧實現(xiàn)隊列的方案的姊妹篇（也是一道思路拓展題），本文給出問題的解決思路和Java實現(xiàn)代碼。

首先定義兩個隊列分別為queue1和queue2。

1.大體思路：

隊列實現(xiàn)棧，棧的特點是后進的先出，我們可以讓元素入隊queue1，留下隊尾元素讓其他元素出隊，暫存到queue2中，然后讓queue1中剩下的元素出隊，即最后進的最先出來。

2.基本解決方案

按照上述的大體思路，我們給出解決方案：入棧和出棧都在queue1中完成，queue2只作為臨時中轉(zhuǎn)空間。

入棧入隊queue1

出棧除queue1隊尾的元素外將其他所有元素出隊queue1，再入隊queue2（中轉(zhuǎn)暫存），然后將queue1中的元素出隊（出棧）。最后一步，將暫存在queue2中的元素再倒回queue1中。

為描述清晰，請看下圖：
事實上，這個思路和用兩個棧實現(xiàn)隊列的方案1類似，都是第二個數(shù)據(jù)區(qū)作為暫存中轉(zhuǎn)，最后在倒回到第一個數(shù)據(jù)區(qū)。

3.改進后的方案

上述方案是一個基本的最容易想到的解決方案，但是仔細觀察會發(fā)現(xiàn)其并不完美：在每次出棧步驟中要把queue2中的元素倒回到queue1中，這個操作很累贅，能否優(yōu)化一下，可不可以不用每次先出棧后倒回？？下面給出改進后的方案

入棧：

兩個隊列全空：任選一個隊列讓元素入隊，此處規(guī)定queue1

兩個隊列一個空：讓元素入隊非空的隊列

注：不考慮兩個隊列全滿，因為本身沒意義

出棧： 將非空隊列中除最后入隊的元素之外的其他所有元素入隊到另外一個隊列中，然后出隊剩下的那個元素（后進來的先出去，完成出棧）

相比于基本方案，改進后的方案沒有了基本方案中的倒回操作，整個流程變得簡潔高效，下面給出改進方案的java代碼實現(xiàn)。

4.java代碼實現(xiàn)

public class Queues2Stack {
    private ArrayQueue q1;
    private ArrayQueue q2;
    private int maxLength;
    
    public Queues2Stack(int capacity){
        maxLength = capacity;
        q1 = new ArrayQueue(capacity);
        q2 = new ArrayQueue(capacity);
    }
    
    public int getSize(){
        return q1.getsize()+q2.getsize();
    }
    
    /**
     * 入棧：
     * @param element 入棧元素
     * @return 入棧成功結(jié)果？
     */
    public boolean push(int element){
        if(getSize() == maxLength){ //隊列都滿，此情景無意義
            return false;
        }
        if(q2.isEmpty()){
            q1.put(element);
        }else{
            q2.put(element);
        }
        return true;
    }
    
    /**
     * 出棧
     * @return 出棧元素
     */
    public Object pop(){
        if(getSize()==0){
            throw new IndexOutOfBoundsException("空棧，無元素可出棧");
        }else{   //留非空隊列中最后一個元素，其他搬到空隊列中
            if(q2.isEmpty()){  
                while(q1.getsize()>1) q2.put(q1.pull()); 
                return q1.pull();  //出隊最后一個，實現(xiàn)后進先出
            }else{
                while(q2.getsize()>1) q1.put(q2.pull());
                return q2.pull();   //出隊最后一個，實現(xiàn)后進先出
            }
        }
    }
}

測試程序：

public class Queues2StackTest {
    public static void main(String[] args) {
        Queues2Stack s = new Queues2Stack(5);
        s.push(1);
        s.push(2);
        s.push(3);
        System.out.println(s.pop());  //返回3
        s.push(4);
        s.push(5);
        System.out.println(s.pop());  //返回5
        System.out.println(s.pop());  //返回4
        System.out.println(s.pop());  //返回2
        System.out.println(s.pop());  //返回1
        System.out.println(s.pop());  //拋出異常：提示棧為空
    }
}

注：以上代碼用到了堆和棧的代碼，請移步到前兩篇文章獲取Java數(shù)據(jù)結(jié)構(gòu)與算法——棧(stack)和Java數(shù)據(jù)結(jié)構(gòu)與算法——隊列（queue）。

本篇的姊妹篇請移步到之前的文章算法面試：棧實現(xiàn)隊列的方案

歡迎討論提問,覺得文章對您有用，請收藏點個贊 ^_^