目錄

stack簡(jiǎn)介

stack的常用接口

queue簡(jiǎn)介

queue的常用接口

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

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

stack簡(jiǎn)介

1. stack是具有后進(jìn)先出操作的一種容器適配器，其只能從容器的一端進(jìn)行元素的插入與刪除操作；

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

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 - C++ Reference

stack的常用接口

int main()
{
	stack<int> st;
	//入棧順序:1,2,3,4
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);

	cout << "size=" << st.size() << endl;
	while (!st.empty())//判斷棧是否為空
	{
		//非空取棧頂元素
		cout << st.top() << " ";
		//出棧
		st.pop();
	}
	cout << endl;
	return 0;
}

?運(yùn)行結(jié)果：

queue簡(jiǎn)介

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

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

3. 底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門設(shè)計(jì)的容器類，該底層容器至少支持以下操作:

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 - C++ Reference

queue的常用接口

int main()
{
	queue<int> q;
	//入隊(duì)列順序:1 2 3 4
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	//計(jì)算隊(duì)列中元素的個(gè)數(shù)
	cout << "size=" << q.size() << endl;
	//取隊(duì)列的尾部元素
	cout << "back=" << q.back() << endl;
	while (!q.empty())//判斷隊(duì)列是否為空
	{
		//非空取隊(duì)列頭部元素
		cout << q.front() << " ";
		//出隊(duì)列
		q.pop();
	}
	cout << endl;
	return 0;
}

?運(yùn)行結(jié)果：

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

?容器適配器：

1. ? 已有的基本容器vector/list/deque相當(dāng)于一臺(tái)設(shè)備，這臺(tái)設(shè)備支持的操作很多，比如插入，刪除，迭代器訪問(wèn)等等，我們的需求是這個(gè)容器表現(xiàn)出來(lái)的是棧的特性: 先進(jìn)后出，入棧出棧等等，此時(shí)，沒有必要重新動(dòng)手寫一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，而是把原來(lái)的容器重新封裝一下，改變它的接口，就可以把它當(dāng)做棧使用；
2. ? 容器適配器就是由基本的容器適配(改造)所形成的容器，比如stack，可以將stack理解成只是對(duì)vector/deque/list的訪問(wèn)受某種規(guī)則約束(只能從尾部訪問(wèn))，所以沒有必要將stack做成一個(gè)基本容器，使用其它的基本容器進(jìn)行封裝改造即可，所以stack在STL中只是一個(gè)“容器適配器”，而不是一個(gè)基礎(chǔ)容器；

template<class T, class Container = deque<T>>
class stack
{
public:
    //構(gòu)造函數(shù),拷貝構(gòu)造函數(shù),析構(gòu)函數(shù),賦值運(yùn)算符重載均不需要實(shí)現(xiàn)
    //對(duì)于自定義類型的成員變量_con,編譯器自動(dòng)調(diào)用類的默認(rèn)成員函數(shù)
     
	//入棧
	void push(const T& x)
	{
		_con.push_back(x);
	}
	//出棧
	void pop()
	{
		_con.pop_back();
	}
	//獲取棧頂元素
	const T& top()
	{
		return _con.back();
	}
	//獲取棧中元素個(gè)數(shù)
	size_t size()
	{
		return _con.size();
	}
	//檢測(cè)棧是否為空
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;//成員變量為容器(vector/list/deque)
};

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

template<class T, class Container = deque<T>>
class queue
{
public:
	//隊(duì)尾入隊(duì)列
	void push(const T& x)
	{
		_con.push_back(x);
	}
	//隊(duì)頭出隊(duì)列
	void pop()
	{
		_con.pop_front();
	}
	//隊(duì)頭元素可被修改
	T& front()
	{
		return _con.front();
	}
	//隊(duì)頭元素不可被修改
	const T& front()const
	{
		return _con.front();
	}
	//隊(duì)尾元素可被修改
	T& back()
	{
		return _con.back();
	}
	//隊(duì)尾元素不可被修改
	const T& back()const
	{
		return _con.back();
	}
	size_t size()const
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};

總結(jié)：

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；

歡迎大家批評(píng)指正，博主會(huì)持續(xù)輸出優(yōu)質(zhì)內(nèi)容，謝謝大家觀看，碼字不易，希望大家給個(gè)一鍵三連支持~ 你的支持是我創(chuàng)作的不竭動(dòng)力~

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

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