用两个栈实现一个队列,并实现两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。
创新互联是一家集网站建设,溆浦企业网站建设,溆浦品牌网站建设,网站定制,溆浦网站建设报价,网络营销,网络优化,溆浦网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。栈的特点是“先进后出,后进先出”,而队列的特点是“先进先出,后进后出”,因此可以想到只用一个栈是无法完成的,所以会需要两个栈,先将输入的数据都依次放入一个栈stack1中,但是先进去的数据会被压在栈底,而栈底的数据是需要最先被取出的,可画图如下:
当要完成在队列头部删除结点这就要用到另外一个栈stack2了,可以将第一个栈stack1的栈顶元素依次取出放进另外的栈stack2中,这样stack1中的栈底元素就变成了stack2中的栈顶元素,当需要删除队列头部结点的时候就可以pop出stack2的栈顶元素;
而需要在队列尾部插入结点就往stack1中压入数据:
也就是相当于,当stack2不为空的时候,要删除队列头部的结点就从stack2的栈顶中取出数据,如果stack2为空的时候就将stack1中的数据全部都从栈顶取出依次放入stack2中,然后再取出stack2的栈顶元素;而要在队列尾部插入结点的时候就直接往stack1里面push数据,这并不影响删除队列首部的结点,因为每次push数据都往stack1里面放,而当stack2不为空的时候从stack2中pop数据,二者并不影响;
程序如下:
#include <iostream> #include <vector> using namespace std; template <class T> class Queue { private: vector<T> _stack1; //定义队列的成员变量直接使用库类vector vector<T> _stack2; public: Queue() //直接用类的默认构造函数,这里会自动调用库vector中的构造函数创建两个栈 {} //当需要向队列尾部放数据的时候,直接在栈1中push数据就可以了 void appendTail(T data) { _stack1.push_back(data); } //当要删除队列头部的数据的时候 void deleteHead() { //先要判断栈2中是否有数据,如果有就直接取出栈顶的元素,此时就为队首的数据 if(!_stack2.empty()) { _stack2.pop_back(); } else//若栈2为空,则需要将栈1中的数据调换到栈2中,以保证先进栈1的数据放在栈2的顶部 { while(!_stack1.empty()) { _stack2.push_back(_stack1.back()); _stack1.pop_back(); } if(!_stack2.empty()) _stack2.pop_back(); else { cout<<"the queue is empty..."<<endl; return; } } cout<<"the new head is "<<_stack2.back()<<endl; } //为了观察方便,这里定义一个打印队列的函数,这个函数其实也就是在完成两个栈实现队列的过程 void print_queue() { //这里要注意的是不能直接使用对象的成员变量stack1和stack2,因为这样会更改对象的数据,而 //我们只是需要打印数据并不希望更改它,因此可以使用vector库中的拷贝构造函数再构造出 //两个临时栈 vector<T> tmp1(_stack1); vector<T> tmp2(_stack2); cout<<"head "; if(tmp2.empty())//当栈2为空的时候需要将栈1的数据挪到栈2再取出 { while(!tmp1.empty()) { tmp2.push_back(tmp1.back()); tmp1.pop_back(); } while(!tmp2.empty()) { cout<<tmp2.back()<<" "; tmp2.pop_back(); } } else { //当栈2不为空的时候先取出栈2的数据,然后再将栈1的数据放入栈2再取出 while(!tmp2.empty()) { cout<<tmp2.back()<<" "; tmp2.pop_back(); if(tmp2.empty()) { while(!tmp1.empty()) { tmp2.push_back(tmp1.back()); tmp1.pop_back(); } } } } cout<<"tail"<<endl; } }; int main() { Queue<char> queue; queue.appendTail('a'); queue.appendTail('b'); queue.appendTail('c'); queue.appendTail('d'); queue.appendTail('e'); queue.print_queue(); queue.deleteHead(); queue.deleteHead(); queue.print_queue(); queue.appendTail('f'); queue.appendTail('g'); queue.appendTail('h'); queue.print_queue(); return 0; }
因为上面的队类是模板类,因此实现了代码复用,队中的数据可以为任意类型;
运行程序:
《完》
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
网站标题:用两个栈实现一个队列——7-创新互联
分享地址:https://www.cdcxhl.com/article10/cejdgo.html
成都网站建设公司_创新互联,为您提供外贸网站建设、定制网站、微信小程序、品牌网站建设、手机网站建设、云服务器
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联