用俩个栈实现队列

古城微笑少年丶 2022-03-25 15:20 39阅读 0赞

# [用俩个栈实现队列][Link 1] #

## 题目描述 ##

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

posted @ 2018-08-04 21:13 [Octopus22][] 阅读( ...) 评论( ...) [编辑][Link 2] 收藏

[Link 1]: https://www.cnblogs.com/Octopus-22/p/9419677.html
[Octopus22]: https://www.cnblogs.com/Octopus-22/
[Link 2]: https://i.cnblogs.com/EditPosts.aspx?postid=9419677