前言：

經(jīng)歷了list三個自定義類型的洗禮，來個簡單的放松放松，即棧和隊列：

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

1 Stack

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

我們在C語言階段使用的是一個整型指針，一個size一個capacity來實現(xiàn)，如果我們在C++仍然這樣實現(xiàn)就不用介紹了，沒意思了就。

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

因為我們有了vector list基礎(chǔ)，完全可以復(fù)用的，為什么復(fù)用vector list，就和deque有關(guān)了。

1.1 雙端隊列

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

因為這個結(jié)構(gòu)集成了vector和list，但是不是只集成了它們的優(yōu)點。

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

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

所以惠普的大佬就尋思再來一個結(jié)構(gòu)，可以當(dāng)vector用也可以當(dāng)list使用，這里因為是了解，所以就直接給結(jié)構(gòu)了:

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

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

這里使用的是中控指針，即再開一塊空間，這塊空間里面只有指針，指針指向不同的空間，但是指針是從中間開始存儲的，因為涉及到頭插。

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

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

所以別看deque集成了list vector，缺點也蠻多的。

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

這也是為什么，stack queue的模板參數(shù)默認是deque，這個"大哥"雖然有點缺點，但是用起來也算不錯。

我們在stack實現(xiàn)的接口有入棧 出棧 size empty 返回棧頂元素，只有5個接口，這5個接口在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;
	};
 
}

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

測試代碼如下：

#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

隊列這里還有點不一樣，棧可以用vector也可以用list，但是隊列不行，隊列的出隊，相當(dāng)于是頭刪，如果非要用vector里面的erase來頭刪也可以，但是效率很差，是O(N)，這里就非常不推薦，所以隊列就用list來實現(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++模擬實現(xiàn)stack和Queue的操作示例的詳細內(nèi)容，更多關(guān)于C++實現(xiàn)stack和Queue的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論