剑指Offer09. 用两个栈实现队列

题目描述

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

示例 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 次调用

JAVA代码

算法设计思想

栈的特点时后进先出，队列的特点是先进先出。
所以，当用两个栈stackA,stackB模拟一个队列时，stackA作为输入栈，逐个元素压栈，模拟队列的入队。
stackB作为输出栈，模拟出队。
当模拟出队时，如果stackB有数据就直接出栈，否则将stackA退栈并逐个压入stackB中，stackA最先入栈的元素在stackB中处于栈顶。这样执行完后，stackB退栈，就相当于队列的先进先出。
队空：当stackA和stackB都为空时。

经典方法

class CQueue {
    

    Stack<Integer> stackA;
    Stack<Integer> stackB;

    public CQueue() {
    
        //新建两个栈，stackA作为队列的队尾，用来入队，stackB作为队列的队头，用来出队。
        stackA= new Stack<Integer>();
        stackB = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
    
        //假设stack是无限大小，就不用判断stackA栈满了。
        stackA.push(value);
    }
    
    public int deleteHead() {
    
        if(stackB.isEmpty()){
    
            //没有数据
            if(stackA.isEmpty()){
    
                return -1;
            }else{
    
            //stackB为空，stackA不为空时，将stackA的数组出栈，再入栈到stackB中，再模拟出队操作。
                while(!stackA.isEmpty()){
    
                    stackB.push(stackA.pop());
                }
            }
        }
        //出队
        return stackB.pop();
    }
}

/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

官方方法

根据官方的方法，修改如下：
由于Stack性能低，官方已经不推荐使用了，所以我们可以将栈的创建方法修改
现在官方推荐使用 java.util.Deque。类似下面的用法：

Deque<Integer> stackA = new ArrayDeque<Integer>();

参考 ：有动态的图解演示

https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/tu-jie-guan-fang-tui-jian-ti-jie-yong-li-yjbf/

拓展：Deque的方法