面试题9：用两个栈实现队列

用两个栈实现一个队列，队列的声明如下：

template <typename T> class CQueue
{
public:
    void appendTail(const T& element);
    T deleteHead();

private:
    stack<T> stack1;
    stack<T> stack2;
};

请实现两个成员函数，分别完成 1. 在队列尾部插入节点；2. 删除队列头部节点并返回之。

答案：

template<typename T>
void CQueue<T>::appendTail(const T& element)
{
    stack1.push(element);
}

template<typename T>
T CQueue<T>::deleteHead()
{
    T ret;
    if (!stack2.empty())
    {
        ret = stack2.top();
        stack2.pop();
    }
    else
    {
        while(!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
        ret = stack2.top();
        stack2.pop();
    }
    return ret;
}