剑指offer9:用两个栈实现队列

分析：这题主要是思路，怎么用两个栈实现一个队列呢？

我们来看看书中的一个例子，首先依次插入a,b,c，然后，如果我们想删除队列头怎么办？是要删除a，但是栈是先入后出的，所以我们只能先取到c，如果序列能够反过来就好了对吧。不要忘记我们有第二个栈，这里我们把第一个栈的内容按顺序取出，装入第二个栈，第二个栈就是这样：

a

b

c

这时我们再把栈顶元素a删除不就实现了删除队列头的功能吗？

总的来说删除队列头的操作是这样的：

1.第二个栈不为空，删除第二个栈的栈顶元素即可

2.第二个栈为空，将第一个栈的元素按顺序取出，依次压入第二个栈，删除第二个栈的栈顶元素

那插入怎么做呢？很简单，直接压入到第一个栈就好了

代码如下所示：

class CQueue {
    stack<int> stack1,stack2;
public:
    CQueue() {
        while(!stack1.empty())
        {
            stack1.pop();
        }
        while(!stack2.empty())
        {
            stack2.pop();
        }
    }
    
    void appendTail(int value) {
        stack1.push(value);
    }
    
    int deleteHead() {
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        if(stack2.empty())
        {
            return -1;
        }
        int ans=stack2.top();
        stack2.pop();
        return ans;
    }
};