STL: 容器適配器stack 與 queue

這篇具有很好參考價(jià)值的文章主要介紹了STL: 容器適配器stack 與 queue。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

?目錄

1.容器適配器

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

1.2 deque的簡單介紹(了解)

1.2.1 deque的原理介紹

1.2.2 deque的缺陷

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

2. stack的介紹和使用

2.1 stack的介紹

?2.2 stack的使用

2.3 利用deque模擬實(shí)現(xiàn)stack

3.queue的介紹和使用

3.1 queue的介紹

?3.2 queue的使用

3.3 利用deque模擬實(shí)現(xiàn)stack?

4.priority_queue的介紹及使用

4.1 priority_queue的介紹

4.2 priority_queue的使用

3.3?priority_queue的模擬實(shí)現(xiàn)

1.容器適配器

什么是適配器：

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

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

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

STL: 容器適配器stack 與 queue,C++,c++,開發(fā)語言,容器,容器適配器

1.2 deque的簡單介紹(了解)

1.2.1 deque的原理介紹

deque文檔介紹?

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

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

STL: 容器適配器stack 與 queue,C++,c++,開發(fā)語言,容器,容器適配器

1.2.2 deque的缺陷

與vector比較，deque的優(yōu)勢是：頭部插入和刪除時(shí)，不需要搬移元素，效率特別高，而且在擴(kuò)容時(shí)，也不需要搬移大量的元素，因此其效率是比vector高的。

與list比較，其底層是連續(xù)空間，空間利用率比較高，不需要存儲(chǔ)額外字段。

但是，deque有一個(gè)致命缺陷：不適合遍歷，不能隨機(jī)訪問，因?yàn)樵诒闅v時(shí)，deque的迭代器要頻繁的去檢測其是否移動(dòng)到某段小空間的邊界，導(dǎo)致效率低下，而序列式場景中，可能需要經(jīng)常遍歷，因此在實(shí)際中，需要線性結(jié)構(gòu)時(shí)，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看到的一個(gè)應(yīng)用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。

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

1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進(jìn)行操作。

2. 在stack中元素增長時(shí)，deque比vector的效率高(擴(kuò)容時(shí)不需要搬移大量數(shù)據(jù))；queue中的元素增長時(shí)，deque不僅效率高，而且內(nèi)存使用率高。

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

2. stack的介紹和使用

2.1 stack的介紹

stack的文檔介紹

翻譯:

stack是一種容器適配器，專門用在具有后進(jìn)先出操作的上下文環(huán)境中，其刪除只能從容器的一端進(jìn)行元素的插入與提取操作。
stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對(duì)特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。我們后面會(huì)詳細(xì)講解容器適配器。
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

STL: 容器適配器stack 與 queue,C++,c++,開發(fā)語言,容器,容器適配器

?2.2 stack的使用

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

void test1()
{
	wdz::stack<int> s1;
	s1.push(1);
	s1.push(2);
	s1.push(3);
	while (!s1.empty())
	{
		cout << s1.top() << " ";
		s1.pop();
	}
	cout << endl;
}

2.3 利用deque模擬實(shí)現(xiàn)stack

?模擬代碼：

#include<deque>
using namespace std;
namespace xlh
{
    template<class T, class Con = deque<T>>
    class stack
    {
    public:

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

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

        T& top()
        {
            return _c.back();
        }

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

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

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

    private:
        Con _c;

    };
}

3.queue的介紹和使用

3.1 queue的介紹

queue的文檔介紹

翻譯：

隊(duì)列是一種容器適配器，專門用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素。
隊(duì)列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從隊(duì)尾入隊(duì)列，從隊(duì)頭出隊(duì)列。
底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門設(shè)計(jì)的容器類。該底層容器應(yīng)至少支持以下操作:

empty：檢測隊(duì)列是否為空

size：返回隊(duì)列中有效元素的個(gè)數(shù)

front：返回隊(duì)頭元素的引用

back：返回隊(duì)尾元素的引用

push_back：在隊(duì)列尾部入隊(duì)列

pop_front：在隊(duì)列頭部出隊(duì)列

標(biāo)準(zhǔn)容器類deque和list滿足了這些要求。默認(rèn)情況下，如果沒有為queue實(shí)例化指定容器類，則使用標(biāo)準(zhǔn)容器deque。

STL: 容器適配器stack 與 queue,C++,c++,開發(fā)語言,容器,容器適配器

?3.2 queue的使用

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

3.3 利用deque模擬實(shí)現(xiàn)stack?

模擬代碼：

#include<deque>
using namespace std;
namespace xlh
{
    template<class T, class Con = deque<T>>
    class queue
    {
    public:

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

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

        T& back()
        {
            return _c.back();
        }

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

        T& front()
        {
            return _c.front();
        }

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

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

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

    private:
        Con _c;
    };

};

4.priority_queue的介紹及使用

4.1 priority_queue的介紹

priority_queue文檔介紹

翻譯：

