使用两个队列实现栈

栈是先进后出，队列先进先出，问题在于如何在队列中找到最后一个进队列的元素。好在有两个队列。从一个队列往另外一个队列里面转移数据，转移到剩余一个的时候，就弹出该元素。压入栈比较简单，向正在使用的队列里面插入一个元素就可以了。

入栈的时间复杂度和普通的栈一致O(1)，但是出栈就是要把装有数据的队列操作一遍，复杂度是O(n)，其中n是队列中元素的个数。

下面是C#实现代码：

public class StackWith2Queues<T>
{
	private Queue<T> curQueue;
	private Queue<T> otherQueue;

	public StackWith2Queues()
	{
		curQueue = new Queue<T>();
		otherQueue = new Queue<T>();
	}

	public int Count { get; private set; }

	public bool Empty { get { return Count == 0; } }

	public void Push(T item)
	{
		curQueue.Enqueue(item);
		Count++;
	}

	public T Peek()
	{
		if (Empty)
		{
			throw new InvalidOperationException();
		}
		else
		{
			while (curQueue.Count > 1)
			{
				otherQueue.Enqueue(curQueue.Dequeue());
			}

			T result = curQueue.Dequeue();
			otherQueue.Enqueue(result);
			SwapQueue();
			return result;
		}
	}

	public T Pop()
	{
		if (Empty)
		{
			throw new InvalidOperationException();
		}
		else
		{
			Count--;
			while (curQueue.Count > 1)
			{
				otherQueue.Enqueue(curQueue.Dequeue());
			}

			T result = curQueue.Dequeue();
			SwapQueue();
			return result;
		}
	}

	private void SwapQueue()
	{
		var tmp = curQueue;
		curQueue = otherQueue;
		otherQueue = tmp;
	}
}