文┞仿目次

• • • 一、容器适配器
    • 二、stack容器
    • • • 1. stack的特点与应用
        • 2. stack的成员函数
    • 三、queue容器
    • • • 1. queue的特点与应用
        • 2. queue的成员函数
        • 3. queue的应用
    • 四、priority_queue容器
    • • • 1. 特点
        • 2. 应用

一、容器适配器

接下来介绍 3 种容器适配器，分别是 stack、queue、priority_queue：

• stack：是一个封装了 deque 容器的适配器类模板，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。stack 模板定义在头文件 stack 中。
• queue：是一个封装了 deque 容器的适配器类模板，默认实现的是一个祖先先出（First-In-First-Out，LIFO）的队列。可认为它指定一个相符肯定前提的基本容器。queue 模板定义在头文件 queue 中。
• priority_queue：是一个封装了 vector 容器的适配器类模板，默认实现的是一个会对元素排序，大年夜而包管最大年夜元素总在队列最前面的队列。priority_queue 模板定义在头文件 queue 中。

简单的懂得容器适配器：将不实用的序列式容器（包含 vector、deque 和 list）变当善

功能如下：

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

三类容器适配器均无迭代器，是以拜访元素的独一方法是遍历容器，经由过程赓续移除拜访过的元素，去拜访下一元素

---

二、stack容器

1. stack的特点与应用

栈中存储的元素知足“落后先出（简称LIFO）”的准则，stack 适配器也同样遵守这一准则。

因为 stack 适配器以模板类 stack<T,Container=deque<T>>（个中 T 为存储元素的类型，Container 表示底层容器的类型）的情势位于头文件中，并定义在 std 定名空间里。第二个参数默认为 deque，可以指定第二个参数的类型，只要该容器支撑 empty()、size()、back()、push_back()、pop_back() 这 5 个成员函数即可，如：vector、deque 和 list：

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

2. stack的成员函数

函数功能size()返回元素个数empty()若stack为空则返回truetop()返回栈顶元素的引用&，栈空则报错push(const T& val)将val压栈，应用了push_back()来实现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;
}

结不雅：

4
8 1 5 2

---

三、queue容器

1. queue的特点与应用

这种存储构造最大年夜的特点是，最先辈入 queue 的元素，也可以最先大年夜 queue 中出来，即竽暌姑此容器适配器存储数据具有“先辈先出（简称 “FIFO” ）”的特点，是以 queue 又称为队列适配器。

queue容器包含在 <queue> 库中，定义一个queue容器可以指定基本容器（deque或list），底层应用的基本容器选择默认为 deque 容器

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

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

2. queue的成员函数

函数功能size()返回元素个数empty()若stack为空则返回truefront()返回 queue 中第一个元素的引用。如不雅 queue 是常量，就返回一个常引用；如不雅 queue 为空，返回值是不决义的back()返回 queue 中最后一个元素的引用。如不雅 queue 是常量，就返回一个常引用；如不雅 queue 为空，返回值是不决义的push(const T& val)在 queue 的尾部添加一个元素的副本。这是经由过程调用底层容器的成员函数 push_back() 来完成的。pop()删除 queue 中的第一个元素。swap(queue &other_queue)交换两个容器（请求底层基本容器雷同

3. queue的应用

#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. 特点

priority_queue容器遵守 “First in，Largest out”原则。直白的翻译，指的就是先辈队列的元素并不必定先出队列，而是优先级最大年夜的元素最先出队列。每个 priority_queue 容器适配器在创建时，都制订了一种排序规矩。根据此规矩，该容器适配器中存储的元素就有了优先级高低之分。

2. 应用

STL 中，priority_queue 容器适配器的定义如下：

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

• priority_queue定义在 <queue> 头文件中
• typename T：指定存储元素的具体类型；
• typename Container：指定 priority_queue 底层应用的基本容器，默认应用 vector 容器。
• typename Compare：指定容器中评定元素优先级所遵守的排序规矩，默认应用std::less按照元素值大年夜大年夜到小进行排序，还可以应用std::greater按照元素值大年夜小到大年夜排序，但更多情况下是应用自定义的排序规矩。

作为 priority_queue 容器适配器的底层容器，其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数，STL 序列式容器中只有 vector 和 deque 容器相符前提。

priority_queue的操作函数和stack的类似，包含了push()、pop()、top()、empty() 和 size() 等函数。

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

输出结不雅为：

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

---

参考内容：容器适配器的应用