剑指 Offer 09. 用两个栈实现队列

用栈实现队列

题目链接-来源：力扣（LeetCode）

示例 1：

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

思路：

栈的特点是后进先出，队列特点是后进后出。对于『后进』的特点， appendTail() 可以直接调用 push() ，我们只需特殊考虑怎么用『先出』实现『后出』。
容易想到，用一个辅助栈 helper，将主栈 main 的元素依次压入辅助栈中，即『逆序』了主栈中的元素，此时弹出辅助栈顶元素即为我们需要的队列的头部元素，也即 deleteHead() 的返回值。然后将 helper 中元素依次放回 main 中。
为了避免将元素在两个栈来回搬运，注意到从队列的视角看，helper 中的元素相对 main 都是较早进队的元素，那么出队时，我们优先考虑 helper 即可；同理，main中的元素较新，在入队时，我们要优先考虑 main。也就是说，在 helper 不空时，需要出队时我们只要对 helper 调用 pop() 即可，而入队时对 main 调用 push()。特例发生在 helper 为空时，我们需要重复一开始的操作，将 main 中元素全部压入 helper 中，之后再进行判断和出队操作。

时间复杂度：O(n)
空间复杂度：O(n)

进一步简化：

我们用双栈实现了队列。考虑到程序如果采用递归的方式，也会自动形成调用栈，那么我们能否只用单栈，配合递归操作实现队列。
首先入队操作不变。
其次考虑递归函数 recur()，回想我们最初有放回版本的操作，我们每次取到辅助栈 helper 中的元素，就是 main 的栈顶元素，这个元素我们之后要放回，所以需要用一个变量 previous 来记录它；现在我们用递归的调用栈取代辅助栈 helper，我们的目的是弹出 main 中的元素直到空为止，我们需要的栈底元素需要通过 recur() 返回值层层传递上来，这个值我们用 toReturn 记录；之后压回 previous；最后返回 toReturn。
时间复杂度：O(n) 此操作的效率低于优化（不放回）的双栈，与未优化（有放回）的双栈效率相当，权当单栈下的思路分享。
空间复杂度：O(n)

实现（双栈）：

class CQueue {
    private Stack<Integer> sMain;
    private Stack<Integer> sHelper;

    public CQueue() {
        sMain = new Stack<>();
        sHelper = new Stack<>();
    }
    
    public void appendTail(int value) {
        sMain.push(value);
    }
    
    public int deleteHead() {  
        if(sHelper.isEmpty()) {
            while (!sMain.isEmpty()) {
            sHelper.push(sMain.pop());
            }
        }
        
        if (sHelper.isEmpty()) {
            return -1;
        }
        
        return sHelper.pop();       
    }
}

实现（单栈）：

class CQueue {
    private Stack<Integer> sMain;

    public CQueue() {
        sMain = new Stack<>();
    }
    
    public void appendTail(int value) {
        sMain.push(value);
    }
    
    public int deleteHead() {  
        if (sMain.isEmpty()) {
            return -1;
        }
        return poll();
    }
    private int poll() {
        if (sMain.size() == 1) {
            return sMain.pop();
        }
        int previous = sMain.pop();
        int toReturn = poll();
        appendTail(previous);
        return toReturn;
    }
}