《剑指offer》之用两个栈来实现一个队列

程序员爱酸奶

发布于 2020-02-29 17:18:20

3710

发布于 2020-02-29 17:18:20

文章被收录于专栏：程序员爱酸奶程序员爱酸奶

前言

今天刷的一道题是用两个栈来表示一个队列。我们知道栈和队列的主要区别在于：栈：后进先出队列：先进先出。

题目

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

分析

需要通过两个后进先出的栈实现一个先进先出的队列。如下图：

假设往栈stack1 中压入 1，2，3，4，5，6，7 这几个数据，如果直接从stack1中取的话，就是7，6，5，4，3，2，1.与我们想要你的先进先出不符合。所以我们将stack1的数据依次出栈并压入栈stack2 中，这样再从stack2 中出栈的数据就是1，2，3，4，5，6，7了。但是，上面的这些只考虑了先进栈后压栈。那如果是进栈出栈交替呢？

比如初始，向stack1 中压入 1，2，3.然后，将stack1 中的数据出栈入栈到stack2 中。

那这个时候，再往stack1 中进栈的话，该怎么压入栈stack2 中呢？这里其实大家应该注意到，如果stack2 中存在数据，那这些数据应该是最先出栈的，所以直接出栈就好了，不用管stack1 中的数据，因为那些是后来的数据，肯定是是后出栈的。当栈stack2 中没有数据的时候，再将stack1 中的数据都出栈压入stack2 中。这样就可以实现一个队列的先进先出啦。

解法

进队列，直接将数据压入栈stack1 中就好了。

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

出队列,先判断stack2 中是否有数据，有的话，直接从stack2 中出栈。如果没有，就将stack1 中的数据压入栈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();
    }
}

测试

本文参与?腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-02-07，如有侵权请联系?cloudcommunity@tencent.com 删除

编程算法

本文分享自程序员爱酸奶微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度