使用两个队列实现一个栈

两个队列实现一个栈

队列是先进先出，而栈是先进后出；考虑到我们取栈顶元素的便利性，我们在实现时使得栈顶等于队列头；

由于栈的pop弹出栈顶元素，而队列的pop也是弹出栈顶元素，所以我们需要特别处理的是插入操作。
由于往栈中添加元素相当于往队列头添加元素，因此我们需要在两个队列中进行元素的转移，比较简单的实现是：
1.queue1和queue2在任一时刻至少有一个为空，即如果有元素，所以元素只在同一个队列中。 
2.当有元素需要插入时，将插入的元素插入到空的队列中，并将另一非空队列的元素转移到该队列中，于是插入的元素添加到了队列头中。
（当然，你可以换一种思路，把队列尾与栈顶对应起来，这样子需要特别处理的是pop操作，相比起来，本文的做法更加简便，因为只需要对插入操作特别处理）

代码：

#include<iostream>
#include<queue>
using namespace std;

template <typename T>
class CStack
{
public:
	CStack()
	{}

	~CStack()
	{}

	void Push(const T& data)
	{
		if (queue1.empty())
		{
			queue1.push(data);

			while (!queue2.empty())
			{
				queue1.push(queue2.front());
				queue2.pop();
			}
		}
		else
		{
			queue2.push(data);

			while (!queue1.empty())
			{
				queue2.push(queue1.front());
				queue1.pop();
			}	
		}
	}

	T Pop()
	{
		T _data = 0;
		if (queue1.empty() && queue2.empty())
		{
			return -1;
		}
		else if (!queue1.empty())
		{
			_data = queue1.front();
			queue1.pop();
		}
		else
		{
			_data = queue2.front();
			queue2.pop();
		}
		return _data;
	}


	private:
		queue<T> queue1;
		queue<T> queue2;

};

int main()
{
	CStack<int> stac;
	stac.Push(1);
	stac.Push(2);
	stac.Push(3);
	stac.Push(4);
	stac.Push(5);


	cout << stac.Pop() << endl;
	cout << stac.Pop() << endl;
	cout << stac.Pop() << endl;
	cout << stac.Pop() << endl;
	cout << stac.Pop() << endl;
	return 0;
}