C++数据结构怎么样实现两个栈实现一个队列?本文主要为大家介绍C++ 数据结构实现两个栈实现一个队列的相关资料,有兴趣的朋友赶紧来了解一下吧。
C++ 数据结构实现两个栈实现一个队列方法:
堆栈是先进先出,队列是先进先出,队列是用两个堆栈实现的。是一个更经典的问题。看到这个问题,我对这个问题的第一个解决方案是:
定义两个堆栈,s1,s2。 S1用作队列的队列,s2用作队列的队列;
进入队列:每次进入队列时,该值都被推入s1堆栈;
Out队列:当离开队列时,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; }