stack和queue的介紹與使用及模擬實(shí)現(xiàn)

公司主營業(yè)務(wù)：成都做網(wǎng)站、網(wǎng)站制作、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)推出黎城免費(fèi)做網(wǎng)站回饋大家。文章目錄

• stack和queue的介紹與使用及模擬實(shí)現(xiàn)
• 1.stack的介紹與使用
• • 1.1.stack的介紹
  • 1.2.stack的使用
  • 1.3.stack的模擬實(shí)現(xiàn)
• 2.queue的介紹和使用
• • 2.1.queue的介紹
  • 2.2.queue的使用
  • 2.3.queue的模擬實(shí)現(xiàn)
• 3. 容器適配器
• • 3.1.STL標(biāo)準(zhǔn)庫中stack和queue的底層結(jié)構(gòu)
  • 3.2.deque的簡單介紹(了解)
  • 3.3.deque原理介紹
  • 3.4.deque的優(yōu)缺點(diǎn)
  • 3.5.為什么選擇deque作為stack和queue的底層默認(rèn)容器

1.stack的介紹與使用 1.1.stack的介紹

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

2、stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數(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。

1.2.stack的使用

函數(shù)說明	接口說明
stack()	構(gòu)造空的棧
empty()	檢測棧是否為空
size()	返回stack中元素的個數(shù)
top()	返回棧頂元素的引用
push()	將元素val壓入棧中
pop()	將stack中尾部的元素彈出

• 定義方式：

使用默認(rèn)的適配器定義棧

stacks;

使用指定的適配器定義棧

stack>s1;
stack>s2;

不能用指定string的適配器

stacks3;//存在截斷數(shù)據(jù)丟失的風(fēng)險

string的數(shù)據(jù)為字符，字符本質(zhì)上存的是ASCII碼，有范圍，超過這個范圍，就會出現(xiàn)截斷導(dǎo)致數(shù)據(jù)丟失

• 測試案例：

void test_stack()
{// 后進(jìn)先出，不支持迭代器
	stacks;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	while (!s.empty())
	{cout<< s.top()<< " ";
		s.pop();
	}
	cout<< endl;
}

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

stack的底層是借助容器適配器來完成的，實(shí)現(xiàn)方式也非常簡單。

namespace stack_realize
{// 函數(shù)參數(shù)控制的是對象，模板參數(shù)控制的是模板
	template>class stack
	{public:
		void push(const T& val)
		{	_con.push_back(val);
		}

		void pop()
		{	_con.pop_back();
		}

		bool empty() const
		{	return _con.empty();
		}

		const T& top() const
		{	return _con.back();
		}
		 
		size_t size() const 
		{	return _con.size();
		}

	private:
		//vector_v; 太死板，有限制
		Container _con;
	};
}

---

2.queue的介紹和使用 2.1.queue的介紹

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：檢測隊(duì)列是否為空
• size：返回隊(duì)列中有效元素的個數(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。

2.2.queue的使用

函數(shù)聲明	接口說明
queue()	構(gòu)造空的隊(duì)列
empty()	檢測隊(duì)列是否為空，是返回true，不是返回false
size()	返回隊(duì)列中有效元素的個數(shù)
front()	返回對頭元素的引用
back()	返回隊(duì)尾元素的引用
push()	在隊(duì)尾將元素val入隊(duì)列
pop()	將對頭元素出隊(duì)列

• 定義方式：

1、使用默認(rèn)的適配器定義隊(duì)列

queueq1;

2、使用指定的適配器定義隊(duì)列

queue>q3;//不能用vector

注意不能使用vector作為適配器，因?yàn)関ector不支持頭刪。

• 測試案例：

void test_queue()
{// 先進(jìn)先出，不支持迭代器
	queueq;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	while (!q.empty())
	{cout<< q.front()<< " ";
		q.pop();
	}
	cout<< endl;
}

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

namespace queue_realize
{// 函數(shù)參數(shù)控制的是對象，模板參數(shù)控制的是模板
	template>class queue
	{public:
		void push(const T& val)
		{	_con.push_back(val);
		}

		void pop()
		{	_con.pop_back();
		}

		const T& front()
		{	return _con.front();
		}
		
		const T& back()
		{	return _con.back();
		}

		bool empty() const
		{	return _con.empty();
		}

		size_t size() const
		{	return _con.size();
		}

	private:
		//vector_v; 太死板，有限制
		Container _con;
	};
}

3. 容器適配器

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

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

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

3.2.deque的簡單介紹(了解)

在正式了解deque之前，先看下vector和list的簡要對比：

• vector的優(yōu)缺點(diǎn)：

vector優(yōu)點(diǎn)	vector缺點(diǎn)
1. 尾插尾刪效率較高	1. 在頭部或中間插入刪除時間復(fù)雜度為O(N)，效率低，需要挪動數(shù)據(jù)
2. 支持隨機(jī)訪問	2. 空間不夠，需要擴(kuò)容，擴(kuò)容有一定性能消耗，還存在一定的空間浪費(fèi)
3. cpu高速緩存命中率高

• list的優(yōu)缺點(diǎn)：

list優(yōu)點(diǎn)	list缺點(diǎn)
1. 在任意位置插入刪除數(shù)據(jù)的時間復(fù)雜度都是O(1)，效率高	1. 不支持隨機(jī)訪問
2. 按需申請釋放空間，不存在空間浪費(fèi)	2. cpu高速緩存命中率低

• 而deque就是綜合了vector和list的優(yōu)缺點(diǎn)設(shè)計(jì)出來的：

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

3.3.deque原理介紹

deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實(shí)際deque類似于一個動態(tài)的二維數(shù)組，為了管理這些連續(xù)空間，deque 容器用中控數(shù)組（數(shù)組名假設(shè)為 map）存儲著各個連續(xù)空間的首地址。也就是說，map 數(shù)組中存儲的都是指針，指向那些真正用來存儲數(shù)據(jù)的各個連續(xù)空間（如下圖所示）。

通過建立 map 數(shù)組，deque 容器申請的這些分段的連續(xù)空間就能實(shí)現(xiàn)“整體連續(xù)”的效果。換句話說，當(dāng) deque 容器需要在頭部或尾部增加存儲空間時，它會申請一段新的連續(xù)空間，同時在 map 數(shù)組的開頭或結(jié)尾添加指向該空間的指針，由此該空間就串接到了 deque 容器的頭部或尾部。

當(dāng)中控數(shù)組map數(shù)組滿了的時候，再申請一塊更大的連續(xù)空間供 map 數(shù)組使用，將原有數(shù)據(jù)（很多指針）拷貝到新的 map 數(shù)組中，然后釋放舊的空間。

3.4.deque的優(yōu)缺點(diǎn)

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

3.5.為什么選擇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中對stack和queue默認(rèn)選擇deque作為其底層容器，主要是因?yàn)椋?/p>

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

結(jié)合了deque的優(yōu)點(diǎn)，而完美的避開了其缺陷。
st。但是STL中對stack和queue默認(rèn)選擇deque作為其底層容器，主要是因?yàn)椋?/p>

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

結(jié)合了deque的優(yōu)點(diǎn)，而完美的避開了其缺陷。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：【C++】STL——stack和queue的介紹與使用及模擬實(shí)現(xiàn)-創(chuàng)新互聯(lián)
路徑分享：http://weahome.cn/article/digpoj.html