文┞仿目次

• • • 一、容器適配器
    • 二、stack容器
    • • • 1. stack的特點(diǎn)與應(yīng)用
        • 2. stack的成員函數(shù)
    • 三、queue容器
    • • • 1. queue的特點(diǎn)與應(yīng)用
        • 2. queue的成員函數(shù)
        • 3. queue的應(yīng)用
    • 四、priority_queue容器
    • • • 1. 特點(diǎn)
        • 2. 應(yīng)用

一、容器適配器

接下來介紹 3 種容器適配器，分別是 stack、queue、priority_queue：

• stack：是一個(gè)封裝了 deque 容器的適配器類模板，默認(rèn)實(shí)現(xiàn)的是一個(gè)后入先出（Last-In-First-Out，LIFO）的壓入棧。stack 模板定義在頭文件 stack 中。
• queue：是一個(gè)封裝了 deque 容器的適配器類模板，默認(rèn)實(shí)現(xiàn)的是一個(gè)祖先先出（First-In-First-Out，LIFO）的隊(duì)列?？烧J(rèn)為它指定一個(gè)相符肯定前提的基本容器。queue 模板定義在頭文件 queue 中。
• priority_queue：是一個(gè)封裝了 vector 容器的適配器類模板，默認(rèn)實(shí)現(xiàn)的是一個(gè)會(huì)對(duì)元素排序，大年夜而包管最大年夜元素總在隊(duì)列最前面的隊(duì)列。priority_queue 模板定義在頭文件 queue 中。

簡(jiǎn)單的懂得容器適配器：將不實(shí)用的序列式容器（包含 vector、deque 和 list）變當(dāng)善

功能如下：

container addaptorcharacteristicfunctionsstackLIFOpush()、pop()、top()queueFIFOpush()、pop()、front()、back()priority_queuefirst item is the greatest prioritypush()、pop()、top()

三類容器適配器均無(wú)迭代器，是以拜訪元素的獨(dú)一方法是遍歷容器，經(jīng)由過程賡續(xù)移除拜訪過的元素，去拜訪下一元素

---

二、stack容器

1. stack的特點(diǎn)與應(yīng)用

棧中存儲(chǔ)的元素知足“落后先出（簡(jiǎn)稱LIFO）”的準(zhǔn)則，stack 適配器也同樣遵守這一準(zhǔn)則。

因?yàn)?stack 適配器以模板類 stack<T,Container=deque<T>>（個(gè)中 T 為存儲(chǔ)元素的類型，Container 表示底層容器的類型）的情勢(shì)位于頭文件中，并定義在 std 定名空間里。第二個(gè)參數(shù)默認(rèn)為 deque，可以指定第二個(gè)參數(shù)的類型，只要該容器支撐 empty()、size()、back()、push_back()、pop_back() 這 5 個(gè)成員函數(shù)即可，如：vector、deque 和 list：

std::stack<std::string, std::list<int>> values;

2. stack的成員函數(shù)

函數(shù)功能size()返回元素個(gè)數(shù)empty()若stack為空則返回truetop()返回棧頂元素的引用&，棧空則報(bào)錯(cuò)push(const T& val)將val壓棧，應(yīng)用了push_back()來實(shí)現(xiàn)pop()彈棧操作

舉例：

#include <iostream>
#include <stack>
#include <list> 
using namespace std;

int main()
{
	stack<int> s;
	stack<int, std::list<int>> s1;
	s.push(2);
	s.push(5);
	s.push(1);
	s.push(8);
	
	cout << s.size() << endl;
	while(!s.empty()){
		cout << s.top() << " ";
		s.pop();
	}
	return 0;
}

結(jié)不雅：

4
8 1 5 2

---

三、queue容器

1. queue的特點(diǎn)與應(yīng)用

這種存儲(chǔ)構(gòu)造最大年夜的特點(diǎn)是，最先輩入 queue 的元素，也可以最先大年夜 queue 中出來，即竽暌姑此容器適配器存儲(chǔ)數(shù)據(jù)具有“先輩先出（簡(jiǎn)稱 “FIFO” ）”的特點(diǎn)，是以 queue 又稱為隊(duì)列適配器。

