题目描述

题目地址：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

用两个栈实现一个队列。

队列的声明如下：请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

解题思路

K神题解：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

LinkedList 底层是双向链表，既可以用作栈也可以用作队列，所以用 LinkedList 来模拟栈是可以的。

addLast( ) 表示向链表尾部插入元素，等价于向栈顶插入元素；
removeLast ( ) 表示从链表尾部取出元素，等价于从栈顶取出元素。

• A 和 B 都可以在某一个时刻存储着队列的所有元素，取决于添加元素和删除队首元素的方法执行了没有：
• 一开始，如果只是添加元素，那就只有栈 A 保存着所有的元素；
• 这时一旦调用了一次删除队首元素，那么原先在栈 A 的所有元素都会以倒序的顺序搬到栈 B ，然后栈 B 的栈顶元素出栈，实现删除队首元素；
• 这时候栈 B 中的剩余元素不用再重新搬回到栈 A 中，因为此时队列的功能并没有被破坏；比如这时若要在队列尾增加元素，就相当于在空的栈 A 中添加元素，功能完全不受影响；而此时的栈 B 是存在元素的，此刻的栈 A 并不能以倒序的方式加到栈 B 中，而是要先等到栈 B 的所有元素都出栈后，栈 A 的元素才可以倒序进入到栈 B（体现在代码中就是在删除队首元素的方法中首先判断 B 栈是否为空，而不能先将栈 A 的元素倒序搬到栈 B 中！）。

• 所以说栈 A 和栈 B 可以同时存储着数据来表示队列，只要队列的功能不受破坏就行了！

• 核心是栈 A 实现在队尾添加元素，栈 B 实现删除队首元素并返回；而在栈 B 删除队首元素的同时，若栈 B 还有元素，则在执行删除队首元素方法的时候，不会将栈 A 还有的元素搬到栈 B 中，而是先执行了将栈 B 栈顶的元素出栈实现删除队首元素并结束方法；直到等到栈 B 为空时，在执行删除队首元素的方法的时候才会将栈 A 的元素倒序搬到栈 B 中。

class CQueue {
    Stack<Integer> A,B;
    public CQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void appendTail(int value) {
        A.add(value);
    }
    public int deleteHead() {
        if(!B.empty()) return B.pop();
        if(A.empty()) return -1;
        while(!A.empty()){
            B.add(A.pop());
        }
        return B.pop();
    }
}

// 用 LinkedList 模拟栈
LinkedList<Integer> A, B;
public CQueue() {
    A = new LinkedList<Integer>();
    B = new LinkedList<Integer>();
}
public void appendTail(int value) {
    A.addLast(value);
}
public int deleteHead() {
    if(!B.isEmpty()) return B.removeLast();
    if(A.isEmpty()) return -1;
    if(B.isEmpty()) {
        while(!A.isEmpty()) {
            B.addLast(A.removeLast());
        }
    }
    return B.removeLast();
}