01.用两个栈实现队列

目录介绍

• 01.题目要求
• 02.问题分析
• 03.实例代码

01.题目要求

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

02.问题分析

• 先来回顾一下栈和队列的基本特点：
  • 栈： 后进先出（LIFO）
  • 队列： 先进先出
  • 很明显我们需要根据JDK给我们提供的栈的一些基本方法来实现。先来看一下Stack类的一些基本方法：
  • 
    image
• 既然题目给了我们两个栈，我们可以这样考虑当push的时候将元素push进stack1，pop的时候我们先把stack1的元素pop到stack2，然后再对stack2执行pop操作，这样就可以保证是先进先出的。（负[pop]负[pop]得正[先进先出]）

03.实例代码

• 代码如下所示

  public class Solution {
  
      Stack<Integer> stack1 = new Stack<Integer>();
      Stack<Integer> stack2 = new Stack<Integer>();
       
      //当执行push操作时，将元素添加到stack1
      public void push(int node) {
          stack1.push(node);
      }
       
      public int pop() {
          //如果两个队列都为空则抛出异常,说明用户没有push进任何元素
          if(stack1.empty()&&stack2.empty()){
              throw new RuntimeException("Queue is empty!");
          }
          //如果stack2不为空直接对stack2执行pop操作，
          if(stack2.empty()){
              while(!stack1.empty()){
                  //将stack1的元素按后进先出push进stack2里面
                  stack2.push(stack1.pop());
              }
          }
            return stack2.pop();
      }
      
      public boolean empty() {
          return q1.isEmpty() && q2.isEmpty();
      }
  }