两个栈实现一个队。
思路:
入队:
只将栈s1作为入队。
出队:
将栈s2作为出队,如果栈s1不为空,s2为空,出队时将s1的元素倒入s2中,再pop();
否则s2不为空,出队时直接在栈s2中pop();
#include<iostream>#include<stack>#include<assert.h>usingnamespacestd;template<classT>classQueue{public:Queue():_size(0){}voidappendTail(Tnum){s1.push(num);_size++;}voiddeleteHead(){assert(_size>0);if(s2.empty()){while(s1.size()!=1){s2.push(s1.top());s1.pop();}s1.pop();}else{s2.pop();}_size--;}T&top(){assert(_size>0);if(s2.empty()){while(s1.size()!=1){s2.push(s1.top());}returns1.top();}else{returns2.top();}}private:stack<T>s1;stack<T>s2;int_size;};intmain(){Queue<int>q;q.appendTail(1);q.appendTail(2);q.appendTail(3);q.appendTail(4);q.deleteHead();q.deleteHead();q.deleteHead();q.deleteHead();q.appendTail(5);cout<<q.top()<<endl;system("pause");return0;}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。