使用两个栈实现一个队列
面试题:用两个栈(Stack)实现一个队列(Queue)
思路:
1、入队时,将元素压入s1。
2、出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
这个思路,避免了反复“倒”栈,仅在需要时才“倒”一次。
具体实现如下:
#include<iostream>usingnamespacestd;#include<stack>#include<string>#include<assert.h>//assert必须为.h库文件template<classT>classQueue{public:voidPush(constT&x);voidPop();voidPrintQueue();boolEmpty();size_tSize();T&Front();T&Back();public:stack<T>s1;//栈s1进行入队stack<T>s2;//栈s2进行出队};template<classT>voidQueue<T>::Push(constT&x){s1.push(x);//s1栈入队}template<classT>voidQueue<T>::Pop(){if(s1.empty()&&s2.empty())//两个队列为空{return;}if(!s2.empty())//s2栈非空元素出栈{s2.pop();}else{while(!s1.empty())//s2栈为空,s1中所有元素导入s2中进行s2的出栈,s1进行pop(){s2.push(s1.top());s1.pop();}s2.pop();//pop掉s2的栈顶元素}}template<classT>voidQueue<T>::PrintQueue(){stack<T>sk1=s1;stack<T>sk2=s2;if(s1.empty()&&s2.empty()){cout<<"queueisempty!"<<endl;return;}while(!sk2.empty())//先输出sk2中的元素,进行sk2的出栈{cout<<sk2.top()<<"";sk2.pop();}while(!sk1.empty())//再进行sk1中元素导入到sk2中,进行sk1的出栈{sk2.push(sk1.top());sk1.pop();}while(!sk2.empty())//最后在sk2中输出sk1中元素,达到队列出队的效果{cout<<sk2.top()<<"";sk2.pop();}cout<<endl;}template<classT>boolQueue<T>::Empty()//判空{returns1.size()==0&&s2.size()==0;}template<classT>size_tQueue<T>::Size()//队列元素个数{returns1.size()+s2.size();}template<classT>T&Queue<T>::Front()//队头{assert(s1.empty()&&s2.empty());//断言队列是否为空if(!s2.empty())//s2不为空,则s2栈顶为队头{returns2.top();}else//s2为空,则将s1中所有元素导入s2中,新s2栈顶为队头{while(!s1.empty()){s2.push(s1.top());s1.pop();}returns2.top();}}template<classT>T&Queue<T>::Back()//队尾{assert(!s1.empty()||!s2.empty());//s1和s2中至少有一个不为空if(!s1.empty())//s1不为空,则s1栈顶为队尾{returns1.top();}else//s1为空,则将s2中所有元素导入s1中,新s1栈顶为队尾{while(!s2.empty()){s1.push(s2.top());s2.pop();}returns1.top();}}
测试用例如下:
voidTest2(){//Queue<int>q1;//q1.s1.push(3);//q1.s2.push(4);//q1.s2.push(5);//q1.Push(2);//q1.Push(1);//q1.PrintQueue();////q1.Pop();////q1.Pop();////q1.Pop();////q1.Pop();////q1.Pop();////q1.Pop();////q1.PrintQueue();Queue<string>q1;q1.s1.push("lllll");q1.s2.push("yyyyy");q1.s2.push("fffff");q1.Push("xxxxx");q1.Push("yyyyy");q1.PrintQueue();cout<<"empty:"<<q1.Empty()<<endl;cout<<"size:"<<q1.Size()<<endl;cout<<"front:"<<q1.Front()<<endl;cout<<"back:"<<q1.Back()<<endl;}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。