【面试题7】用两个栈实现队列

栈和队列 操作系统会给每个系统创建一个栈用来存储函数调用时各个函数的参数，返回地址及临时变量等。栈的特点是后进先出，即最后被压入（push）栈的元素会被第一个弹出（pop）。

题目： 用两个栈实现一个队列。 队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队尾部插入结点和在队头部删除结点的功能。

队列声明：

template <typename T> class Cqueue { public: Cqueue(void); ~CQueue(void); void appendTail(const T& node); T deleteHead(); private: stack<T> stack1; stack<T> stack2; }

上述声明中可以看出，一个队列中包含了两个栈stack1和stack2,操作这两个“先进后出”的栈实现一个“先进先出”的队列Cqueue。 代码如下:

template<typename T>void CQueue<T>::appendTail(const T& element) { stack1.push(element); } template<typename T>T CQueue<T>::deleteHead() { if(stack2.size()<=0) { while(stack1.size()>0) { T& data=stack1.top(); stack1.pop(); stack2.push(data); } } if(stack2.size()==0) throw new exception("queue is empty"); T head=stack2.top(); stack2.pop(); return head; }