题目描述

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

 

思路：

栈是先进后出的结构，而队列是先进先出的结构，题目中给出俩个栈，一个栈只能完成特定的操作，如何才能利用俩个栈让元素能够先进去先出来？

一个栈元素是后出，那么叠加式把一个栈放入另一个栈中，该元素的出入顺序就变成了先入先出。

 

注意：这里有一个细节很重要

 

if(stack2.empty()){...}     这句话的意思就是在stack2的元素没有全部出栈的情况下，是不够执行入栈操作的，我在第一次做的时候就未加这句话，结果出现下面错误

测试用例:

["PSH1","PSH2","PSH3","POP","POP","PSH4","POP","PSH5","POP","POP"]

对应输出应该为:

1,2,3,4,5

你的输出为:

1,2,4,5,3

 

由于你的stack2没有全部出栈就又重新入栈了，则导致当前“队列”出队列元素就是永远都是你的新入栈元素，结果就会错误。

例如输入样例为上（很尴尬，当时只想到了判断栈1空没有想到这里，看了测试结果恍然大悟）

 

 

1 import java.util.Stack; 2 public class Solution { 3     Stack
       
         stack1 = new Stack
        
         (); 4     Stack
         
           stack2 = new Stack
          
           (); 5       6     public void push(int node) { 7         stack1.push(node); 8     } 9      10     public int pop() {11         if(stack1.empty()&&stack2.empty()){12            System.out.println("The queue is empty!");13         }14         if(stack2.empty()){ 15             while(!stack1.empty()){16                 stack2.push(stack1.pop());17             }18     }19         return stack2.pop();20     }21 }