容器适配器

栈

STL 栈 (std::stack) 是一种后进先出 (Last In, First Out) 的容器适配器，仅支持查询或删除最后一个加入的元素（栈顶元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

头文件

定义

成员函数

以下所有函数均为常数复杂度

• top() 访问栈顶元素（如果栈为空，此处会出错）
• push(x) 向栈中插入元素 x
• pop() 删除栈顶元素
• size() 查询容器中的元素数量
• empty() 询问容器是否为空

简单示例

队列

STL 队列 (std::queue) 是一种先进先出 (First In, First Out) 的容器适配器，仅支持查询或删除第一个加入的元素（队首元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

头文件

定义

成员函数

以下所有函数均为常数复杂度

• front() 访问队首元素（如果队列为空，此处会出错）
• push(x) 向队列中插入元素 x
• pop() 删除队首元素
• size() 查询容器中的元素数量
• empty() 询问容器是否为空

简单示例

优先队列

头文件

定义

成员函数

以下所有函数均为常数复杂度

• top() 访问堆顶元素（此时优先队列不能为空）
• empty() 询问容器是否为空
• size() 查询容器中的元素数量

以下所有函数均为对数复杂度

• push(x) 插入元素，并对底层容器排序
• pop() 删除堆顶元素（此时优先队列不能为空）

简单示例