首先，我們得了解隊(duì)列和棧的基本原理。

成都創(chuàng)新互聯(lián)公司成立與2013年，先為黃山等服務(wù)建站，黃山等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢(xún)服務(wù)。為黃山企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。

 隊(duì)列是一個(gè)“先進(jìn)先出“的一個(gè)結(jié)構(gòu)。隊(duì)列的定義是在隊(duì)尾插入，在隊(duì)頭刪除，這就要求要用一種在尾部插入容易的，在頭部刪除容易的結(jié)構(gòu)，你一定會(huì)想到單鏈表，對(duì)，庫(kù)的實(shí)現(xiàn)就是用一個(gè)鏈表實(shí)現(xiàn)的。

 棧，相信大家都不會(huì)陌生，函數(shù)棧幀等的實(shí)現(xiàn)，它是一種”先進(jìn)后出“的結(jié)構(gòu)。棧的插入刪除都是在尾部進(jìn)行的。

 所以要用隊(duì)列實(shí)現(xiàn)一個(gè)棧，要解決的問(wèn)題就是在刪除時(shí)要?jiǎng)h除最后插入的那個(gè)元素。

我們先來(lái)模擬一下出棧和入棧的情況：

 （1）入棧：Q1：1，2，3，4入隊(duì)列（相當(dāng)于入棧）；

 （2）出棧：Q1：1，2，3出隊(duì)列，Q2：1，2，3入隊(duì)列；（此時(shí)Q1只剩4，正是我們要出棧的元素）

 （3）

   1>入棧：Q1：5入隊(duì)列（每次入棧都用Q1入隊(duì)列實(shí)現(xiàn)，而不入隊(duì)列Q2，這樣會(huì)提高效率，后面會(huì)說(shuō)到）

   2>出棧：判斷：如果Q1隊(duì)列不為空就用（1）（2）步的方法出棧最后一個(gè)元素。否則，出棧Q2隊(duì)列的最后一個(gè)元素。

我們首先來(lái)搭建這個(gè)棧的結(jié)構(gòu)：

#pragma once
#include
#include
#include
#include

using namespace std;

template
class MYStack
{
public:
	MYStack()
		:_size(0)
	{
	}
	~MYStack()
	{
	}
	void Push(const T& x);
	void Pop();
	bool Empty();
	size_t Size();
	void Print();


private:
	queue q1;
	queue q2;
	size_t _size;
};

 一個(gè)棧具有的功能我們都實(shí)現(xiàn)一下，Psh(),Pop(),Empty(),Size()等等。

 在這個(gè)結(jié)構(gòu)中數(shù)據(jù)成員是兩個(gè)隊(duì)列的對(duì)象，因?yàn)槲覀兪怯脙蓚€(gè)隊(duì)列來(lái)實(shí)現(xiàn)的，還有一個(gè)_size用來(lái)記錄棧中元素的個(gè)數(shù)。

下面是函數(shù)具體實(shí)現(xiàn)：

template
void MYStack::Push(const T& x)
{
	q1.push(x);
	++_size;
}

template
void MYStack::Pop()
{
	//assert(_size > 0);
	//size_t plen = q1.size();
	//while (plen != 1)
	//{
	//	T tmp = q1.front();
	//	q2.push(tmp);
	//	q1.pop();
	//	--plen;
	//}
	//q1.pop();
	//plen = q2.size();
	//while (plen)
	//{
	//	T tmp = q2.front();
	//	q1.push(tmp);
	//	q2.pop();
	//	--plen;
	//}
	//--_size;


	assert(_size > 0);
	size_t plen = q1.size();
	if (plen == 0)
	{
		//if (q2.size() == 0)
		//	return;
		plen = q2.size();
		while (plen != 1)
		{
			T tmp = q2.front();
			q1.push(tmp);
			q2.pop();
			--plen;
		}
		q2.pop();
	}
	else
	{
		size_t plen = q1.size();
		while (plen != 1)
		{
			T tmp = q1.front();
			q2.push(tmp);
			q1.pop();
			--plen;
		}
		q1.pop();
	}
	--_size;
}


template
bool MYStack::Empty()
{
	return _size ? false : true;
}

template
size_t MYStack::Size()
{
	return _size;
}

template
void MYStack::Print()
{
	//size_t plen = q1.size();
	//while (plen--)
	//{
	//	cout << q1.front() << " ";
	//	q1.pop();
	//}


	size_t plen = q2.size();
	while (plen--)
	{
		cout << q2.front() << " ";
		q2.pop();
	}
	plen = q1.size();
	while (plen--)
	{
		cout << q1.front() << " ";
		q1.pop();
	}
}

 注釋掉的部分也可以實(shí)現(xiàn)，它的原理是不管第（3）步是出棧還是入棧，都把剩下的元素從Q2出棧入棧到Q1，輸出的時(shí)候只用輸出Q1中的元素。但是它的效率較低。如果有這種情況：1，2，3.....100000入棧，然后1，2，3......100000出棧，這會(huì)導(dǎo)致Q1和Q2頻繁的出棧和入棧，效率非常之低。

 優(yōu)化方法就是沒(méi)有注釋部分。它的實(shí)現(xiàn)就是入棧都是Q1入隊(duì)列，出棧后不把Q2的元素移到Q1，這樣的話效率就會(huì)提高，只是在輸出的時(shí)候要先輸出Q2里的元素，再輸出Q1里的元素。因?yàn)镼1里的元素總是棧頂?shù)脑亍?/p>

另外有需要云服務(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ù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

標(biāo)題名稱(chēng)：使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧-創(chuàng)新互聯(lián)
文章URL：http://weahome.cn/article/hjjhp.html