【100题】第五十七题 用两个栈实现队列

一，题目

某队列的声明如下：

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;
};

二，分析

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

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

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

1）stack1 入队队列 的栈

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

三，参考代码如下：

template<typename T> void CQueue<T>::appendTail(const T& element)//入队 
{
      m_stack1.push(element);
}

template<typename T> void CQueue<T>::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 <iostream>
#include <stack>
#include <assert.h>
using namespace std;

// 两个队列实现一个栈
template<typename T> class CStack
{
public:
    CStack() {}
    ~CStack() {}

    void mypush(const T& element);  

    void mypop();               


private:
    deque <T> m_queue1;
    deque <T> m_queue2;
};

template<typename T> void CStack<T>::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<typename T> void CStack<T>::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<int> myStack;
    myStack.mypush(1);
    myStack.mypush(2);
    myStack.mypush(3);
    myStack.mypop();
    myStack.mypush(4);
    myStack.mypop();

    return 0;
}