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

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

上篇文章写了用两个栈实现一个队列,这篇文章实现用两个队列实现一个栈,其实两者的思想都是差不多的。

下边继续画图说明:


下边给出实现代码

#include<queue>
template<typename T>
class Stack
{
public:
	void Push(const T& x)
	{
		//q1,q2都为空,push进q1
		if (_q1.empty()&&_q2.empty())
		{
			_q1.push(x);
		}
		else if (!_q1.empty())//q1不空就push进q1
		{
			_q1.push(x);
		}
		//q1空,q2不空(直接放入q1,这样pop的话可能更方便一些),要是之后还需要push就不方便了
		else//q2不空,push进q2
		{
			_q2.push(x);
		}
	}
	T Pop()
	{
		if (_q1. empty() && _q2.empty())
		{
			exit(EXIT_FAILURE);
		}
		if (!_q1.empty())
		{
			while (_q1.size() != 1)
			{
				T tmp = _q1.front();
				_q1.pop();
				_q2.push(tmp);
			}
			T  ret = _q1.front();
			_q1.pop();
			return ret;
		}
		if (!_q2.empty())
		{
			while (_q2.size() != 1)
			{
				T tmp = _q2.front();
				_q2.pop();
				_q1.push(tmp);
			}
			T  ret = _q2.front();
			_q2.pop();
			return ret;
		}
		
	}
private:
	queue<T> _q1;
	queue<T> _q2;
};
void test()
{
	Stack<int> s;
	s.Push(1);
	s.Push(4);
	s.Push(5);
	s.Push(6);
	s.Push(7);
	cout << s.Pop() << endl;
	cout << s.Pop() << endl;
	cout << s.Pop() << endl;
	cout << s.Pop() << endl;
	cout << s.Pop() << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}


通过上边的代码,我们可以看出,这段代码实现方法图片里的方法2,即就是,每次push进不空的队列,pop时

将空队列当做辅助队来实现,这样的方法图片中给出的方法1更有效一些。

上边程序的输出结果 7 6 5 4 1(两个 数字之间回车隔开),这样实现了先进后出。

对于图片中的方法1,这里就不给出代码了,有兴趣可以自己实现。~~~

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

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