算法43（用俩个栈实现队列）

57.用俩个栈实现队列。
题目：某队列的声明如下：
template<typename T> class CQueue
{
public:
      CQueue() {}
      ~CQueue() {}

      void appendTail(const T& node);  // append a element to tail
      void deleteHead();               // remove a element from head

private:
     T> m_stack1;
     T> m_stack2;
};

分析：从上面的类的声明中，我们发现在队列中有两个栈。
因此这道题实质上是要求我们用两个栈来实现一个队列。
相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，
因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器，
我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。
参考代码如下：
// Append a element at the tail of the queue
template<typename T> void CQueue<T>::appendTail(const T& element)
{
      // push the new element into m_stack1
      m_stack1.push(element);
}

// Delete the head from the queue
template<typename T> void CQueue<T>::deleteHead()
{
      // if m_stack2 is empty, and there are some
      // elements in m_stack1, push them in m_stack2
      if(m_stack2.size() <= 0)
      {
            while(m_stack1.size() > 0)
            {
                  T& data = m_stack1.top();
                  m_stack1.pop();
                  m_stack2.push(data);
            }
      }

      // push the element into m_stack2
      assert(m_stack2.size() > 0);
      m_stack2.pop();
}

扩展：这道题是用两个栈实现一个队列。反过来能不能用两个队列实现一个栈？如果可以，该如何实现？

用两个栈实现一个队列的功能？要求给出算法和思路！设2个栈为A,B, 一开始均为空. 入队:将新元素push入栈A;出队:(1)判断栈B是否为空；(2)如果不为空，则将栈A中所有元素依次pop出并push到栈B；(3)将栈B的栈顶元素pop出；这样如果B中有数据 那不是把A中的新元素给丢弃了。求过程

问题补充：

弹栈和出栈一样吗？

举例说明，假设我们进行以下4步：push 1, 2pop //此时应pop 1push 3pop //此时应pop 2在运行第一个pop时，把A中的1,2全push到B中去，然后再pop得到1，此时B中还剩一个2下一步push 3，是push到A中最后一步pop，把B中的2给pop出去关键点：(2)如果不为空，则将栈A中所有元素依次pop出并push到栈B；这里隐含了一点，如果为空，就直接从B中pop，不对A进行任何操作。很显然，需要if..else语句。 弹栈和一般的出栈不同，需要多一部检测B是否为空。如果B不为空，则直接从B出栈，这时与一般的出栈相同。如果B为空，则需要把A中所有的元素出栈并压栈到B中去，然后再对B进行一般的出栈操作。