queue容器包含在 <queue> 庫(kù)中，定義一個(gè)queue容器可以指定基本容器（deque或list），底層應(yīng)用的基本容器選擇默認(rèn)為 deque 容器

#include <queue>
#include <iostream>
using namespace std;

queue<int, deque<int>> q;
queue<int, std::list<int>> q1;

2. queue的成員函數(shù)

函數(shù)功能size()返回元素個(gè)數(shù)empty()若stack為空則返回truefront()返回 queue 中第一個(gè)元素的引用。如不雅 queue 是常量，就返回一個(gè)常引用；如不雅 queue 為空，返回值是不決義的back()返回 queue 中最后一個(gè)元素的引用。如不雅 queue 是常量，就返回一個(gè)常引用；如不雅 queue 為空，返回值是不決義的push(const T& val)在 queue 的尾部添加一個(gè)元素的副本。這是經(jīng)由過程調(diào)用底層容器的成員函數(shù) push_back() 來完成的。pop()刪除 queue 中的第一個(gè)元素。swap(queue &other_queue)交換兩個(gè)容器（請(qǐng)求底層基本容器雷同

3. queue的應(yīng)用

#include <queue>
#include <iostream>
using namespace std;

int main()
{
	queue<int> myque;
	myque.push(5);
	myque.push(2);
	myque.push(2);
	myque.push(3);
	myque.push(6);
	
	cout << "size: " << myque.size() << endl;
	while (!myque.empty()){
		cout << myque.front() << " ";
		myque.pop();
	}
	return 0;
}

---

四、priority_queue容器

1. 特點(diǎn)

priority_queue容器遵守 “First in，Largest out”原則。直白的翻譯，指的就是先輩隊(duì)列的元素并不必定先出隊(duì)列，而是優(yōu)先級(jí)最大年夜的元素最先出隊(duì)列。每個(gè) priority_queue 容器適配器在創(chuàng)建時(shí)，都制訂了一種排序規(guī)矩。根據(jù)此規(guī)矩，該容器適配器中存儲(chǔ)的元素就有了優(yōu)先級(jí)高低之分。

2. 應(yīng)用

STL 中，priority_queue 容器適配器的定義如下：

template <typename T,
        typename Container=std::vector<T>,
        typename Compare=std::less<T> >
class priority_queue{
    //......
}

• priority_queue定義在 <queue> 頭文件中
• typename T：指定存儲(chǔ)元素的具體類型；
• typename Container：指定 priority_queue 底層應(yīng)用的基本容器，默認(rèn)應(yīng)用 vector 容器。
• typename Compare：指定容器中評(píng)定元素優(yōu)先級(jí)所遵守的排序規(guī)矩，默認(rèn)應(yīng)用std::less按照元素值大年夜大年夜到小進(jìn)行排序，還可以應(yīng)用std::greater按照元素值大年夜小到大年夜排序，但更多情況下是應(yīng)用自定義的排序規(guī)矩。

作為 priority_queue 容器適配器的底層容器，其必須包含 empty()、size()、front()、push_back()、pop_back() 這幾個(gè)成員函數(shù)，STL 序列式容器中只有 vector 和 deque 容器相符前提。

priority_queue的操作函數(shù)和stack的類似，包含了push()、pop()、top()、empty() 和 size() 等函數(shù)。

#include <iostream>
#include <queue>
using namespace std;

class Student{
	public:
		string name;
		int number;
		Student(string str, int n):name(str), number(n){}
};

struct mycmp{
	bool operator() (const Student &s1, const Student &s2){
		return s1.number < s2.number;	// 大年夜大年夜到小 
	}
};

int main()
{
	priority_queue<Student, deque<Student>, mycmp> pq;
	pq.push(Student("L", 12));
	pq.push(Student("Y", 3));
	pq.push(Student("U", 8));
	pq.push(Student("C", 5));
	
	cout << "Size = " << pq.size() << endl;
	cout << "name" << "t" << "number" << endl;
	while(!pq.empty()){
		Student stud = pq.top();
		cout << stud.name << "\t" << stud.number << endl;
		pq.pop();
	}
	return 0;
}

輸出結(jié)不雅為：

Size = 4
nametnumber
L       12
U       8
C       5
Y       3

---

參考內(nèi)容：容器適配器的應(yīng)用