使用兩個棧實現一個隊列

面試題：用兩個棧（Stack）實現一個隊列（Queue）

思路：

1、入隊時，將元素壓入s1。

2、出隊時，判斷s2是否為空，如不為空，則直接彈出頂元素；如為空，則將s1的元素逐個“倒入”s2，把最后一個元素彈出并出隊。

這個思路，避免了反復“倒”棧，僅在需要時才“倒”一次。

具體實現如下：

#include<iostream>
using namespace std;
#include<stack>
#include<string>
#include<assert.h>//assert必須為.h庫文件

template<class T>
class Queue
{
public:
	void Push(const T& x);
	void Pop();
	void PrintQueue();
	bool Empty();
	size_t Size();
	T& Front();
	T& Back();
public:
	stack<T> s1;//棧s1進行入隊
	stack<T> s2;//棧s2進行出隊
};
template<class T>
void Queue<T>::Push(const T& x)
{
	s1.push(x);//s1棧入隊
}
template<class T>
void Queue<T>::Pop()
{
  if (s1.empty() && s2.empty())//兩個隊列為空
  {
   	return;
  }
	if (!s2.empty())//s2棧非空元素出棧
	{
		s2.pop();
	}
	else
	{
		while (!s1.empty()) //s2棧為空，s1中所有元素導入s2中進行s2的出棧，s1進行pop()
		{
			s2.push(s1.top());
			s1.pop();
		}
		s2.pop();//pop掉s2的棧頂元素
	}
}
template<class T>
void Queue<T>::PrintQueue()
{
	stack<T> sk1 = s1;
	stack<T> sk2 = s2;
	if (s1.empty() && s2.empty())
	{
		cout << "queue is empty!" << endl;
		return;
	}
	while (!sk2.empty())//先輸出sk2中的元素，進行sk2的出棧
	{
		cout << sk2.top() << " ";
		sk2.pop();
	}
	while (!sk1.empty())//再進行sk1中元素導入到sk2中，進行sk1的出棧
	{
		sk2.push(sk1.top());
		sk1.pop();
	}
	while (!sk2.empty())//最后在sk2中輸出sk1中元素，達到隊列出隊的效果
	{
		cout << sk2.top() << " ";
		sk2.pop();
	}
	cout << endl;
}
template<class T>
bool Queue<T>::Empty()//判空
{
	return s1.size() == 0 && s2.size() == 0;
}
template<class T>
size_t Queue<T>::Size()//隊列元素個數
{
	return s1.size() + s2.size();
}
template<class T>
T& Queue<T>::Front()//隊頭
{
	assert(s1.empty() && s2.empty());//斷言隊列是否為空
	if (!s2.empty())//s2不為空，則s2棧頂為隊頭
	{
		return s2.top();
	}
	else//s2為空，則將s1中所有元素導入s2中，新s2棧頂為隊頭
	{
		while (!s1.empty())
		{
			s2.push(s1.top());
			s1.pop();
		}
		return s2.top();
	}
}
template<class T>
T& Queue<T>::Back()//隊尾
{
	assert(!s1.empty() || !s2.empty());//s1和s2中至少有一個不為空
	if (!s1.empty())//s1不為空，則s1棧頂為隊尾
	{
		return s1.top();
	}
	else//s1為空，則將s2中所有元素導入s1中，新s1棧頂為隊尾
	{
		while (!s2.empty())
		{
			s1.push(s2.top());
			s2.pop();
		}
		return s1.top();
	}
}

測試用例如下：

void Test2()
{
	//Queue<int> q1;
	//q1.s1.push(3);
	//q1.s2.push(4);
	//q1.s2.push(5);
	//q1.Push(2);
	//q1.Push(1);
	//q1.PrintQueue();
	////q1.Pop();
	////q1.Pop();
	////q1.Pop();
	////q1.Pop();
	////q1.Pop();
	////q1.Pop();
	////q1.PrintQueue();

	Queue<string> q1;
	q1.s1.push("lllll");
	q1.s2.push("yyyyy");
	q1.s2.push("fffff");
	q1.Push("xxxxx");
	q1.Push("yyyyy");
	q1.PrintQueue();
	cout << "empty: " << q1.Empty() << endl;
	cout << "size: " << q1.Size() << endl;
	cout << "front: " << q1.Front() << endl;
	cout << "back: " << q1.Back() << endl;
}