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

题目要求：

　　某队列的声明如下：

 

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

 

　　用两个栈实现队列，实现appendTail()和deleteHead()，分别完成在队列尾部插入结点和在队列头部删除结点的功能。

 

 

题目分析：

　　压栈的时候往stack1中压，出栈的时候，如果stack2不为空则，直接出栈stack2，如果stack2空，则把stack1的所有元素依次压入stack2，然后再出栈stack2。举个例子，如下图所示：

 

代码实现：

#include <iostream>
#include <stack>using namespace std;template<class T> 
class CQueue
{
public:CQueue() {}~CQueue() {}void appendTail(const T& node);T deleteHead();
private:stack<T> m_stack1;stack<T> m_stack2;
};
template<class T> 
void CQueue<T>::appendTail(const T& node)
{m_stack1.push(node);
}
template<class T> 
T CQueue<T>::deleteHead()
{if(m_stack2.size()==0){while(m_stack1.size()){T data = m_stack1.top();m_stack1.pop();m_stack2.push(data);}}if(m_stack2.size()==0)throw new exception("queue is empty");T top = m_stack2.top();m_stack2.pop();return top;}
int main(void)
{CQueue<int> queue;queue.appendTail(1);queue.appendTail(2);cout << queue.deleteHead()<<endl;queue.appendTail(3);cout << queue.deleteHead()<<endl;cout << queue.deleteHead()<<endl;return 0;
}