栈、队列与双端队列容器适配器详解
容器适配器原理
容器适配器是通过封装现有容器实现特定数据结构的功能组件。C++标准库中的stack和queue均属于此类适配器，其核心特性包括：
- 接口限制：仅暴露符合数据结构语义的操作，如stack仅提供push/pop/top接口
- 底层容器选择：默认使用deque实现，因其支持两端高效操作
- 设计模式应用：采用适配器模式转换容器接口，提升代码复用性
典型适配器对比
| 适配器类型 | 核心操作 | 适用场景 |
|---|---|---|
| stack | push/pop/top | 表达式求值、括号匹配 |
| queue | push/pop/front/back | 任务调度、广度优先搜索 |
| priority_queue | push/pop/top | 事件处理、资源调度 |
deque深度解析
底层架构
deque采用分段连续内存结构，由多个缓冲区构成。每个缓冲区大小固定（如16字节），通过中控指针数组管理。其核心特征包括：
- 支持两端O(1)插入/删除
- 随机访问效率优于list但低于vector
- 内存利用率较高，适合频繁头尾操作场景
迭代器机制
deque迭代器包含四个关键指针：
struct iterator {
T* cur; // 当前缓冲区位置指针
T* first; // 缓冲区起始地址
T* last; // 缓冲区结束地址
vector* node; // 中控指针数组位置
};
迭代器移动时需处理跨缓冲区跳转，通过node指针定位新缓冲区并更新cur指针。
扩容策略
当缓冲区满载时触发扩容：
- 中控指针数组扩容（通常翻倍）
- 迁移原有缓冲区指针至新数组
- 更新所有迭代器指向新数组
自定义容器适配器
stack实现示例
template>
class CustomStack {
public:
void push(const T& value) { container_.push_back(value); }
void pop() { container_.pop_back(); }
const T& top() const { return container_.back(); }
bool empty() const { return container_.empty(); }
private:
Container container_;
};
queue实现示例
template>
class CustomQueue {
public:
void push(const T& value) { container_.push_back(value); }
void pop() { container_.pop_front(); }
const T& front() const { return container_.front(); }
bool empty() const { return container_.empty(); }
private:
Container container_;
};
性能考量
deque相较于其他容器的优势：
- 相比vector：头插效率更高，内存碎片更少
- 相比list：支持随机访问，缓存利用率更高
- 适用于需要频繁头尾操作但无需中间插入的场景
不推荐使用场景：
- 频繁中间插入/删除操作
- 需要遍历所有元素的场景
典型应用场景
- STL标准库中的stack和queue实现
- 消息队列系统中的任务调度
- 浏览器历史记录管理
- 算法中的递归深度限制
