当前位置：首页 > news >正文

【C++】STL库_stack_queue 的模拟实现

news 来源：原创 2025/7/2 1:36:21

栈（Stack）、队列（Queue）是C++ STL中的经典容器适配器

容器适配器特性

不是独立容器，依赖底层容器（deque/vector/list）
通过限制基础容器接口实现特定访问模式
不支持迭代器操作（无法遍历元素）
时间复杂度：
栈/队列操作均为O(1)
底层容器影响性能：
vector实现栈可能导致扩容拷贝
list实现队列保证稳定性能

典型应用场景：

栈：函数调用栈、括号匹配、表达式求值
队列：消息队列、BFS算法、缓冲机制

（栈和队列前面C语言写过，这里直接贴C++代码）

双端队列：

（不常用，简单介绍和理解）

STL标准库里面默认适配器使用的是deque这个容器，

deque（双端队列）是C++标准库中的顺序容器，全称"double-ended queue"，支持在头尾两端高效插入/删除元素。

分段连续存储：由多个固定大小的存储块（称为缓冲区buffer）构成
中控器结构：使用指针数组（map）管理存储块的地址

优势：

任意位置（头尾插入）插入删除
可以随机访问

缺陷：

operator[]，计算稍显复杂，大量使用，性能下降。
中间插入删除效率不高
底层角度选代器会很复杂

cur 表示当前数据
first 和 last 表示 buffer 的开始和结束
node 反向指向中控位置，方便遍历时找下一个buffer

栈：

template<class T,class Container=deque<T>>
class stack
{
public:void push(const T& x){_con.push_back(x);}void pop();T& top(){return _con.back();}bool empty()const{return _con.empty();}size_t size(){return _con.size();}private:Container _con;};template<class T, class Container>
inline void stack<T, Container>::pop()
{_con.pop_back();
}

队列：

template<class T, class Container = deque<T>>
class queue
{
public:void push(const T& x);void pop(){_con.pop_front();}T& back(){return _con.back();}T& front(){return _con.front();}bool empty()const{return _con.empty();}size_t size(){return _con.size();}private:Container _con;};template<class T, class Container>
inline void queue<T, Container>::push(const T& x)
{_con.push_back(x);
}

仿函数：

仿函数（Functor），也称为函数对象，是通过重载operator()运算符使得类对象可以像函数一样被调用的技术。它常用于STL算法中，提供灵活且可定制的操作逻辑。

仿函数设计出来是用来替代函数指针的。

template<class T>
struct greater 
{bool operator()(const T& l, const T& r) const {return l > r;}
};template<class T>
struct less 
{bool operator()(const T& l, const T& r) const {return l < r;}
};

优先级队列（priority_queue）：

优先级队列（priority_queue）是C++标准库中的容器适配器，它基于堆数据结构实现，能够保证队列头部始终是最大（默认）或最小值的元素。

底层的数据结构实际为堆（Heap）。

#include <queue>
priority_queue<int> pq; // 默认大顶堆
priority_queue<int, vector<int>, greater<int>> min_pq; // 小顶堆

PS：

Compare 进行比较的仿函数 less->大堆
Compare 进行比较的仿函数 greater->小堆

//compare进行比较的仿函数 less->大堆
template<class T, class Container = vector<T>, class Compare=std::less<T>>
class priority_queue
{
public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first!=last){_con.push_back(*first);++first;}//建堆for (int i = (_con.size()-1-1)/2;i>=0;--i){adjust_down(i);}}void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent] ,_con[child])) { //默认less 向上调整建大堆std::swap(_con[child] , _con[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size()-1);}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()) {//选出左右孩子大的那一个 默认less 向下调整建小堆if (child + 1 < _con.size() && com(_con[child],_con[child+1])) {++child;}if (com(_con[parent], _con[child])) {std::swap(_con[child] , _con[parent]);parent = child; child = parent * 2 + 1;}else {break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T &top()const{return _con[0];}private:Container _con;
};

代码几乎都是前面写过的，关键是C++让其封装起来了。

代码还是有几个要注意的点：

STL库里面priority用greater(大于) 比较建立小堆，less(小于)比较建立小堆。所以这里要跟标准库里面保持一致，所以要注意比较时，代码的顺序。

而这里影响位置顺序的地方在向上调整和向下调整的函数上。

void adjust_up(size_t child)
{Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent] ,_con[child])) { std::swap(_con[child] , _con[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}void adjust_down(size_t parent)
{Compare com;size_t child = parent * 2 + 1;while (child < _con.size()) {if (child + 1 < _con.size() && com(_con[child],_con[child+1])) {++child;}if (com(_con[parent], _con[child])) {std::swap(_con[child] , _con[parent]);parent = child; child = parent * 2 + 1;}else {break;}}
}

构建堆的复杂度差异：

自底向上建堆：时间复杂度为 O(n)，因为大多数节点位于低层。
自顶向下建堆：时间复杂度为 O(n log n)，因为每个元素插入时都可能需要 O(log n) 调整。

所以这里使用自底向上建堆。

_con[parent] > _con[child]
等价于 
_con[child] <  _con[parent] _con[parent] < _con[child]
等价于 
_con[child] >  _con[parent]

这里写法顺序的不同，会导致代码的意思不同。这里要跟库里面最好保持一直。库里面是greater(大于)建立小堆，所以这里 > 保持不变的情况下，_con[parent] 要放在左边， _con[child] 要放在右边 (自顶向下建堆) 。

根据代码的意思就可以知道，如果 _con[parent] > _con[child]，则交换父子节点的数据，那么一直到根节点，数据变成了上面下，下面大的结构，就建成了小堆。同理如果是 _con[child] > _con[parent]，则变成了数据上面大，下面小的结构，会建成大堆。

双端队列：

栈：

队列：

仿函数：

优先级队列（priority_queue）：

相关文章：