前言：

經(jīng)歷了list三個(gè)自定義類型的洗禮，來(lái)個(gè)簡(jiǎn)單的放松放松，即棧和隊(duì)列：

文檔記錄的，棧和隊(duì)列是一種容器適配器，它們不屬于stl，但是它們的大體結(jié)構(gòu)我們都是了解的，在數(shù)據(jù)結(jié)構(gòu)初階我們已經(jīng)用了C語(yǔ)言進(jìn)行實(shí)現(xiàn)，這里用C++進(jìn)行實(shí)現(xiàn)。

1 Stack

根據(jù)文檔，stack也是使用了模板，第一個(gè)參數(shù)是數(shù)據(jù)類型，那么第二個(gè)是？

我們?cè)贑語(yǔ)言階段使用的是一個(gè)整型指針，一個(gè)size一個(gè)capacity來(lái)實(shí)現(xiàn)，如果我們?cè)贑++仍然這樣實(shí)現(xiàn)就不用介紹了，沒(méi)意思了就。

后面的參數(shù)deque是另一種結(jié)構(gòu)，叫做雙端隊(duì)列，后面細(xì)說(shuō)，為什么引入第二個(gè)模板參數(shù)呢？

因?yàn)槲覀冇辛藇ector list基礎(chǔ)，完全可以復(fù)用的，為什么復(fù)用vector list，就和deque有關(guān)了。

1.1 雙端隊(duì)列

deque是雙端隊(duì)列，那么為什么在stack queue的模板參數(shù)里面都有這個(gè)結(jié)構(gòu)呢？

因?yàn)檫@個(gè)結(jié)構(gòu)集成了vector和list，但是不是只集成了它們的優(yōu)點(diǎn)。

先簡(jiǎn)單談?wù)刣eque的結(jié)構(gòu)：

list的優(yōu)點(diǎn)是插入刪除效率很高，缺點(diǎn)是不好訪問(wèn)數(shù)據(jù)，vector的優(yōu)點(diǎn)是訪問(wèn)任意數(shù)據(jù)的效率很高，缺點(diǎn)是插入刪除數(shù)據(jù)如果在頭部或者中間的效率很低。

所以惠普的大佬就尋思再來(lái)一個(gè)結(jié)構(gòu)，可以當(dāng)vector用也可以當(dāng)list使用，這里因?yàn)槭橇私猓跃椭苯咏o結(jié)構(gòu)了:

 看起來(lái)就像是個(gè)大 boss，當(dāng)我們存數(shù)據(jù)的時(shí)候，該結(jié)構(gòu)會(huì)開(kāi)一塊空間，比如叫buff，空間大小為16，當(dāng)一直插入數(shù)據(jù)，該數(shù)據(jù)插滿之后，不會(huì)擴(kuò)容，會(huì)重新開(kāi)一塊空間，空間大小也是16，數(shù)據(jù)插好后，我們?cè)撊绾慰焖僭L問(wèn)呢？
假定開(kāi)的空間大小不變，我們想訪問(wèn)第i個(gè)數(shù)據(jù)，一塊空間的大小為N，那么我們就應(yīng)該先找到i數(shù)據(jù)在第幾個(gè)空間的，在找該數(shù)據(jù)在第幾個(gè)，找到在哪個(gè)空間可以i / N，第幾個(gè)可以i % N，這樣就可以快速訪問(wèn)了。

那么這么多空間應(yīng)該如何管理？

這里使用的是中控指針，即再開(kāi)一塊空間，這塊空間里面只有指針，指針指向不同的空間，但是指針是從中間開(kāi)始存儲(chǔ)的，因?yàn)樯婕暗筋^插。

但是對(duì)于deque的結(jié)構(gòu)來(lái)說(shuō)，只有兩個(gè)迭代器，一個(gè)迭代器有4個(gè)指針，分別指向當(dāng)前節(jié)點(diǎn)，頭結(jié)果，尾節(jié)點(diǎn)和中控指針的節(jié)點(diǎn)，如果涉及到了插入刪除數(shù)據(jù)，比如頭插，就要先開(kāi)一塊空間，倒著存數(shù)據(jù)，那么此時(shí)找數(shù)據(jù)，i就要先減去這個(gè)不滿的第一個(gè)數(shù)據(jù)塊的數(shù)據(jù)個(gè)數(shù)，才能通過(guò)/ % 快速訪問(wèn)數(shù)據(jù)。中間插入數(shù)據(jù)的時(shí)候，有兩個(gè)選擇，一是重新開(kāi)空間，二是在原來(lái)的空間上擴(kuò)容，但是擴(kuò)容之后，每個(gè)空間的大小不一樣，找數(shù)據(jù)的效率就會(huì)降低了。

當(dāng)涉及刪除數(shù)據(jù)的時(shí)候，刪除了之后，后面的數(shù)據(jù)往前移動(dòng)，比較麻煩。

所以別看deque集成了list vector，缺點(diǎn)也蠻多的。

比如訪問(wèn)數(shù)據(jù)的效率不極致，中間插入刪除數(shù)據(jù)也沒(méi)list快，它就比較尷尬。。

這也是為什么，stack queue的模板參數(shù)默認(rèn)是deque，這個(gè)"大哥"雖然有點(diǎn)缺點(diǎn)，但是用起來(lái)也算不錯(cuò)。

我們?cè)趕tack實(shí)現(xiàn)的接口有入棧 出棧 size empty 返回棧頂元素，只有5個(gè)接口，這5個(gè)接口在vector里面都有，所以，直接使用：

namespace Free3
{
	template <class T, class container = vector<T>>
	class stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
		T& top()
		{
			return _con.back();
		}
		void pop()
		{
			_con.pop_back();
		}
	private:
		container _con;
	};
 
}

這里有個(gè)很厲害的點(diǎn)就是，模板參數(shù)也可以有缺省值，我們給上vector<int>，那么默認(rèn)的用vector來(lái)實(shí)現(xiàn)stack。

測(cè)試代碼如下：

#include "Stack.h"
using namespace Free3;
int main()
{
	Free3::stack<int, vector<int>> s1;
	Free3::stack<int> s2;
	s1.push(1);
	s1.push(2);
	s1.push(3);
	s1.push(4);	
	s2.push(1);
	s2.push(2);
	s2.push(3);
	s2.push(4);
	s2.push(5);
	while (!s2.empty())
	{
		cout << s2.top() << " ";
		s2.pop();
	}
	cout << endl;
	return 0;
}

2 Queue

隊(duì)列這里還有點(diǎn)不一樣，棧可以用vector也可以用list，但是隊(duì)列不行，隊(duì)列的出隊(duì)，相當(dāng)于是頭刪，如果非要用vector里面的erase來(lái)頭刪也可以，但是效率很差，是O(N)，這里就非常不推薦，所以隊(duì)列就用list來(lái)實(shí)現(xiàn)。

namespace Free4
{
	template<class T>
	class Queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
		}
		size_t size()
		{
			return _con.size();
		}
		T& front()
		{
			return _con.front();
		}
		bool empty()
		{
			return _con.empty();
		}
 
	private:
		list<T> _con;
	};
 
}

以上就是C++模擬實(shí)現(xiàn)stack和Queue的操作示例的詳細(xì)內(nèi)容，更多關(guān)于C++實(shí)現(xiàn)stack和Queue的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論