使用两个栈实现队列

1.题目

使用两个栈实现队列的push,poll,peek操作

2.解决

栈的特点是先进后出,队列的特点是先进先出,使用两个栈可以保证顺序的正确性,一个栈记为stackPush,另一个栈记为stackPop,每次进行push操作时,在stackPush中只需要正常入栈

即可,队列进行poll操作时,如果stackPop栈为空,把stackPush栈里面的所有元素全部pop出来,并压入到stackPop栈栈里面,这时stackPop栈的栈顶元素,就是最先进来的元素,只需要返回stackPop.pop()即可,如果队列再一次执行pop,那么再一次返回栈顶。队列的peek操作同样如此,只需要返回stackPop栈的peek()即可


代码实现:

package java1;

import java.util.Stack;

/**
 * @Author : hadoo
 * @Date : 2020/3/17 18:28
 */
public class twoStackQueue {
   private Stack<Integer> stackPush;
   private Stack<Integer> stackPop;
   public twoStackQueue(){
       stackPush = new Stack<>();
       stackPop = new Stack<>();
   }
   //实现队列的push方法
    public void push(int data){
       stackPush.push(data);
    }
    //实现队列的poll方法
    public int poll(){
       if(stackPop.isEmpty() && stackPush.isEmpty())
           throw new RuntimeException("Queue is empty!");
       if(stackPop.isEmpty()){
           while(!stackPush.isEmpty())
               stackPop.push(stackPush.pop());
       }
       return stackPop.pop();
    }
    //实现队列的peek方法
    public int peek(){
        if(stackPop.isEmpty() && stackPush.isEmpty())
            throw new RuntimeException("Queue is empty!");
        if(stackPop.isEmpty()){
            while(!stackPush.isEmpty())
                stackPop.push(stackPush.pop());
        }
        return stackPop.peek();
    }
}