[数据结构与算法]Day【5】用栈实现队列

思路

栈的特点是先进后出， 队列的特点是先进先出。 我们可以设计两个栈， 一个栈stackPush用来存放数据， 另一个栈stackPop用来存放stackPush栈中元素的倒序结果， 利用栈的特点，删除stackPop的栈顶， 就相当于进行了出队操作。 比如说：

• stackPush: 栈底 1 2 3 4 5 栈头
• stackPop: 栈底 5 4 3 2 1 栈头

按照队列的顺序1 2 3 4 5。出队的话，就是出 1，相当于就是 stackPop的队头。

向栈中添加元素

• 向stackPush中添加即可

删除队头元素

• 当stackPop中仍然有元素的时候，直接返回头即可
• 如果上一步没有执行，说明stackPop中没有元素，先判断一下 ，有没有向stackPush中添加元素，如果说没有，返回 -1
• 最后，说明stackPush中有元素，但是没有倒在stackPop中，倒入
• 返回 stackPop的栈顶

代码

class MyQueue {
    private LinkedList<Integer> stackPush;
    private LinkedList<Integer> stackPop;
    private int size;
    public MyQueue() {
        size = 0;
        stackPop = new LinkedList<>();
        stackPush = new LinkedList<>();
    }
    
    public void push(int x) {
        size++;
        stackPush.add(x);
    }
    
    public int pop() {
        size--;
        //移除队列开头的元素
        if(!stackPop.isEmpty()) return stackPop.removeLast();
        if(stackPush.isEmpty()) return -1;
        while(!stackPush.isEmpty()) {
            stackPop.addLast(stackPush.removeLast());
        }
        return stackPop.removeLast();
    }
    
    public int peek() {
        // 返回队列开头的元素
        if(!stackPop.isEmpty()) return stackPop.getLast();
        if(stackPush.isEmpty()) return -1;
        while(!stackPush.isEmpty()) {
            stackPop.add(stackPush.removeLast());
        }
        return stackPop.getLast();

    }
    
    public boolean empty() {
        return size == 0;
    }
}