面試題：用兩個(gè)棧（Stack）實(shí)現(xiàn)一個(gè)隊(duì)列（Queue）

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),隴川企業(yè)網(wǎng)站建設(shè),隴川品牌網(wǎng)站建設(shè),網(wǎng)站定制,隴川網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,隴川網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

思路：

1、入隊(duì)時(shí)，將元素壓入s1。

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

這個(gè)思路，避免了反復(fù)“倒”棧，僅在需要時(shí)才“倒”一次。

具體實(shí)現(xiàn)如下：

#include
using namespace std;
#include
#include
#include//assert必須為.h庫(kù)文件

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

測(cè)試用例如下：

void Test2()
{
	//Queue 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 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;
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站欄目：使用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列-創(chuàng)新互聯(lián)
分享URL：http://weahome.cn/article/cegjdd.html