C++ 数据结构实现两个栈实现一个队列
C++ 数据结构实现两个栈实现一个队列
栈为后进先出,队列为先进先出
用两个栈实现一个队列。是一个比较经典的问题。
看到这个问题,我的第一个解题思路为:
定义两个栈,s1,s2。s1作为入队列栈,s2作为出队列栈;
入队列:每次入队列的时候,将数值压入s1栈中;
出队列:出队列时,将s1中的所有数据,压进s2栈中,然后删除s2的栈顶数据,然后再将s2中的剩余数据压入s1中。
在这其中s1是一个存储空间,s2是一个辅助空间。
进一步想一下上述办法,在出队列时,每一次都要将s1倒进s2,然后删除s2栈顶后又将s2的数据倒入s1;有另一个思路可以减少倒的次数;
入队列时:将数据压进s1;
出队列时:判断如果s2为空,那么将s1中的数据,压进s2中,然后删除s2栈顶,如果s2不为空那么再删除s2的栈顶即可;
并且还可以优化,优化如下:
出队列时,判断如果s2为空,那么将s1中n-1个数据,压进s2中,然后删除s1中的栈顶,如果s2不为空那么直接删除s2的栈顶即可;
优化版的c++实现如下:
#include<iostream> using namespace std; #include<stack> //栈 后进先出 队列 先进先出 template<class T> class Queue { public: /*T Pop_back() { if (s2.size() <= 0) { while(s1.size() > 0) { T& temp = s1.top(); s1.pop(); s2.push(temp); } } if (s2.size() == 0) throw new exception("queue is empty "); T tep = s2.top(); s2.pop(); return tep; }*/ T Pop_back() //比上面少一次出栈 { if (s2.size() <= 0) { while (s1.size() > 1) { T& temp = s1.top(); s1.pop(); s2.push(temp); } T tep = s1.top(); s1.pop(); return tep; } else{ T tep = s2.top(); s2.pop(); return tep; } } void Push_back(const T& value) { s1.push(value); } bool Empty() { return (s1.empty() && s2.empty()); } protected: stack<T> s1; stack<T> s2; }; void TextQueue() { Queue<int> q1; q1.Push_back(1); q1.Push_back(2); q1.Push_back(3); q1.Push_back(4); cout << q1.Pop_back() << endl; cout << q1.Pop_back() << endl; cout << q1.Pop_back() << endl; cout << q1.Pop_back() << endl; }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关文章
- 队列的特性很简答,就是先进先出,一般利用数组来实现,本文就介绍了C#队列的简单使用,文中根据实例编码详细介绍的十分详尽,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-17
- 这篇文章主要介绍了SpringBoot集成Redis实现消息队列的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-10
- 这篇文章主要介绍了JavaScript 栈的详解及实例代码的相关资料,需要的朋友可以参考下...2017-01-26
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
C#使用RabbitMq队列(Sample,Work,Fanout,Direct等模式的简单使用)
这篇文章主要介绍了C#使用RabbitMq队列(Sample,Work,Fanout,Direct等模式的简单使用),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-12-08- 这篇文章主要介绍了Nodejs 数组的队列以及forEach的应用详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-25
asp.net通过消息队列处理高并发请求(以抢小米手机为例)
这篇文章主要介绍了asp.net通过消息队列处理高并发请求(以抢小米手机为例),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-09-22- 这篇文章主要介绍了C#队列Queue用法,实例分析了队列的功能、定义及相关使用技巧,需要的朋友可以参考下...2020-06-25
- 本篇文章小编为大家介绍,基于条件变量的消息队列 说明介绍。需要的朋友参考一下...2020-04-25
- 这篇文章主要介绍了c语言尾队列tailq使用示例,大家参考使用吧...2020-04-25
- 这篇文章主要介绍了C++循环队列实现模型,较为详细的分析了循环队列算法的原理与实现方法,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-04-25
- 本篇文章是对消息队列的应用进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了C#队列Queue多线程用法,实例分析了队列的相关使用技巧,需要的朋友可以参考下...2020-06-25
- 在生活中很多时候都会用到延迟队列,本文基于Redis延迟队列的实现代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-05-13
- 在本篇文章里小编给大家整理的是一篇关于php双向队列如何理解的相关内容及实例,需要的朋友们可以跟着学习下。...2021-11-05
- 这篇文章主要介绍了Vue页面堆栈管理器...2021-10-23
Node.js + Redis Sorted Set实现任务队列
本文给大家分享的是使用Node.js + Redis Sorted Set实现任务队列的方法示例,非常的实用,有需要的小伙伴可以参考下...2016-10-03- 这篇文章主要给大家详细介绍了c++如何实现堆栈及创建对象,文中先进行了简单的介绍,而后给出了详细的示例代码及注释,相信对大家的理解和学习很有帮助,有需要的朋友们下面跟着小编一起来学习学习吧。...2020-04-25
- 这篇文章主要介绍了C#多线程处理多个队列数据的方法,涉及C#线程与队列的相关操作技巧,需要的朋友可以参考下...2020-06-25
- 队列的特点是节点的排队次序和出队次序按入队时间先后确定,即先入队者先出队,后入队者后出队,这篇文章主要给大家介绍了关于java固定大小队列的几种实现方式,需要的朋友可以参考下...2021-07-15