好资源导航 » 文章资讯 » C++ 数据结构实现两个栈实现一个队列

C++ 数据结构实现两个栈实现一个队列

2024-02-27 08:45:04 84

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
usingnamespacestd;
#include
//栈后进先出队列先进先出
template
classQueue
{
public:

/*TPop_back()
{
if(s2.size()<=0)
{
while(s1.size()>0)
{
T&temp=s1.top();
s1.pop();
s2.push(temp);
}
}
if(s2.size()==0)
thrownewexception("queueisempty");

Ttep=s2.top();
s2.pop();
returntep;
}*/

TPop_back()//比上面少一次出栈
{
if(s2.size()<=0)
{
while(s1.size()>1)
{
T&temp=s1.top();
s1.pop();
s2.push(temp);
}
Ttep=s1.top();
s1.pop();
returntep;
}
else{
Ttep=s2.top();
s2.pop();
returntep;
}
}

voidPush_back(constT&value)
{
s1.push(value);
}

boolEmpty()
{
return(s1.empty()&&s2.empty());
}

protected:
stacks1;
stacks2;
};

voidTextQueue()
{
Queueq1;
q1.Push_back(1);
q1.Push_back(2);
q1.Push_back(3);
q1.Push_back(4);

cout<
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

返回顶部
514930285
czq8825@qq.com

C++ 数据结构实现两个栈实现一个队列

热门推荐

随机推荐