C++ STL 适配器：stack & queue，从 vector/list 到 deque 深度解析- 惊觉

一、什么是容器适配器（adapter）

适配器不是独立容器！ 适配器本身不存储数据，它只是对已有容器做一层包装，对外提供一套新的接口，限制原有容器的功能，只暴露我们需要的操作。

一句话总结：适配器 = 包装已有容器，改变接口，复用底层存储。

STL 中典型容器适配器：

stack 栈：后进先出 LIFO
queue 队列：先进先出 FIFO
priority_queue 优先队列（堆）

语法原型：

template< class T, class Container = deque<T> >
class stack;

template< class T, class Container = deque<T> >
class queue;

第二个模板参数就是底层适配容器，可以手动指定，默认是deque。

源码比较简单，我们就直接写了，一会可以直接看分析：

stack：

#ifdef STACK_H
#define STACK_H

#include<iostream>
#include<queue>
using namespace std;

namespace st
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		stack() = default;

		void push(T x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		size_t size()const
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}
		T& top()
		{
			return _con.back();
		}
		const T& top()const
		{
			return _con.back();
		}

	private:
		Container _con;
	};
}

#endif

queue:

#ifdef QUEUE_H
#define QUEUE_H

#include<iostream>
#include<queue>
using namespace std;

namespace qu
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		queue() = default;

		void push(T x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
		size_t size()const
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}
		T& top()
		{
			return _con.front();
		}
		const T& top()const
		{
			return _con.front();
		}

	private:
		Container _con;
	};
}

#endif

二、stack 适配 vector /list，对比优缺点

stack 需要的底层容器必须支持的操作： push_back、pop_back、back、empty、size。只要支持尾插、尾删、取尾部元素，就可以作为 stack 底层容器。

1. stack + vector

stack<int, vector<int>> st;

✅ 优点

连续内存，缓存命中率极高，CPU 预读友好，访问速度快。
内存紧凑，无额外节点指针开销，内存占用小。
随机访问能力底层自带（只是 stack 适配器把 [] 接口屏蔽了）。

❌ 缺点

vector 是动态数组，扩容代价大：容量不够时，重新开辟一块更大连续内存，拷贝全部旧元素，释放旧内存。
只能尾部高效增删；如果底层 vector 容量过剩，不会自动收缩内存，存在内存浪费。
大量频繁 push/pop，反复触发扩容时性能抖动明显。

2. stack + list

stack<int, list<int>> st;

✅ 优点

按需分配节点，没有扩容拷贝问题，每次 push 只 new 一个节点，内存不会一次性预分配大块空间。
没有容量概念，不会出现扩容拷贝。

❌ 缺点

非连续内存，每个节点附带前后指针，内存开销大；内存碎片化，缓存失效严重，遍历 / 访问慢。
频繁 new/delete 节点，内存分配开销高于 vector。
list 本身支持头尾插入删除，但 stack 只用尾部能力，list 的能力被浪费。

小结：栈场景，少量元素、频繁扩容场景选 list；元素多、追求访问速度优先选 vector。但 STL 默认 stack 不用 vector 也不用 list，而是 deque。

三、queue 适配 vector /list，对比优缺点

queue 要求底层容器支持：push_back（队尾入队）、pop_front（队头出队）、front、back。 👉 重点：vector 不能用作 queue 底层容器！

1. queue + vector ❌ 不推荐，甚至不能直接用

vector尾插 O (1)，但是头部删除 pop_front 是 O (n)。删除头部元素，后面所有元素全部向前挪动。如果队列元素很多，每次出队代价极高。

所以 queue 不适合 vector。

2. queue + list ✅ 合法

queue<int, list<int>> q;

✅优点 list 头尾增删都是 O (1)，完美满足 queue 入队、出队需求，没有移动元素开销。

❌缺点同样是链表：节点带指针，内存碎片，缓存差，访问速度慢，频繁分配释放节点开销。

问题来了： stack 可以用 vector，queue 不能用 vector；list 两者都能用但是缓存差。那有没有一种容器：头尾增删都是 O (1)，同时尽可能保持连续内存，缓存友好？ 答案：deque 双端队列，也就是 stack、queue默认底层容器。

四、deque（double-ended queue）双端队列详解

deque：双端队列，支持两端高效插入删除，也支持随机访问[]，但是不是整块连续数组！ 很多初学者误区：deque 不是一个大连续数组，这点和 vector 完全不同。

核心特性

支持 push_back / pop_back 尾操作 O (1)
支持 push_front / pop_front 头操作 O (1)
支持随机访问 deq[i]，时间接近 O (1)
中间插入 / 删除效率很差 O (n)，和 vector 一样，需要挪动元素
扩容：不需要拷贝全部旧元素！这是对比 vector 最大优势

deque 采用分段连续数组 + 中控数组（map）的结构：

buffer（缓冲区）：一块一小块的连续内存块（固定大小数组，叫数据块），每块 buffer 存放若干元素。
中控 map：是一个指针数组，里面每一个指针，指向一块 buffer。map 本身是动态数组。

