STL中容器适配器：stack,queue,priority_queue 的介绍与简单模拟实现

stack(栈)

stack的基本介绍

栈（Stack）是一种后进先出（LIFO）的线性数据结构，只能在容器的一端（称为栈顶）进行插入和删除操作。

**核心特性

• 仅允许在栈顶插入和删除元素
• 不支持随机访问
• 没有迭代器，只能访问栈顶元素

template<classT,classContainer=deque<T>>classstack;

stack的常用接口

stack的模拟实现

template<classT,classContainer=deque<T>>classStack{private:Container _con;// 底层容器public:Stack()=default;voidpush(constT&val){_con.push_back(val);// 尾部作为栈顶}voidpop(){_con.pop_back();}T&top(){return_con.back();}constT&top()const{return_con.back();}boolempty()const{return_con.empty();}size_tsize()const{return_con.size();}};

queue（队列）

queue的基本介绍

**队列（Queue）是一种先进先出（FIFO）**的线性数据结构，允许在队尾插入元素，在队头删除元素。

template<classT,classContainer=deque<T>>classqueue;

queue的常用接口

queue的模拟实现

template<classT,classContainer=deque<T>>classQueue{private:Container _con;public:Queue()=default;voidpush(constT&val){_con.push_back(val);}voidpop(){_con.pop_front();// 需要底层支持pop_front}T&front(){return_con.front();}T&back(){return_con.back();}boolempty()const{return_con.empty();}size_tsize()const{return_con.size();}};

priority_queue的基本介绍

优先队列（Priority Queue）是一种特殊的队列，其中的元素按照优先级排序。默认情况下，优先级最高的元素（最大堆）总是在队头。

template<classT,classContainer=vector<T>,classCompare=less<typenameContainer::value_type>>classpriority_queue;

核心特性

• 底层通常使用**堆（heap）**实现
• 默认是大根堆（最大元素在顶部）
• 支持插入和删除最大/最小元素的操作（O(log n)）
• 支持查看堆顶元素（O(1)）

priority_queue的基本用法

// 默认大根堆priority_queue<int>maxHeap;// 小根堆priority_queue<int,vector<int>,greater<int>>minHeap;// 使用数组初始化vector<int>nums={3,1,4,1,5,9};priority_queue<int>pq(nums.begin(),nums.end());

priority_queue的模拟实现

template<classT,classContainer=vector<T>,classCompare=less<T>>classPriorityQueue{private:Container _con;Compare _comp;// 向上调整（用于插入）voidshiftUp(intidx){while(idx>0){intparent=(idx-1)/2;if(!_comp(_con[parent],_con[idx]))break;swap(_con[parent],_con[idx]);idx=parent;}}// 向下调整（用于删除）voidshiftDown(intidx){intsize=_con.size();while(idx*2+1<size){intchild=idx*2+1;if(child+1<size&&_comp(_con[child],_con[child+1])){child++;}if(!_comp(_con[idx],_con[child]))break;swap(_con[idx],_con[child]);idx=child;}}public:PriorityQueue()=default;voidpush(constT&val){_con.push_back(val);shiftUp(_con.size()-1);}voidpop(){if(empty())return;_con[0]=_con.back();_con.pop_back();if(!empty())shiftDown(0);}constT&top()const{return_con.front();}boolempty()const{return_con.empty();}size_tsize()const{return_con.size();}};

注释版/** * 优先队列（堆）模板类 * @tparam T 元素类型 * @tparam Container 底层容器类型，默认为vector<T> * @tparam Compare 比较器类型，默认为less<T>（最大堆） */template<classT,classContainer=vector<T>,classCompare=less<T>>classPriorityQueue{private:Container _con;// 底层容器（通常为数组）Compare _comp;// 比较函数对象/** * 向上调整（堆化） - 用于插入新元素后维护堆性质 * @param idx 需要向上调整的节点索引 * 时间复杂度：O(log n) */voidshiftUp(intidx){// 从当前节点开始，向上遍历直到根节点while(idx>0){intparent=(idx-1)/2;// 计算父节点索引// 如果当前节点不比父节点"优先"，则停止调整if(!_comp(_con[parent],_con[idx]))break;// 交换父子节点swap(_con[parent],_con[idx]);idx=parent;// 继续向上检查}}/** * 向下调整（堆化） - 用于删除堆顶后维护堆性质 * @param idx 需要向下调整的节点索引 * 时间复杂度：O(log n) */voidshiftDown(intidx){intsize=_con.size();// 当当前节点至少有一个子节点时继续调整while(idx*2+1<size){intchild=idx*2+1;// 左子节点索引// 如果存在右子节点且右子节点比左子节点"更优先"if(child+1<size&&_comp(_con[child],_con[child+1])){child++;// 选择更优先的子节点}// 如果当前节点比子节点"优先"，则停止调整if(!_comp(_con[idx],_con[child]))break;// 交换父子节点swap(_con[idx],_con[child]);idx=child;// 继续向下检查}}public:// 默认构造函数PriorityQueue()=default;/** * 插入元素到优先队列 * @param val 要插入的值 * 步骤：1. 添加到末尾 2. 向上调整恢复堆性质 */voidpush(constT&val){_con.push_back(val);// 在末尾添加新元素shiftUp(_con.size()-1);// 从新元素位置开始向上调整}/** * 移除堆顶元素（优先级最高的元素） * 步骤：1. 用末尾元素替换堆顶 2. 删除末尾 3. 向下调整恢复堆性质 */voidpop(){if(empty())return;// 空队列检查_con[0]=_con.back();// 用最后一个元素覆盖堆顶_con.pop_back();// 删除最后一个元素if(!empty())shiftDown(0);// 从堆顶开始向下调整}/** * 获取堆顶元素（优先级最高的元素） * @return 堆顶元素的常量引用 * 注意：调用前需确保队列非空 */constT&top()const{return_con.front();// 堆顶位于容器首部}/** * 检查优先队列是否为空 * @return bool 队列为空返回true */boolempty()const{return_con.empty();}/** * 获取优先队列中元素数量 * @return size_t 元素个数 */size_tsize()const{return_con.size();}};// 使用示例说明：// PriorityQueue<int> pq; // 最大堆（默认）// PriorityQueue<int, vector<int>, greater<int>> min_pq; // 最小堆

容器适配器

**适配器（Adapter）**是一种设计模式，它将一个类的接口转换成客户期望的另一个接口。STL中的容器适配器是在现有容器的基础上封装新的接口。

STL中的容器适配器

deque（双端队列）

deque的结构原理

**deque（Double-ended Queue）**是一个双开口的"连续"空间数据结构：

• 支持在头部和尾部高效插入/删除（O(1)）
• 实际是分段连续空间（动态二维数组）
• 通过**中控器（map）**管理多个固定大小的缓冲区

deque的底层结构

中控器map[ptr0]->[缓冲区0:012][ptr1]->[缓冲区1:345][ptr2]->[缓冲区2:678]...

迭代器设计：

deque迭代器需要维护:

1. 当前元素位置
2. 当前缓冲区指针
3. 缓冲区边界信息

deque的优缺点分析

优点

1. 头尾插入删除高效：O(1)时间复杂度
2. 空间利用率较高：比list连续，无需额外指针开销
3. 扩容代价较低：无需像vector一样整体搬移

缺点

1. 遍历效率低：需要频繁检查缓冲区边界
2. 随机访问较慢：需要计算定位到具体缓冲区
3. 中间插入删除效率低：需要移动元素

deque作为默认容器的原因

// STL中的默认定义template<classT,classContainer=deque<T>>classstack;template<classT,classContainer=deque<T>>classqueue;

选择deque的原因：

1. 对于stack：
   • 只需要尾插尾删，deque效率高
   • 比vector扩容代价小
   • 比list空间利用率高
2. 对于queue：
   • 需要头删尾插，deque在两端操作都是O(1)
   • vector不支持高效的头删
   • list空间开销大
3. 综合优势：
   • 避免了vector的大规模数据搬移
   • 避免了list的额外指针开销
   • 完美适配stack和queue的操作需求

容器选择总结

// 根据需求自定义底层容器// 1. 如果需要频繁遍历stack<int,vector<int>>st1;// 使用vectorqueue<int,list<int>>q1;// 使用list// 2. 如果对内存敏感stack<int,list<int>>st2;// 无扩容问题queue<int,deque<int>>q2;// 折中方案// 3. 如果对性能要求极高stack<int,deque<int>>st3;// 默认最优queue<int,deque<int>>q3;// 默认最优// 4. priority_queue的特殊需求priority_queue<int,vector<int>>pq1;// 默认，随机访问快priority_queue<int,deque<int>>pq2;// 扩容代价小