温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何用两个栈来实现一个队列及其Push和Pop操作

发布时间:2021-12-03 09:12:34 来源:亿速云 阅读:124 作者:柒染 栏目:大数据

如何用两个栈来实现一个队列及其Push和Pop操作,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。

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

题目

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

分析

需要通过两个后进先出的栈实现一个先进先出的队列。如下图:如何用两个栈来实现一个队列及其Push和Pop操作假设往栈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了。但是,上面的这些只考虑了先进栈后压栈。那如果是进栈出栈交替呢?如何用两个栈来实现一个队列及其Push和Pop操作比如初始,向stack1 中压入 1,2,3.然后,将stack1 中的数据出栈入栈到stack2 中。如何用两个栈来实现一个队列及其Push和Pop操作那这个时候,再往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();
   }
}

测试

如何用两个栈来实现一个队列及其Push和Pop操作如何用两个栈来实现一个队列及其Push和Pop操作

看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注亿速云行业资讯频道,感谢您对亿速云的支持。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI