0x01 栈

1
#include<stack>

先记录一下栈stack。

和数据结构教材讲的性质基本一致，这里记录一下STL实现栈的方法。

1
stack<typename T, typename Container = deque<T>>

栈的类模板，第一个参数是存储对象的类型，第二个参数是底层容器的类型。

image-20240225200412230

还有一个swap函数，swap(stack &other_stack)，能将当前栈中的元素和参数中的元素交换。stack模板还有赋值运算符重载，operator=( )。

访问栈：

1
2
3
4
5
6
7
8
9
10
11
12
deque<int> data{0,1,2,3,4}; 
//初始化一个栈
stack<int> data(data); 
cout<<"data : "<<data.size()<<endl; 
while(!data.empty()){   
    //获得栈顶元素
	cout<<data.top()<<" ";  
    //栈顶元素出栈 
	data.pop();
}
cout<<endl; 
cout<<"data : "<<data.size()<<endl;

0x02 队列

1
#include<queue>

stack和queue这类模板在初始化时，都默认封装了一个deque容器，修改第二个参数的模板类型能使用其他自定义的容器。

image-20240225201211734

这里顺便记录一下emplace是什么吧，我当时看的时候也不懂，看这个例子就完全明白了

image-20240225203600168也有赋值运算符重，也有swap函数，也有拷贝构造函数。

1
2
3
4
5
list<int> data_{0,1,2,3}; 
queue<int,list<int>> q(data_); 
//list容器初始化队列
queue<int,list<int>> copy_q {q}; 
//拷贝构造新队列

这里补充一下，list容器类似于链表，deque容器类似于vector，但是是双端数组，可以对头部进行插入和删除。具体操作再看。

栈和队列两种模板默认封装deque容器，更利于头尾的修改。

0x03 堆（优先队列）

优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。

1
priority_queue<Type, Container, Functional>

Type就是数据类型，Container就是容器类型，STL里默认vector。Functional就是比较的方式（是一个仿函数，重载了括号），默认大顶堆

1
2
3
4
5
//升序队列（小顶堆）
priority_queue <int,vector<int>,greater<int> > q;
//降序队列（大顶堆）
priority_queue<int> a;（默认大顶堆）
priority_queue <int,vector<int>,less<int> >q;

如果你用的不是int这种基本数据类型，比如比较两个类，那么就要填入自己重载后的运算符了。

c++优先队列(priority_queue)用法详解

C++ STL 之 stack 和 queue

C++11新特性emplace操作

优先队列自定义类型