一，题目

       某队列的声明如下：

template
    
       class CQueue{public:      CQueue() {}      ~CQueue() {}      void appendTail(const T& node);  // append a element to tail      void deleteHead();               // remove a element from headprivate:     T  m_stack1;     T  m_stack2;};
    

二，分析

          栈：后入先出，插入删除在栈顶操作

          队列：先入先出，插入在队尾，删除在队首

          因此对队列进行的插入和删除操作都是在栈顶上进行；我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。

          1）stack1  入队队列 的栈

          2）stack2  出队队列 的栈，如果出队列时候，stack2为空则将stack1中元素全部弹入stack2，然后出栈

三，参考代码如下：

 

template
    
      void CQueue
     
      ::appendTail(const T& element)//入队 {      m_stack1.push(element);}template
      
        void CQueue
       
        ::deleteHead() //出队 {      if(m_stack2.size() <= 0)      {            while(m_stack1.size() > 0)            {                  T& data = m_stack1.top();                  m_stack1.pop();                  m_stack2.push(data);            }      }      assert(m_stack2.size() > 0);      m_stack2.pop();}
       
      
     
    

扩展：用两个队列实现一个栈？

思路：

        1.有两个队列q1和q2，先往q1内插入a，b，c，这做的都是栈的push操作。

        2.现在要做pop操作，即要得到c，这时可以将q1中的a,b两个元素全部dequeue并存入q2中，这时q2中元素为a，b，对q1再做一次dequeue操作即可得到c。

        3.如果继续做push操作，比如插入d，f，则把d，f插入到q2中，

        4.此时若要做pop操作，则做步骤2

        5.以此类推，就实现了用两个队列来实现一个栈的目的。

       注意在此过程中，新push进来的元素总是插入到非空队列中，空队列则用来保存pop操作之后的那些元素，那么此时空队列不为空了，原来的非空队列变为空了，总是这样循环。

对于push和pop操作，其时间为O(n).

 

#include 
    
     #include 
     
      #include 
      
       using namespace std;// 两个队列实现一个栈template
       
         class CStack{public:    CStack() {}    ~CStack() {}    void mypush(const T& element);      void mypop();               private:    deque 
        
          m_queue1;    deque 
         
           m_queue2;};template
          
            void CStack
           
            ::mypop() //出栈 { if (m_queue1.size() == 0) { while (m_queue2.size() > 1) { T& data = m_queue2.front(); m_queue2.pop_front(); m_queue1.push_back(data); } assert(m_queue2.size() == 1); //确保队列2内有一个元素 T& result = m_queue2.front(); m_queue2.pop_front(); cout << result << endl; } else if (m_queue2.size() == 0) { while (m_queue1.size() > 1) { T& data = m_queue1.front(); m_queue1.pop_front(); m_queue2.push_back(data); } assert(m_queue1.size() == 1); //确保队列1内有一个元素 T& result = m_queue1.front(); m_queue1.pop_front(); cout << result << endl; }}template
            
              void CStack
             
              ::mypush(const T& element)//入栈 { if (m_queue1.size() > 0) { m_queue1.push_back(element); } else if (m_queue2.size() > 0) { m_queue2.push_back(element); } else { m_queue1.push_back(element); }}int main(){ CStack
              
                myStack; myStack.mypush(1); myStack.mypush(2); myStack.mypush(3); myStack.mypop(); myStack.mypush(4); myStack.mypop(); return 0;}