【数据结构】 两个栈实现一个队列【面试】

前端之家收集整理的这篇文章主要介绍了【数据结构】 两个栈实现一个队列【面试】前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

栈结构:先进后出,后进先出,只允许在栈尾操作。

队列:先进先出,在队尾入队,在队头出队。

要想用两个栈实现一个队列,就需要使用一个相当于中间量的结构进行队列的入队和出队操作。


用图形象化为:

wKiom1cTKdyAGgZmAAAdDuQIW7Q496.png

这样问题就从图中得出了思路:

入队操作:把入队元素一一存入一个栈结构中即可。

出队操作:出队时,先判断另一个栈结构中是否有元素,若有先将元素出栈Pop();若为空,则把栈S1中的元素全部倒入Push()栈S2中,然后让S2栈顶元素出栈Pop(),此时的元素序列和栈S1中刚好相反,即达到出队效果


那么,用代码实现也变得简单:

#include<iostream>
#include<stack>
usingnamespacestd;

classQueue
{
public:
voidPush_Queue(intval)
{
s1.push(val);//实现了入队尾入队操作
cout<<s1.top()<<"";
}

voidPop_Queue()
{
if(s2.empty())
{
while(s1.top())
{
s2.push(s1.top()--);
}
s2.pop();//实现了队头出队操作
}
else
{
s2.pop();
}
}

voidShow()
{
cout<<endl;
//因为使用的是系统库stack,其pop函数返回值为void,所以不能打印出来,我们只打印pop后的队头元素进行验证
cout<<s2.top()<<endl;
}

private:
stack<int>s1;
stack<int>s2;

};

intmain()
{
Queueq;//??构造函数的参数
q.Push_Queue(1);
q.Push_Queue(2);
q.Push_Queue(3);
q.Push_Queue(4);
q.Push_Queue(5);

q.Pop_Queue();

q.Show();//打印pop后的对头元素

system("pause");
return0;
}

如有纰漏,欢迎指正。


本文出自 “Vs吕小布博客,请务必保留此出处http://www.jb51.cc/article/p-cvrhtoms-ms.html

原文链接:https://www.f2er.com/datastructure/382489.html

猜你在找的数据结构相关文章