225 用队列实现栈

注意: 队列的基本操作为add和poll和isEmpty，栈的基本操作为push和pop和empty

思路：

• 准备两个队列，一个queue队列一个help队列

• 执行push操作时，只向queue队列中add元素

• 执行pop操作时，将queue中元素弹入help中，只剩下一个需要弹出的元素，将queue中剩下的这一个元素保存后弹出。 最后，将help和queue互换，因为此时queue已弹空，原来queue元素均导入到help中。为了实现任何入列都是入到queue中，因此需将两个队列互换

• 执行peek操作时，与pop操作大体相同。只是peek并未真要弹出栈顶元素，只是取出而已。所以需要将这个元素也加进help中。最终的效果相当于把queue中元素均加入到help中，再将help与queue互换

• queue队列为空栈即为空

• *代码：**

  class MyStack {
  
      Queue<Integer> queue1;
      Queue<Integer> help;
      
      /** Initialize your data structure here. */
      public MyStack() {
          queue1 = new LinkedList<>();
          help = new LinkedList<>();
      }
      
     public void push(int x) {
          //只向队列queue中push元素
          queue1.add(x);
      }
      
      /** Removes the element on top of the stack and returns that element. */
      public int pop() {
          //将queue中元素弹入help中，只剩下一个需要弹出的元素
          while(queue1.size() != 1)
              help.add(queue1.poll());
          //将queue中剩下的这一个元素保存后弹出
          int res = queue1.poll();
          //将help和queue互换
  		//因为此时queue已弹空，原来queue元素均导入到help中。
  		//为了实现任何入列都是入到queue中，因此需将两个队列互换
          swap();
          return res;
      }
      
      /** Get the top element. */
      //取队顶元素的peek操作大体与pop相同，只是peek并未真要弹出栈顶元素，只是取出而已
  	//所以需要将这个元素也加进help中。最终的效果相当于把queue中元素均加入到help中，再将help与queue互换
      public int top() {
          while(queue1.size() != 1)
              help.add(queue1.poll());
          int res = queue1.poll();
          help.add(res);
          swap();
          return res;
      }
      
      /** Returns whether the stack is empty. */
      public boolean empty() {
          return queue1.isEmpty();
      }
      
      private void swap() {
          Queue<Integer> tmp = help;
          help = queue1;
          queue1 = tmp;
      }
  }