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

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

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

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

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

我們先來模擬一下出棧和入棧的情況：

 （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ì)說到）

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

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

#pragma once
#include<iostream>
#include<queue>
#include<string>
#include<assert.h>

using namespace std;

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


private:
	queue<T> q1;
	queue<T> q2;
	size_t _size;
};

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

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

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

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

template<class T>
void MYStack<T>::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<class T>
bool MYStack<T>::Empty()
{
	return _size ? false : true;
}

template<class T>
size_t MYStack<T>::Size()
{
	return _size;
}

template<class T>
void MYStack<T>::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)化方法就是沒有注釋部分。它的實(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元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

當(dāng)前標(biāo)題：使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://chinadenli.net/article48/hjjhp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、營銷型網(wǎng)站建設(shè)、ChatGPT、做網(wǎng)站、域名注冊、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)