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

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

下边继续画图说明：

下边给出实现代码：

#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，这里就不给出代码了，有兴趣可以自己实现。~~~

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!