用两个栈实现队列

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

image.png

思路解题
将一个栈当作输入栈，用于压入appendTail传入的数据；另一个栈当作输出栈，用于deleteHead 操作。
每次deleteHead 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序（也就是输入栈从队尾到队首）。

代码如下

class CQueue {
        Deque<Integer> inStack;
        Deque<Integer> outStack;
        public CQueue(){
            inStack = new ArrayDeque<Integer>();
            outStack = new ArrayDeque<Integer>();
        }

        public void appendTail(int value) {
            inStack.push(value);
        }

        public int deleteHead() {
            if (outStack.isEmpty()){
                if (inStack.isEmpty()){
                    return -1;
                }
                in2out();
            }
            return outStack.pop();
        }

        private void in2out() {
            while (!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
    }

复杂度分析
时间复杂度：appendTail为 O(1)，deleteHead为均摊O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)。
空间复杂度：O(n)。其中 nn 是操作总数。对于有 n 次 appendTail 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)。