=========================================================================

個(gè)人主頁(yè)點(diǎn)擊直達(dá)：小白不是程序媛

C++系列學(xué)習(xí)專(zhuān)欄：C++干貨鋪

代碼倉(cāng)庫(kù)：Gitee

=========================================================================

目錄

stack的介紹和使用

stack的介紹

stack的使用

queue的介紹和使用

queue的介紹

queue的使用

容器適配器

什么是適配器

STL中stack和queue的底層結(jié)構(gòu)

deque的介紹

deque的缺陷

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

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

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

stack的介紹和使用

stack的介紹

1. stack是一種容器適配器，專(zhuān)門(mén)用在具有后進(jìn)先出操作的上下文環(huán)境中，其刪除只能從容器的一端進(jìn)行元素的插入與提取操作。

2. stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對(duì)特定類(lèi)封裝作為其底層的容器，并提供一組特定的成員函數(shù)來(lái)訪(fǎng)問(wèn)其元素，將特定類(lèi)作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。

3. stack的底層容器可以是任何標(biāo)準(zhǔn)的容器類(lèi)模板或者一些其他特定的容器類(lèi)，這些容器類(lèi)應(yīng)該支持以下操作：

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

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

?

stack的使用

stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	cout << st.size() << endl;
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}

?

queue的介紹和使用

queue的介紹

?

1. 隊(duì)列是一種容器適配器，專(zhuān)門(mén)用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素。

2. 隊(duì)列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定容器類(lèi)封裝作為其底層容器類(lèi)，queue提供一組特定的成員函數(shù)來(lái)訪(fǎng)問(wèn)其元素。元素從隊(duì)尾入隊(duì)列，從隊(duì)頭出隊(duì)列。

3. 底層容器可以是標(biāo)準(zhǔn)容器類(lèi)模板之一，也可以是其他專(zhuān)門(mén)設(shè)計(jì)的容器類(lèi)。該底層容器應(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)容器類(lèi)deque和list滿(mǎn)足了這些要求。默認(rèn)情況下，如果沒(méi)有為queue實(shí)例化指定容器類(lèi)，則使用標(biāo)準(zhǔn)容器deque。?

queue的使用

	queue<int> qu;
	qu.push(1);
	qu.push(2);
	qu.push(3);
	qu.push(4);
	qu.push(5);
	cout << qu.size() << endl;
	while (!qu.empty())
	{
		cout << qu.front() << " ";
		qu.pop();
	}

?

容器適配器

什么是適配器

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

STL中stack和queue的底層結(jié)構(gòu)

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

deque的介紹

deque(雙端隊(duì)列)：是一種雙開(kāi)口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開(kāi)口的含義是：

可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。?

deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實(shí)際deque類(lèi)似于一個(gè)動(dòng)態(tài)的二維數(shù)組，?其底層結(jié)構(gòu)如下圖所示：

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

?

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í)際中，需要線(xiàn)性結(jié)構(gòu)時(shí)，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看到的一個(gè)應(yīng)用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。

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

stack是一種后進(jìn)先出的特殊線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，因此只要具有push_back()和pop_back()操作的線(xiàn)性結(jié)構(gòu)，都可以作為stack的底層容器，比如vector和list都可以；queue是先進(jìn)先出的特殊線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，只要具有push_back和pop_front操作的線(xiàn)性結(jié)構(gòu)，都可以作為queue的底層容器，比如list。但是STL中對(duì)stack和queue默認(rèn)選擇deque作為其底層容器，主要是因?yàn)椋?/p>

1. stack和queue不需要遍歷(因此stack和queue沒(méi)有迭代器)，只需要在固定的一端或者兩端進(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)，而完美的避開(kāi)了其缺陷。

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

template<class T, class Container=deque<T>>
	class Stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		T& top()
		{
			return _con.back();
		}
		void pop()
		{
			_con.pop_back();
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

容器適配器默認(rèn)缺省為deque，但是對(duì)于stack的特點(diǎn)：尾插尾刪；使用vector和list都可以。

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

template<class T ,class Container=deque<T>>
	class Queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		T& front()
		{
			return _con.front();
		}
		void pop()
		{
			_con.pop_front();
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;

queue和stack的默認(rèn)缺省適配器也是deque，但是對(duì)于queue的特點(diǎn)：頭刪尾插；適配器可以使用list，不可以使用vector因?yàn)閷?duì)于vector來(lái)說(shuō)頭刪需要移動(dòng)數(shù)據(jù)，不是很方便。

今天對(duì)適配器以及stack和queue的介紹、使用、模擬實(shí)現(xiàn)的分享到這就結(jié)束了，希望大家讀完后有很大的收獲，也可以在評(píng)論區(qū)點(diǎn)評(píng)文章中的內(nèi)容和分享自己的看法。您三連的支持就是我前進(jìn)的動(dòng)力，感謝大家的支持??！?!

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-755498.html

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