目錄

一.stack 介紹

?二.stack 使用

三.stack 模擬實(shí)現(xiàn)

普通版本：

適配器版本：

四.queue的介紹

五. queue使用

六.queue模擬實(shí)現(xiàn)

七.deque介紹

1.容器適配器

2.deque的簡(jiǎn)單介紹

3.deque的缺陷

4.為什么選擇deque作為stack和queue的底層默認(rèn)容器

一.stack 介紹

stack------reference

1. stack是一種容器適配器，專門用在具有后進(jìn)先出操作的上下文環(huán)境中，其刪除只能從容器的一端進(jìn)行元素的插入與提取操作。
2. stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對(duì)特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
3. stack的底層容器可以是任何標(biāo)準(zhǔn)的容器類模板或者一些其他特定的容器類，這些容器類應(yīng)該支持以下操作：

• empty：判空操作
• back：獲取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部刪除元素操作

4. 標(biāo)準(zhǔn)容器vector、deque、list均符合這些需求，默認(rèn)情況下，如果沒有為stack指定特定的底層容器，默認(rèn)情況下使用deque。

?二.stack 使用

三.stack 模擬實(shí)現(xiàn)

普通版本：

stack的模擬實(shí)現(xiàn)非常簡(jiǎn)單，我們利用已經(jīng)學(xué)過的vector去封裝他的幾個(gè)接口就可以了。

	template<class T>
	class Stack
	{
	public:
		Stack()
		{}

		const T& top()
		{
			return _v.back();
		}

		void pop()
		{
			return _v.pop_back();
		}

		void push(const T& val)
		{
			_v.push_back(val);
		}

		size_t size()
		{
			return _v.size();
		}

		bool empty()
		{
			return _v.empty();
		}
	private:
		vector<T> _v;
	};
    
    int main()
    {
	    Stack<int> st;
	    st.push(100);
	    st.push(200);
	    st.push(300);
	    st.push(400);

	    while (!st.empty())
	    {
		    cout << st.top()<<" ";
		    st.pop();
	    }
        return 0;
    }

?這里我們使用的是vector做的底層容器，在std::stack中，底層容器是deque并且支持切換成其他容器，這也就是stack被叫做容器適配器的原因。

適配器版本：

容器適配器，我們僅僅需要利用一個(gè)類模板參數(shù)就可以了，一個(gè)類模板參數(shù)就可以控制底層存儲(chǔ)數(shù)據(jù)的容器類型，是vector還是list又或者是deque。

    //容器適配器class Container = vector<T>，class Container = list<T>....
    template<class T ,class Container >
	class Stack
	{
	public:
		Stack()
		{}

		const T& top()
		{
			return _v.back();
		}

		void pop()
		{
			return _v.pop_back();
		}

		void push(const T& val)
		{
			_v.push_back(val);
		}

		size_t size()
		{
			return _v.size();
		}

		bool empty()
		{
			return _v.empty();
		}
	private:
		Container _v;
	};

    int main()
    {
	    Stack<int,list<int>> st;
	    st.push(100);
	    st.push(200);
	    st.push(300);
	    st.push(400);

	    while (!st.empty())
	    {
		    cout << st.top()<<" ";
		    st.pop();
	    }
        return 0;
    }

在類模板的哪里也是可以給缺省參數(shù)，就可以實(shí)現(xiàn)默認(rèn)存儲(chǔ)容器。

template<class T ,class Container = deque<T>>

四.queue的介紹

queue-----reference

1. 隊(duì)列是一種容器適配器，專門用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素。
2. 隊(duì)列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從隊(duì)尾入隊(duì)列，從隊(duì)頭出隊(duì)列。
3. 底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門設(shè)計(jì)的容器類。該底層容器應(yīng)至少支持以下操作:

• empty：檢測(cè)隊(duì)列是否為空
• size：返回隊(duì)列中有效元素的個(gè)數(shù)
• front：返回隊(duì)頭元素的引用
• back：返回隊(duì)尾元素的引用
• push_back：在隊(duì)列尾部入隊(duì)列
• pop_front：在隊(duì)列頭部出隊(duì)列

4. 標(biāo)準(zhǔn)容器類deque和list滿足了這些要求。默認(rèn)情況下，如果沒有為queue實(shí)例化指定容器類，則使用標(biāo)準(zhǔn)容器deque。?

