date: 2020/01/11

stack, queue, priorty_queue均为用顺序容器实现的容器适配器

stack类

http://www.cplusplus.com/reference/stack/stack/

http://c.biancheng.net/view/393.html

#include <stack> 

stack是容器适配器,使用顺序容器实现(默认为deque),不一定是vector, list, deque,只要是实现了 empty , size , back , push_back , pop_back 的容器都可以用stack适配。

std::stack<int> s1;   // deque实现的stack
std::stack<int, vector<int>> s2;    // vector实现的stack


仅支持以下的简单接口——

bool empty();   // 是否为空(size为0)【调用实现容器的empty()】
size_type size();     // 获取当前长度【调用实现容器的size()】
T &top();   // 获取栈顶元素【调用实现容器的back()】
void push(const T &x);   // 压入栈【调用实现容器的push_back()】
void pop();    // 弹出栈顶(不返回)【调用实现容器的pop_back()】

queue类

http://www.cplusplus.com/reference/queue/queue/

http://c.biancheng.net/view/396.html

#include <queue> 

queue是容器适配器,使用顺序容器实现(默认为deque),不一定是list, deque,只要是实现了 empty , size , back , front ,  push_back , pop_front 的容器都可以用queue适配。


用法与stack类似,仅支持以下简单接口——

bool empty();   // 是否为空(size为0)【调用实现容器的empty()】
size_type size();     // 获取当前长度【调用实现容器的size()】
T &front();   // 获取队首元素【调用实现容器的front()】
T &back();   // 获取队尾元素【调用实现容器的back()】
void push(const T &x);   // 入队【调用实现容器的push_back()】
void pop();    // 出队(不返回)【调用实现容器的pop_front()】


priority_queue类

http://www.cplusplus.com/reference/queue/priority_queue/

http://c.biancheng.net/view/396.html

#include <queue> 

priority_queue是容器适配器,使用顺序容器实现(默认为vector),不一定是vector, list, deque,只要是实现了 empty , size , back (注意不是front), push_back , pop_back 的容器都可以用priority_queue适配。


用法与stack类似,但还额外支持可以比较函数(默认为less)作为参数;

注意队头是top而不是front

#include <functional>  // less, greater
std::priority_queue<int, vector<int>, std::less<T>> pq;


作为优先序列,队头肯定是优先级最高的(队头x,对于队列内任意其他元素y,总有cmp(x, y)为false)。但priority_queue内部采用的是“堆排序”,并不是完全有序的,但能确保队头一只是最大的。


priority_queue主要用于逐一插入元素,每次取走最大的一个元素的情形。其插入和删除操作的复杂度均为O(logn)。


支持的接口与stack类完全相同。


示例: