【C++篇】STL适配器（上篇）：栈与队列的底层（deque）奥秘-海口c网

【C++篇】STL适配器（上篇）：栈与队列的底层（deque）奥秘

article/2025/7/5 18:58:03

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对C++感兴趣的朋友

文章目录

- 前言
- - 一、何为适配器？
  - 二、容器适配器
  - 三、stack的介绍和使用
  - - 模拟实现stack
  - 四、queue的介绍和使用
  - - 模拟实现queue
  - 五、deque双端队列
  - - 1. deque的原理介绍
    - 2. deque的缺陷

前言

本文，我们接着学习STL的适配器。C++中的适配器主要分为三类：容器适配器、迭代器适配器及函数适配器。

本阶段我们重点学习容器适配器和迭代器适配器。

适配器的内容我将分为两篇文章进行讲解，主要内容为：

上篇（本文）：栈stack和队列queue
下篇：优先级队列priority_queue和反向迭代器reverse_iterator

【本文目标】

了解什么是容器适配器
学会使用stack、queue
了解stack、queue的默认底层容器——deque
能够模拟实现stack、queue

一、何为适配器？

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总
结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

在这里插入图片描述

【核心思想】

复用：通过封装已有功能，避免重复实现

二、容器适配器

基于现有容器（如 deque、list 或 vector）实现，提供特定的接口。
常见的容器适配器：
- 栈stack：后进先出（LIFO），默认基于 deque（也是一个容器，后文会讲解）。
- 队列queue：先进先出（FIFO），默认基于 deque。
- 优先级队列priority_queue：优先级队列（堆），默认基于 vector。

三、stack的介绍和使用

在我们在学习初阶数据结构的时候已经掌握了stack和queue的物理和逻辑结构并用C语言模拟实现，若有遗忘，一定要及时复习：【初探数据结构】线性表——栈与队列（代码实现与详解）

在这里插入图片描述
在C++中，我们的STL库中已经有它们了，以后我们使用的时候直接调用接口即可，非常方便！终于不用再像C语言那样手搓一个栈了😭

接口记不住就查阅文档，用多了自然就记住了stack文档介绍

常用接口：

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

看到这里可以去刷一些stack的题哦

模拟实现stack

我们先来凑一眼stl库的源代码

值的一提的是，很多小伙伴都说源代码看不懂，太晦涩了。其实我也看不懂（我是个小菜鸡😁），不必焦虑，我们仍在学习的过程中，我相信我们只要不断地坚持学习，看懂只是时间问题。

看不懂为什么还要看呢？
其实我们并不需要完全看懂，我们只需要提取关键信息（成员变量和成员函数），知道他在干什么就可以了。

#ifndef __SGI_STL_INTERNAL_STACK_H
#define __SGI_STL_INTERNAL_STACK_H__STL_BEGIN_NAMESPACE#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class stack {friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:typedef typename Sequence::value_type value_type;typedef typename Sequence::size_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;
protected:Sequence c;
public:bool empty() const { return c.empty(); }size_type size() const { return c.size(); }reference top() { return c.back(); }const_reference top() const { return c.back(); }void push(const value_type& x) { c.push_back(x); }void pop() { c.pop_back(); }
};template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {return x.c == y.c;
}template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {return x.c < y.c;
}__STL_END_NAMESPACE

我们可以看到：

他的模板信息：一个类型 + 一个容器（默认为deque）
成员变量：一个容器对象
成员函数实现方式：调用容器接口实现功能

有这些信息就够了，我们已经可以自己实现它们了！

#pragma once#include<iostream>
#include<deque>
#include<list>
#include<vector>using namespace std;namespace zhh
{template<class T, class Con = deque<T>>class stack{public:void push(const T& x){_c.push_back(x);}void pop(){_c.pop_back();}T& top(){return _c.back();}const T& top()const{return _c.back();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};
}

是不是很简单，复用就是这么爽🤣

四、queue的介绍和使用

queue与stack的学习方式一样

queue文档介绍

在这里插入图片描述
常用接口：

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

模拟实现queue

我们直接在stack代码的基础上改就可以了，控制尾进头出即可。
需要注意的是，pop必须调用pop_front()，那vector没有这个接口，是不是就不能适配了？没错，容器用vector会直接报错。
那为什么不用erase，这样就都适配了呀？
那我问你，vector头删的代价大不大？queue是不是只能用头删，是没有意义的。库中也是这样实现的。

#pragma once#include<iostream>
#include<deque>
#include<list>
#include<vector>using namespace std;namespace zhh
{template<class T, class Con = deque<T>>class queue{public:void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& back(){return _c.back();}const T& back()const{return _c.back();}T& front(){return _c.front();}const T& front()const{return _c.front();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};
};

五、deque双端队列

为什么选择deque作为stack和queue的底层默认容器？

deque有何神通呢？

我们知道：

vector头插头删效率低，扩容还要更换空间
list迭代器不支持随机访问，空间不连续，CPU高速缓存效率不行

这些缺点，deque都弥补了。那为什么没有被广泛使用呢？

1. deque的原理介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构
双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)。与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比
较高。
在这里插入图片描述

其实deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的。实际deque类似于一个动态的二维数组，由一个中控（指针数组）map，每个指针指向一块空间buff

底层结构如下图所示：
在这里插入图片描述

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂。
如下图所示：

在这里插入图片描述

全貌：
在这里插入图片描述

2. deque的缺陷

相比于vector：
- 随机访问的效率不及vector
相比于list：
- 中间插入效率很低，只适合头和尾的修改

deque还有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到
某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

stack和queue需求只有头尾的修改，因此deque再适合不过了

完~