兩個隊列實現一個棧

在之前我曾經實現了兩個棧實現一個隊列的面試題，其實思路也很簡單就是充分利用棧的特性-後進先出，將輸入的數據先輸入棧1，將該棧1再輸出到棧2，最後將棧2的數據輸出，利用這個交換的特性實現兩個棧實現一個隊列.

那仫如何利用兩個隊列實現一個棧呢？

思路分析篇：

其實思路類似之前的面試題-兩個棧實現一個隊列，也是通過交換的特性：

(1).先將要輸入的數據類似 1->2->3->4->5輸入到隊列1中

(2).在Pop時則需要一點技巧了，因為是模擬實現棧，所以出棧的順序為5->4->3->2->1.如果隊列1不為空則將隊列1的前n-1個數據尾插到隊列2中，隊列1中只剩下最後一個元素n-在上面這種情況下我們將 1 2 3 4從隊列1中刪除尾插到隊列2中，隊列1中只剩下5

(3).如果我們將隊列1剩下的數據刪除掉，則正好滿足出棧順序的第一個元素，此時隊列1為空--如果此時再插入數據(6)，我們只能將該數據尾插到隊列2中(保證出棧順序不被改變);如果我們沒有將隊列1中的最後一個元素n刪除掉，則此時插入數據則將該數據插入到隊列1中，同樣是為了滿足出棧順序.

(4).之前提到隊列1為空，隊列2為1->2->3->4->6，和剛才的想法類似，將隊列2的前n-1個數據尾插到隊列1中，隊列2中只剩下最後一個元素n,將隊列2中的最後一個數據Pop掉就是現在的棧頂元素啦!!!

...以後的步驟類似(4).

下圖是我畫的一個簡單的實現過程:

代碼實現篇：

//兩個隊列實現一個棧
template
class StackBy2Queue
{
public:
	void Push(const T& x)
	{
		if(_queue1.size() > 0)
			//如果隊列1不為空則將數據插入到隊列1中
			_queue1.push(x);
		else if(_queue2.size() > 0)
			//隊列1為空隊列2不為空插入到隊列2中
			_queue2.push(x);
		else
			_queue1.push(x);
	}
	void Pop()
	{
		assert(!_queue1.empty() || !_queue2.empty());
		if(_queue2.empty())
		{
			//隊列2為空時
			while(_queue1.size() > 1)
			{
				//保留隊列1原本的隊尾元素
				_queue2.push(_queue1.front());
				_queue1.pop();
			}
			_queue1.pop();
		}
		else
		{
			//隊列2不為空
			while(_queue2.size() > 1)
			{
				//保留隊列2的隊尾元素
				_queue1.push(_queue2.front());
				_queue2.pop();
			}
			_queue2.pop();
		}
	}
	T& Top()
	{
		if(_queue1.size() > 0)
			return _queue1.back();
		else
			return _queue2.back();
	}
	bool Empty()
	{
		//兩個隊列都為空時才為空
		return (_queue1.empty()) && (_queue2.empty());
	}
	size_t Size()
	{
		return _queue1.size()+_queue2.size();
	}
private:
	queue _queue1;
	queue _queue2;
};

test.cpp

void testStackBy2Queue()
{
	StackBy2Queue<int> sq;
	sq.Push(1);
	sq.Push(2);
	sq.Push(3);
	sq.Push(4);
	sq.Push(5);
	cout<<sq.top()<<endl; 4="" 5="" 6="" pre="">

這只是我個人的一點小小理解，如果有問題希望指出.