五. queue使用

六.queue模擬實(shí)現(xiàn)

因?yàn)閝ueue的接口中存在頭刪和尾插，因此使用vector來封裝效率太低，故可以借助list來模擬實(shí)現(xiàn)queue，具體如下：

普通list版本：

    template<class T>
	class Queue
	{
	public:
		Queue()
		{
		}

		void push(const T& val)
		{
			_q.push_back(val);
		}

		void pop()
		{
			_q.pop_front();
		}

		const T& front()
		{
			return _q.front();
		}

		const T& back()
		{
			return _q.back();
		}

		size_t size()
		{
			return _q.size();
		}

		bool empty()
		{
			return _q.empty();
		}

	private:
		list<T> _q;
	};

適配器版本：

    template<class T,class Container=list<T>>
	class Queue
	{
	public:
		Queue()
		{
		}

		void push(const T& val)
		{
			_q.push_back(val);
		}

		void pop()
		{
			_q.pop_front();
		}

		const T& front()
		{
			return _q.front();
		}

		const T& back()
		{
			return _q.back();
		}

		size_t size()
		{
			return _q.size();
		}

		bool empty()
		{
			return _q.empty();
		}

	private:
		Container _q;
	};

?七.deque介紹

1.容器適配器

適配器是一種設(shè)計(jì)模式(設(shè)計(jì)模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié))，該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口。

STL標(biāo)準(zhǔn)庫(kù)中stack和queue的底層結(jié)構(gòu) ：

雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因?yàn)閟tack和隊(duì)列只是對(duì)其他容器的接口進(jìn)行了包裝，STL中stack和queue默認(rèn)使用deque，比如：

2.deque的簡(jiǎn)單介紹

deque(雙端隊(duì)列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。

?同時(shí)從庫(kù)中提供的接口來看，deque還提供了下標(biāo)的隨機(jī)訪問的功能，但是deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實(shí)際deque類似于一個(gè)動(dòng)態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：

?雙端隊(duì)列底層是一段假象的連續(xù)空間，實(shí)際是分段連續(xù)的，為了維護(hù)其“整體連續(xù)”以及隨機(jī)訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設(shè)計(jì)就比較復(fù)雜，如下圖所示：

? 3.deque的缺陷

與vector比較，deque的優(yōu)勢(shì)是：頭部插入和刪除時(shí)，不需要搬移元素，效率特別高，而且在擴(kuò)容時(shí)，也不需要搬移大量的元素，因此其效率是比vector高的。與list比較，其底層是連續(xù)空間，空間利用率比較高，不需要存儲(chǔ)額外字段。
但是，deque有一個(gè)致命缺陷：不適合遍歷，因?yàn)樵诒闅v時(shí)，deque的迭代器要頻繁的去檢測(cè)其是否移動(dòng)到某段小空間的邊界，導(dǎo)致效率低下，而序列式場(chǎng)景中，可能需要經(jīng)常遍歷，因此在實(shí)際中，需要線性結(jié)構(gòu)時(shí)，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看到的一個(gè)應(yīng)用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。

4.為什么選擇deque作為stack和queue的底層默認(rèn)容器

stack是一種后進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，因此只要具有push_back()和pop_back()操作的線性結(jié)構(gòu)，都可以作為stack的底層容器，比如vector和list都可以；queue是先進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，只要具有push_back和pop_front操作的線性結(jié)構(gòu)，都可以作為queue的底層容器，比如list。但是STL中對(duì)stack和queue默認(rèn)選擇deque作為其底層容器，主要是因?yàn)椋?mark hidden color="red">文章來源：http://www.zghlxwxcb.cn/news/detail-655466.html

1. ?stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進(jìn)行操作。
2. 在stack中元素增長(zhǎng)時(shí)，deque比vector的效率高(擴(kuò)容時(shí)不需要搬移大量數(shù)據(jù))；queue中的元素增長(zhǎng)時(shí)，deque不僅效率高，而且內(nèi)存使用率高。

結(jié)合了deque的優(yōu)點(diǎn)，而完美的避開了其缺陷。文章來源地址http://www.zghlxwxcb.cn/news/detail-655466.html

到了這里，關(guān)于C++ STL stack & queue的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！