前言：

本章我們將學(xué)習(xí)stack與queue的基本使用以及模擬實現(xiàn)。與前面已經(jīng)學(xué)過的容器不同，stack與queue屬于STL六大組件之一的容器適配器范疇。

一.stack簡介

在STL中，stack是一個模板類，用于實現(xiàn)棧數(shù)據(jù)結(jié)構(gòu)。棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，可以在棧頂進(jìn)行插入和刪除操作。

stack是一種容器適配器，容器適配器不是容器類型本身，而是對現(xiàn)有的容器類型進(jìn)行了一定程度的封裝和改造，從而形成了一種新的容器類型。

stack類封裝了一個底層容器，可以使用多種不同的容器作為其底層實現(xiàn)，比如deque和vector等。

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

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

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

至于deque是什么我們先不深究，我們就先把它看作vector一樣，后面會講到。

二.stack的模擬實現(xiàn)

我們已經(jīng)知道棧是一個容器適配器，底層封裝了其它容器，所以棧的實現(xiàn)非常簡單，在實現(xiàn)各個函數(shù)接口時，我們直接復(fù)用封裝的容器的相關(guān)接口即可。

不同于vector與list的模擬實現(xiàn)，stack需要兩個模板參數(shù)：

參數(shù)類型：class T
容器類型：class Container

我們可以在自己的命名空間中定義stack類，如下：

namespace dianxia
{
	template<class T, class Container = vector<T>>
	class stack
	{
	public:

		void push(const T& data)
		{
			//...
		}

		void pop()
		{
			//...
		}

		const T& top()
		{
			//...
		}

		size_t size()
		{
			//...
		}

		bool empty()
		{
			//...
		}

	private:
		Container _con;
	};
}

接下來就是實現(xiàn)各個接口了。作為容器適配器，stack的各接口實現(xiàn)極其簡單，用一分鐘實現(xiàn)一個棧來描述也不是太夸張，一起來看看吧。

namespace dianxia
{
	template<class T, class Container = vector<T>>
	class stack
	{

	public:

		void push(const T& data)
		{
			_con.push_back(data);
		}

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

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

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

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

	private:
		Container _con;
	};

}

因為容器適配器是封裝了一層容器的，所以可以直接調(diào)用底層容器的接口供自己使用?，F(xiàn)在再回頭看文章開頭對于容器適配器的描述，應(yīng)該能深刻理解了。

三.queue簡介

queue與stack非常相似。在STL中，隊列（queue）是一種基本的數(shù)據(jù)結(jié)構(gòu)，它是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)。隊列可以看作是一條通往某個目的地的等待隊列，其中最先進(jìn)入的元素首先被處理，而最后進(jìn)入的元素則最后被處理。

與stack相同，queue同樣也是一個容器適配器，queue與stack對比起來學(xué)習(xí)會更加輕松。

四.queue模擬實現(xiàn)

queue與stack的實現(xiàn)方式大同小異，此處不做贅述。

namespace dianxia
{
	template<class T, class Container = list<T>>
	class queue
	{
		void push()
		{
			_con.push_back();
		}

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

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

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

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

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

本章節(jié)的內(nèi)容就到這里了。下一章我們將學(xué)習(xí)雙端隊列——deque和優(yōu)先級隊列——priority_queue，認(rèn)識了雙端隊列，我們就能明白為什么庫中的stack與queue要使用deque來做底層容器了。

本文到此結(jié)束，碼文不易，還請多多支持哦！?。?span toymoban-style="hidden">文章來源地址http://www.zghlxwxcb.cn/news/detail-603363.html

到了這里，關(guān)于模擬實現(xiàn)stack類與queue類的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！