優(yōu)先隊(duì)列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個(gè)元素總是它所包含的元素中最大的。
此優(yōu)先級(jí)隊(duì)列類似于堆，在堆中可以隨時(shí)插入元素，并且只能檢索最大堆元素(優(yōu)先隊(duì)列中位于頂部的元素)。
優(yōu)先隊(duì)列被實(shí)現(xiàn)為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，隊(duì)列提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優(yōu)先隊(duì)列的頂部。
底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計(jì)的容器類。容器應(yīng)該可以通過隨機(jī)訪問迭代器訪問，所以這里deque不可以，還要支持以下操作：

empty()：檢測容器是否為空

size()：返回容器中有效元素個(gè)數(shù)

front()：返回容器中第一個(gè)元素的引用

push_back()：在容器尾部插入元素

pop_back()：刪除容器尾部元素
標(biāo)準(zhǔn)容器類vector和deque滿足這些需求。默認(rèn)情況下，如果沒有為特定的priority_queue類實(shí)例化指定容器類，則使用vector。
需要支持隨機(jī)訪問迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過在需要時(shí)自動(dòng)調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來自動(dòng)完成此操作。

4.2 priority_queue的使用

優(yōu)先級(jí)隊(duì)列默認(rèn)使用vector作為其底層存儲(chǔ)數(shù)據(jù)的容器，在vector上又使用了堆算法將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。注意：默認(rèn)情況下priority_queue是大堆。

函數(shù)聲明	接口說明
priority_queue()/priority_queue(first, last)	構(gòu)造一個(gè)空的優(yōu)先級(jí)隊(duì)列
empty( )	檢測優(yōu)先級(jí)隊(duì)列是否為空，是返回true，否則返回 false
top( )	返回優(yōu)先級(jí)隊(duì)列中最大(最小元素)，即堆頂元素
push(x)	在優(yōu)先級(jí)隊(duì)列中插入元素x
pop()	刪除優(yōu)先級(jí)隊(duì)列中最大(最小)元素，即堆頂元素

默認(rèn)情況下priority_queue是大堆。如果要建立小堆，這里還涉及到仿函數(shù)。我們這里先簡單了解一下

STL: 容器適配器stack 與 queue,C++,c++,開發(fā)語言,容器,容器適配器

仿函數(shù)類似于C語言中的函數(shù)指針

示例：

//仿函數(shù)
class Less
{
public:
	bool operator()(int x,int y)
	{
		return x < y;
	}
};

void test6()
{
	Less less;
	//仿函數(shù)，函數(shù)對(duì)象
	cout << less(2, 3) << endl;//less是一個(gè)對(duì)象而不是一個(gè)函數(shù)名
    //輸出1 
	cout << less.operator()(2, 3) << endl;
}

通過對(duì)（）括號(hào)進(jìn)行運(yùn)算符重載，即可實(shí)現(xiàn)大小的比較。我們下面定義兩個(gè)類模板，來確定比較的方法，然后傳入優(yōu)先級(jí)隊(duì)列，即可改變比較的方法。

//仿函數(shù)

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

?建立小堆，greater是由算法庫提供的比較方式，與上面寫的Greater類似。

#include <vector>
#include <queue>
#include <functional> // greater算法的頭文件

void TestPriorityQueue()
{
    // 默認(rèn)情況下，創(chuàng)建的是大堆，其底層按照小于號(hào)比較
    vector<int> v{3,2,7,6,0,4,1,9,8,5};
    priority_queue<int> q1;
    for (auto& e : v)
    q1.push(e);
    cout << q1.top() << endl;
    // 如果要?jiǎng)?chuàng)建小堆，將第三個(gè)模板參數(shù)換成greater比較方式
    priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
    cout << q2.top() << endl;
}

如果在priority_queue中放自定義類型的數(shù)據(jù)，用戶需要在自定義類型中提供> 或者< 的重載。

3.3?priority_queue的模擬實(shí)現(xiàn)

模擬代碼：

#include<vector>
using namespace std;

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

namespace xlh
{
	template<class T,class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	public:

		priority_queue()
		{}

		template<class InputIterator>
		priority_queue(InputIterator frist, InputIterator last)
			:_con(frist,last)
		{
			//向下調(diào)整建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}
			//直接用push相當(dāng)于向上調(diào)整。
		}


		void adjust_up(int child)
		{
			int parent = (child - 1) / 2;//減一除2是不會(huì)小于0的，因?yàn)?0.5 == 0
			Compare com;
			while (child > 0)
			{

				//if(_con[child]>_con[parent])
				if (com(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}

		}

		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void adjust_down(int parent)
		{
			Compare com;

			int child = parent * 2 + 1;

			while (child < _con.size())
			{
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
				{
					child++;
				}

				//if (_con[parent] < _con[child]);
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}


		T& top()
		{
			return _con[0];
		}

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

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

	private:
		Container _con;
	};
}

本篇結(jié)束！文章來源地址http://www.zghlxwxcb.cn/news/detail-752655.html

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