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

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

景宁畲族自治ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：028-86922220（备注：SSL证书合作）期待与您的合作！

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

题目

用两个栈来实现一个队列，完成队列的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 stack1=new Stack<>();
   Stack 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();
   }
}

测试

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