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

栈结构：先进后出，后进先出，只允许在栈尾操作。

队列：先进先出，在队尾入队，在队头出队。

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

用图形象化为：

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

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

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

那么，用代码实现也变得简单：

#include?<iostream>
#include?<stack>
using?namespace?std;

class?Queue
{
public:
????void?Push_Queue(int?val)
????{
????????s1.push(val);???//?实现了入队尾入队操作
????????cout?<<s1.top()?<<?"?";
????}

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

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

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

};

int?main()
{
????Queue?q;??//?？？构造函数的参数
????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");
????return?0;
}

如有纰漏，欢迎指正。

（编辑：ASP站长网）