[数据结构与算法]每日写题分享--双栈实现队列

题目描述：

?题目链接：双栈实现队列

解题思路：

这题考察的就是出入栈和出入队列的顺序，栈是先进后出的数据结构，队列是先进先出的数据结构，要用栈实现队列的功能，只要用两个站互相倒元素，出入栈顺序就能反过来。

这里我没有直接使用stack，因为stack继承了vector接口，vector底层是Object[]数组，要考虑空间扩容和移位等因素，会导致速度比较慢。而LinkedList实现了Deque接口，可以用Linkedlist做stack的容器。

1.创建两个栈

2.在队尾插入元素。前面说了，用两个栈模拟队列的功能，队列是先进先出，后进后出的，在队列队尾插入元素，就要最后出这个元素。那么先给元素放入到stack1（入元素栈）。

3.删除头结点。要考虑出队的问题就要考虑顺序的问题，刚才入栈是在stack1里面，现在出栈如果用stack1那就是先进后出的顺序，所以要将stack1里面的元素倒过来。做法是：将stack1的所有元素一次倒入stack2中st2.push(st1.pop());但是这么做有个前提，就是stack2中没有元素，因为如果stack2中有元素，说明上次倒入的元素还没有出完，此时如果将stack1元素倒入stack2中，顺序就会打乱，所以在出队之前要有判空，如果stack2倒完了，才能执行st2.push(st1.pop())。

代码实现如下：

class CQueue {
    private LinkedList<Integer> st1;
    private LinkedList<Integer> st2;
    public CQueue() {
        st1 = new LinkedList<>();
        st2 = new LinkedList<>();
    }

    public void appendTail(int value) {
        st1.push(value);
    }
    
    public int deleteHead() {
        if (st2.isEmpty()) {
            if (st1.isEmpty()) return -1;
            while (!st1.isEmpty()) {//判空，只有stack2的元素都出栈了，才能入栈新的元素
                st2.push(st1.pop());
            }
            return st2.pop();
        } else return st2.pop();
    }
}