用两个栈实现队列

用两个栈实现队列

题目

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

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


示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

• 1 <= values <= 10000
• 最多会对 appendTail、deleteHead 进行 10000 次调用

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

题目要求用栈实现，完成在队列尾部插入整数和在队列头部删除整数的功能。

栈的特点是先进后出，先进入栈的元素最后出栈，如果想要删除栈底元素，只能将其他元素出栈。

此时就可以用两个栈，栈A元素出栈进入B中，这样在栈A中处于栈底的元素就是栈B的栈顶元素。此时栈B出栈就相当于删除栈A的栈底元素。

所以在完成功能时，可以利用栈A实现队列尾部插入整数，利用栈B进行反转栈A，将栈B的栈顶元素出栈实现删除队列头部整数。

此时栈B出栈栈顶元素时有一下几种情况：

• 栈A不为空，栈B为空时，将栈A元素转到栈B中，返回栈B的栈顶元素，即栈A的栈底元素
• 当栈A为空，栈B也为空时，两个栈都没有元素，说明此队列中没有元素，deleteHead操作返回-1
• 当栈B不为空时，此时栈B中依旧有反转后的元素，栈B的栈顶依旧是栈A的栈底（因为栈是先进后出，即使栈A添加了元素或者栈A中依旧有元素，但是不影响栈B的栈顶元素是栈A的栈底元素）

示例一：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]

[[],[3],[],[]]

输出：[null,null,3,-1]

作者：jyd
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码实现

class CQueue {

    LinkedList<Integer> A, B;

    public CQueue() {
        //创建栈A和栈B并初始化
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        //添加数据
        A.addLast(value);
    }
    
    public int deleteHead() {
        //分三种情况

        //1. 栈A，B都为空时，表示队列没有数据
        if(A.isEmpty()&& B.isEmpty()){
            return -1;
        }

        //2. 当B不为空时，输出B的栈顶元素
        if(!B.isEmpty()){
            return B.removeLast();
        }

        //3. 当A不为空，B为空时,要将A中的数据转到B中
        while(!A.isEmpty()){
            B.addLast(A.removeLast());
        }
        return B.removeLast();
    }
}