用两个栈实现队列

 2019-10-270 Comments

队列是先进先出的,栈是先进后出的,使用两个栈s1,s2,s1用于添加,s2用于队列poll,add时候直接加到s1中,poll的时候如果s2不为空就直接pop s2,如果为空就把s1中的元素依次pop出来,push到s2中,来保证元素的顺序是入时候的顺序。

class Queue<E>{
    Stack<E> inStack;
    Stack<E> outStack;

    public Queue() {
        this.inStack = new Stack<>();
        this.outStack = new Stack<>();
    }

    public void add(E e){
        if(e==null){
            throw new NullPointerException();
        }
        inStack.push(e);
    }

    public E poll(){
        if(!outStack.empty()){
            return outStack.pop();
        }
        if(inStack.empty()){
            throw new RuntimeException("队列为空");
        }
        while(!inStack.empty()){
            outStack.push(inStack.pop());
        }
        return outStack.pop();
    }
}