【百日算法计划】：每日一题，见证成长（017）

题目

用栈来实现队列

思路1

入队直接入，出队用两个栈来回倒腾。

static class StackToQueue{

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> tmpStack = new Stack<>(); //临时栈

    public StackToQueue(){}

    //入队 直接入
    public void enqueue(Integer val){
        stack.push(val);
    }

    //出队
    public Integer dequeue(){

        if (stack.isEmpty()) return null;

        while (!stack.isEmpty()){
            tmpStack.push(stack.pop());
        }

        Integer pop = tmpStack.pop();
        while (!tmpStack.isEmpty()){
            stack.push(tmpStack.pop());
        }
        return pop;
    }
}

思路2

入队来回倒腾，出队直接出。

static class StackToQueue2{
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> tmpStack = new Stack<>(); //临时栈

    public StackToQueue2(){}

    //入队 两个栈倒腾
    public void enqueue(Integer val){
        //新元素进来时，把stack里面的元素倒腾到tmp里去
        while (!stack.isEmpty()){
            tmpStack.push(stack.pop());
        }
        stack.push(val);
        while (!tmpStack.isEmpty()){
            stack.push(tmpStack.pop());
        }
    }

    //出队
    public Integer dequeue(){
        if (stack.isEmpty()) return null;
        return stack.pop();
    }
}

思路3

倒腾到tmpStack后，不用再倒腾回去了；当tmpStack不为空的时候，直接从tmpStack出队。

static class StackToQueue3{

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> tmpStack = new Stack<>(); //临时栈

    public StackToQueue3(){}

    //入队 直接入
    public void enqueue(Integer val){
        stack.push(val);
    }

    //出队 优化一下
    public Integer dequeue(){

        if (stack.isEmpty() && tmpStack.isEmpty()) return -1;
        int r;
        if (!tmpStack.isEmpty()){
            r = tmpStack.pop();
        } else {
            while (!stack.isEmpty()){
                tmpStack.push(stack.pop());
            }
            r = tmpStack.pop();
        }
        return r;
    }
}