如何用兩個棧來實現(xiàn)一個隊列及其Push和Pop操作

如何用兩個棧來實現(xiàn)一個隊列及其Push和Pop操作，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

今天刷的一道題是用兩個棧來表示一個隊列。我們知道棧和隊列的主要區(qū)別在于：棧：后進先出 隊列：先進先出。

題目

用兩個棧來實現(xiàn)一個隊列，完成隊列的Push和Pop操作。隊列中的元素為int類型。

分析

需要通過兩個后進先出的棧實現(xiàn)一個先進先出的隊列。如下圖：假設(shè)往棧stack1 中壓入 1，2，3，4，5，6，7 這幾個數(shù)據(jù)，如果直接從stack1中取的話，就是7，6，5，4，3，2，1.與我們想要你的先進先出不符合。所以我們將stack1的數(shù)據(jù)依次出棧并壓入棧stack2 中，這樣再從stack2 中出棧的數(shù)據(jù)就是1，2，3，4，5，6，7了。但是，上面的這些只考慮了先進棧后壓棧。那如果是進棧出棧交替呢？比如初始，向stack1 中壓入 1，2，3.然后，將stack1 中的數(shù)據(jù)出棧入棧到stack2 中。那這個時候，再往stack1 中進棧的話，該怎么壓入棧stack2 中呢？這里其實大家應(yīng)該注意到，如果stack2 中存在數(shù)據(jù)，那這些數(shù)據(jù)應(yīng)該是最先出棧的，所以直接出棧就好了，不用管stack1 中的數(shù)據(jù)，因為那些是后來的數(shù)據(jù)，肯定是是后出棧的。當(dāng)棧stack2 中沒有數(shù)據(jù)的時候，再將stack1 中的數(shù)據(jù)都出棧壓入stack2 中。這樣就可以實現(xiàn)一個隊列的先進先出啦。

解法

進隊列，直接將數(shù)據(jù)壓入棧stack1 中就好了。

public void push(int node){
        stack1.push(node);
    }

出隊列,先判斷stack2 中是否有數(shù)據(jù)，有的話，直接從stack2 中出棧。如果沒有，就將stack1 中的數(shù)據(jù)壓入棧stack2 中。然后再從stack2 中出棧。

public int pop(){
        if(!stack2.isEmpty()){
            return stack2.pop();
        }
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }

不過上面的代碼還可以簡化一下，畢竟兩個return stack2.pop(); 有點不舒服。

public int pop(){
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

源代碼：

public class Solution {
    Stack<Integer> stack1=new Stack<>();
    Stack<Integer> stack2=new Stack<>();

    public static void main(String[] args) {
        Solution solution= new Solution();
        solution.push(0);
        solution.push(1);
        solution.push(2);
        solution.push(3);
        solution.push(4);
        solution.push(5);
        System.out.print(solution.pop()+"\t");
        System.out.print(solution.pop()+"\t");
        System.out.print(solution.pop()+"\t");
        solution.push(6);
        solution.push(7);
        solution.push(8);
        System.out.print(solution.pop()+"\t");
        System.out.print(solution.pop()+"\t");
        System.out.print(solution.pop()+"\t");
    }

    public void push(int node){
        stack1.push(node);
    }

    public int pop(){
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }

        return stack2.pop();
    }
}

測試

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。