【C++篇】STL适配器（上篇）：栈与队列的底层（deque）奥秘
【C++篇】STL适配器（上篇）：栈与队列的底层（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() | 构造空的队列 |
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再适合不过了
完~
腾讯云开发者
