【C++】STL——容器适配器 stack 深度剖析及模拟实现

1. stack的介绍及使用

1.1 stack的介绍

stack的文档介绍

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行

元素的插入与提取操作。

stack是作为容器适配器被实现的，容器适配器是使用特定容器类的封装对象作为其基础容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的“背面”（称为堆栈顶部）推/弹出。

stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下

操作：

empty：判空操作

back：获取尾部元素操作

push_back：尾部插入元素操作

pop_back：尾部删除元素操作

标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

文档中的介绍大家有些地方可能不懂，先了解一下即可，我们后面会讲到。

stack其实就是我们之前数据结构学的栈。 所以说，它的基本使用我们其实是可以直接上手的。

那我我们先来看一下它的成员函数：

🆗，那我们看到它的成员函数其实除了emplace其它的我们都是比较熟悉的。

另外，大家可能注意到，stack是不是没有迭代器啊，而我们之前学的string、vector、list都有啊，为什么呢？

我们之前学的string、vector、list都是容器，而今天要学的stack和queue 是容器适配器

那我们知道stack要保证先进后出，所以其实它不需要迭代器。

1.2 stack的使用

那我们接下来就练习一下stack的使用。

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

int main()
{
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);
    st.push(6);
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
    return 0;
}

运行一下

使用也很简单，没什么可说的，大家可以自己找一下题目做一做，下一篇文章我们也会带着大家做一些相关的题目。

2. stack的模拟实现

那接下来我们就来模拟实现一下stack：

首先大家回想一下，stack就是我们数据结构学的栈，是一种操作受限制的线性表，所以它可以用链表实现，也可以用顺序表（数组）实现，不过我们当时只实现了数组栈，因为相对而言数组的结构实现更优一些。因为数组在尾上插入删除数据的代价比较小。

所以说，如果我们现在想模拟实现stack：

那传统的写法就是和我们数据结构写的一样，用一个数组去搞。

但是呢:

既然我们是模拟实现，那我们就按库里的方式来搞，用适配器（配接器）模式来实现。

2.1 适配器模式的了解

那关于适配器模式，大家可能不了解：

不过说到适配器的话，大家应该不陌生，电源适配器大家应该都见过

就是这个，只不过我们平时可能不这么叫。

那大家知不知道，电源适配器的作用是啥？

🆗，它的作用其实是去转换电压的

无论是电脑、手机还是其它电器，充电时都无法直接使用 220V 的交流电，为了方便用户使用，各个电器厂商都会提供一个适用于自己产品的电源线，它可以将 220V 的交流电转换成适合电器使用的低压直流电。

从用户的角度看，电源线扮演的角色就是将原本不适用的交流电变得适用，因此其又被称为电源适配器。

那容器适配器呢？

那我们一开始就提到，我们学的stack是一种容器适配器，所以它也是一样的，是用来进行转换的，对已有的容器进行转换。

简单的理解容器适配器，其就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。即通过封装某个序列式容器，并重新组合该容器中包含的成员函数，使其满足某些特定场景的需要。

适配器模式：

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总

结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

所以，按照适配器模式的思想：

如果我们现在要实现一个stack（栈），我们要自己去造轮子吗？

不要，我们是不是可以考虑对已有的容器进行封装，进行一个转换啊，通过转换来满足我们的需求。

2.2 结构

所以：

怎么做呢？

增加一个参数，这个参数就是被作为封装对象的基础容器

我们看到，库里面给Container 指定的默认容器是deque，至于deque是啥，我们后面也会讲到。

当然我们也可以自己指定容器，只要它能支持这些操作：

就可以作为这里的基础容器。

2.3 成员函数

那stack的成员函数：

常见的这些接口是不是很容易就搞定了啊。

那我们的stack就写好了，测试一下：

链式栈怎么搞？

当然：

这里的Container我们最好给一个缺省值，我们说了库里面给的缺省参数是deque，deque我们还没学，我们可以先给个vector

那我们在使用的时候就可以这样写了：