题目
用俩个栈实现一个队列。队列的声明如下，请实现它的俩个函数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，若没有数据就把stack1里面的数据依次搬过来，刚好在stack1最里面的数据，到stack2最上面，删除即可。实现如下图
C++
#include<iostream> #include<stack> using namespace std; template <typename T> class CQueue { public: CQueue(void); ~CQueue(void); void appendTail(const T& node); T deleteHead(); private: stack<T> stack1; stack<T> stack2; }; template<typename T> CQueue<T>::CQueue(void) { } template<typename T> CQueue<T>::~CQueue(void) { } template <typename T> void CQueue<T>::appendTail(const T& node) { stack1.push(node); } template <typename T> T CQueue<T>::deleteHead() { if (stack2.empty() == true) { while (stack1.empty() != true) { stack2.push(stack1.top()); stack1.pop(); } } if (stack2.empty() == true) { cout << "queue is empty!" << endl; exit(EXIT_FAILURE); } T head = stack2.top(); stack2.pop(); return head; } int main() { CQueue<int> c; //入队 c.appendTail(2); c.appendTail(3); c.appendTail(5); //出队 cout << c.deleteHead() << endl; cout << c.deleteHead() << endl; cout << c.deleteHead() << endl; cout << c.deleteHead() << endl; return 0; }
扩展题
用俩个队列实现一个栈。
分析
按照上面的思想，我们还是可以将queue1作为新来数据的存放点。每次进行输出，都将queue1中的数据除了最后一个都移动到queue2中，然后把唯一一个queue1中的数据保存起来，最后用于函数返回，再把所有queue2中的数据搬回queue1中即可。
下图为5、6、7已经进入queue1的队列的删除过程。
#include<iostream> #include<queue> using namespace std; template <typename T> class CStack { public: CStack(void); ~CStack(void); void appendelem(const T& node); T deleteelem(); private: queue<T> queue1; queue<T> queue2; }; template<typename T> CStack<T>::CStack(void) { } template<typename T> CStack<T>::~CStack(void) { } template<typename T> void CStack<T>::appendelem(const T& node) { queue1.push(node); } template<typename T> T CStack<T>::deleteelem() { if (queue1.empty() == true) { cout << "stack is empty!" << endl; exit(EXIT_FAILURE); } int size = queue1.size(); while (size > 1) { queue2.push(queue1.front()); queue1.pop(); size--; } T tmp = queue1.front(); queue1.pop(); size = queue2.size(); while (size > 0) { queue1.push(queue2.front()); queue2.pop(); size--; } return tmp; } int main() { CStack<int> c; //入栈 c.appendelem(3); c.appendelem(4); c.appendelem(5); //出栈 cout << c.deleteelem() << endl; cout << c.deleteelem() << endl; cout << c.deleteelem() << endl; cout << c.deleteelem() << endl; return 0; }
本章完！
