目錄

一，stack

1，stack的介紹

2，stack 框架

3，push(const T& x)

4，pop()

5，top()

6，size()

7，empty()

8，stack 測試

9，源代碼

二，queue

1，queue的介紹

2，queue 框架

3，push(const T& x)

4，pop()

5，front()

6，back()

7，size()

8，empty()

9，queue 測試

10，源代碼

三，總結(jié)

一，stack

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。

2，stack 框架

這里我們要用【適配器】

	template<class T,class Container=vector<T>>
	class stack
	{
	public:
	
	private:
		Container _con;
	};

適配器 Container 可以轉(zhuǎn)換成特定的容器；

3，push(const T& x)

尾插

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

4，pop()

尾刪

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

5，top()

取棧頂元素

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

6，size()

堆棧有效數(shù)據(jù)個數(shù)

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

7，empty()

判空

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

8，stack 測試

void test1()
{
	wxd::stack<int> sk1;

	sk1.push(1);
	sk1.push(2);
	sk1.push(3);
	sk1.push(4);

	sk1.pop();
	cout << sk1.top() << " " << sk1.size() << " " << sk1.empty() << " " << endl;
}

9，源代碼

	template<class T,class Container=vector<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		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;
	};

二，queue

1，queue的介紹

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

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

3，底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門設(shè)計的容器類。該底層容器應(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，queue 框架

	template<class T, class Container = list<T>>
	class queue
	{
	public:
		
	private:
		Container _con;
	};

適配器 Container 可以轉(zhuǎn)換成特定的容器；

3，push(const T& x)

尾插

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

4，pop()

頭刪

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

5，front()

返回隊(duì)列頭部的值

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

6，back()

返回隊(duì)列尾部的值

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

7，size()

返回有效數(shù)據(jù)個數(shù)

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

8，empty()

判空

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

9，queue 測試

void test_queue()
{
	wxd::queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

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

}

10，源代碼

	template<class T, class Container = list<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

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

	private:
		Container _con;
	};

三，總結(jié)

我們就先搞一個大概的，其中還有很多分支，比如我們寫的是擦除某個數(shù)據(jù)，其實(shí)也可以擦除某個范圍，這些就靠大家去摸索，查閱文檔了；

stack 和 queue 類的實(shí)現(xiàn)就到這里了；

加油！

文章來源地址http://www.zghlxwxcb.cn/news/detail-852148.html

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