中控map（指针数组）
[ptr0][ptr1][ptr2][ptr3]
  ↓     ↓     ↓     ↓
buffer0: [ 1 ][ 2 ][ 3 ]
buffer1: [ 4 ][ 5 ][ 6 ]
buffer2: [ 7 ][ 8 ][ 9 ]
buffer3: [10 ][11 ][12]

其实简单点就是:先看看buff1里面是不是，不是的话就buff2开始从头开始直接找。

ifference_type buf = last - cur;
if(i < buf)
{
    // 目标还在当前这块buffer内部，直接cur += i，不用换块
    cur += i;
}
else
{
    // 跨buffer，减掉当前buffer剩余元素，跳到下一个buffer
    i -= buf;
    // 切换到下一块buffer
    node++;
    cur = first;
    last = *(node) + buffer_size;
    // 循环，直到i落在当前buffer里面
}

可视化解释：每一块 buffer 内部内存连续；但是 buffer 和 buffer 之间不连续。中控数组保存每一块 buffer 的起始地址。访问 deq [i] 时：

通过 i 算出落在哪一块 buffer（找 map 里对应的指针）
再在该 buffer 内部偏移找到元素。

graph LR
    subgraph deque中控map(中控map:指针数组)
        p0[ptr0]
        p1[ptr1]
        p2[ptr2]
        p3[ptr3]
    end
    p0 --> B0[buffer0<br/>[1, 2, 3]]
    p1 --> B1[buffer1<br/>[4, 5, 6]]
    p2 --> B2[buffer2<br/>[7, 8, 9]]
    p3 --> B3[buffer3<br/>[10,11,12]]

deque 扩容机制（重点！对比 vector）

vector 扩容：开辟更大整块连续内存，拷贝全部元素，释放旧整块内存，大容器扩容开销巨大。

deque 扩容：

当后端 buffer 用完：单独申请一块新 buffer，把新 buffer 地址存入中控 map，原有所有 buffer 数据完全不动，不需要拷贝旧元素！
前端空间用完：直接在前面新增一块 buffer，map 数组前面插入指针，头部新增元素。

这就是为什么push_front效率很高！

⚠️ 但是中控 map 本身也是数组，如果 map 满了，需要对中控 map 扩容。但是 map 只存指针，指针大小很小，拷贝开销远小于拷贝容器里面的数据元素。

deque 随机访问原理

deque[idx]

每个 buffer 固定元素个数（如 512 字节一块，看元素类型）
计算 idx /buffer_size → 得到是第几块 buffer，拿到 map 中对应 buffer 起始地址
计算 idx % buffer_size → 在当前 buffer 内部偏移，取出元素

不是真正 O (1)（多一次指针寻址），但是速度很快，远快于 list。

五、deque 优缺点深度分析

✅ 优点

头尾插入删除都是 O (1)，完美适配 stack 和 queue！ stack 只用尾操作；queue 头尾都要操作，deque 天生适合。
扩容不需要迁移已有元素，避免 vector 大规模拷贝的性能灾难。
支持随机访问[]，list 不支持。
内存按需分段申请，不会一次性申请巨大连续内存。内存利用率比 vector 好，vector 会预分配多余 capacity。

❌ 缺点

分段存储，不是整块连续内存。跨 buffer 访问会出现缓存失效，连续遍历性能略低于 vector。
存在两层寻址（中控 map + buffer），随机访问比 vector 稍微慢一点点。
中间位置插入删除 O (n)，需要移动后面元素，不适合频繁中间增删场景。
多一层 map 管理，少量元素场景，内存有少量额外开销（中控指针数组）。

为什么 stack /queue 默认底层容器选 deque？

综合权衡：

stack 只需要尾增删：vector 也可以，但 vector 扩容拷贝代价高；deque 扩容不用拷贝元素。
queue 需要头 + 尾增删：vector 头部删除 O (n) 直接淘汰；list 缓存太差。 👉 deque 兼顾：两端高效操作 + 支持随机访问 + 扩容无元素拷贝，是 stack、queue 适配器最优折中方案。

一句话总结选型：

需要大量随机访问，很少头尾插入 → vector
任意位置频繁增删，不关心随机访问 → list
只在头尾增删，偶尔随机访问，不想扩容拷贝元素 → deque（stack/queue 默认）

六、总结

stack、queue 本质只是容器适配器，本身不存储数据，只是封装底层容器接口。

vector 适合连续存储，但头部删除低效、扩容需要拷贝全部元素，queue 无法使用。
list 双向链表，头尾 O (1)，但内存碎片化，缓存差，没有随机访问。
deque 分段数组 + 中控指针数组，分段连续，头尾增删 O (1)，扩容不需要迁移原有数据，牺牲一点点连续遍历性能换取两端操作能力，因此成为 stack、queue 的默认底层容器。

误区纠正：很多人以为 stack/queue 是独立容器，实际上只是对 deque 做接口限制，屏蔽了中间插入、随机访问等接口，只保留栈 / 队列需要的操作。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/chenbingjie_c/article/details/167282960

C++ STL 适配器：stack & queue，从 vector/list 到 deque 深度解析