两个栈实现队列及两个队列实现栈
分类：数据结构与算法
用两个栈实现队列的push() 和 pop()
;template <class T>class CQueue{public:CQueue() {};~CQueue() {};void appendTail(const T& node);T deleteHead();private:stack<T> stack1;stack<T> stack2;};template <class T>void CQueue<T>::appendTail(const T& node){stack1.push(node);}template <class T>T CQueue<T>::deleteHead(){if (stack2.empty()){while (!stack1.empty()){T& tmp = stack1.top();stack1.pop();stack2.push(tmp);}}if (stack2.empty()){throw runtime_error(” queue is empty”);}T head = stack2.top();stack2.pop();return head;}void Test(int actual, int excepted){if (actual == excepted)cout << “Test passed.\n”;elsecout << “Test failed.\n”;}int main(){ try {CQueue<int> queue;queue.appendTail(1);queue.appendTail(2);queue.appendTail(3);int head = queue.deleteHead();Test(head,1);head = queue.deleteHead();Test(head,2);queue.appendTail(4);head = queue.deleteHead();Test(head,3);queue.appendTail(5);head = queue.deleteHead();Test(head,4);head = queue.deleteHead();Test(head,5); }catch (runtime_error err) {cout << err.what() << endl;}return 0;}
两个队列实现一个栈
进栈就是进队列，出栈 先把元素进一个队列queue1，然后除了队尾元素其余全部进队列queue2， 然后queue1出队列。
;template <typename T>class CStack{public:CStack(void){};~CStack(void){};void push(const T& node);T pop();private:queue<T> queue1;queue<T> queue2;};//插入元素template <typename T> void CStack<T>::push(const T& element){if(queue1.size()>0)//如果queue1不为空则往queue1中插入元素queue1.push(element);else if(queue2.size()>0)//如果queue2不为空则往queue2中插入元素queue2.push(element);else//如果两个队列都为空，则往queue1中插入元素queue1.push(element);}//删除元素template <typename T> T CStack<T>::pop(){if(queue1.size()==0)//如果queue1为空{while(queue2.size()>1)//保证queue2中有一个元素，，将其余元素保存到queue1中{queue1.push(queue2.front());queue2.pop();}T& data=queue2.front();queue2.pop();return data;}else//如果queue2为空{while(queue1.size()>1)//保证queue1中有一个元素，将其余元素保存到queue2中{queue2.push(queue1.front());queue1.pop();}T& data=queue1.front();queue1.pop();return data;}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇重建二叉树下一篇c++ 11 基于范围的for循环
顶0踩0
哪里会顾得上这些。等到时间将矛盾一层层降解为流言是非误解过结
