容器适配器
在模拟实现stack和queue之前我们首先要知道容器适配器是一个什么样子的概念
“容器适配器是一个封装了序列容器的一个类模板,它在一般的序列容器的基础上提供了一些不同的功能。之所以称为容器适配器,是因为它是适配容器来提供其它不一样的功能。通过对应的容器和成员函数来实现我们需要的功能。”
上面一些比较官方的解释
那么我们怎么通俗的理解容器适配器的概念呢？
实际上虽然stack和queue都可以存储数据
但是它们实际上是由其他容器封装而成的（参考迭代器）
所以说它们算不上是一个容器 只能说是一个由容器适配的适配器
Stack模拟实现
知道了容器适配器的概念之后我们再来实现下Stack
这里我们用来适配的容器叫做deque 在本文末尾会有简单的介绍
接口函数一览
代码一览
因为这里代码比较简单 只有格式上稍微要注意点 这里我就不一一解释了 大家仔细看一遍应该就都会了
namespace shy { template<class T, class Container = std::deque<T>> class myStack { public: // 入栈 void push_back(const T& x) { _con.push_back(x); } // 出栈 void pop() { _con.pop_back(); } // 获取栈顶元素 T& top() { return _con.back(); } //获取栈中有效元素个数 size_t size() const { return _con.size(); } //判断栈是否为空 bool empty() const { return _con.empty(); } //交换两个栈中的数据 void swap(mystack<T, Container>& st) { _con.swap(st._con); } private: Container _con; }; }
Queue的模拟实现
接口函数一览
代码一览
这里和stack的代码大同小异
还是一样不做过多讲解了 大家看看就好
namespace shy { template<class T, class Container = std::deque<T>> class queue { public: //入队列 void push(const T& x) { _con.push_back(x); } //出队列 void pop() { _con.pop_front(); } //获取队头元素 T& front() { return _con.front(); } //获取队尾元素 T& back() { return _con.back(); } const T& back() const { return _con.back(); } //获取队列中有效元素个数 size_t size() const { return _con.size(); } //判断队列是否为空 bool empty() const { return _con.empty(); } //交换两个队列中的数据 void swap(queue<T, Container>& q) { _con.swap(q._con); } private: Container _con; }; }
deque的简单介绍
deque的结构大概是一个这样子的状态
它由一个中控数组和一系列的小数组组成（一般大小固定为8个）
我们首先使用中间的哪个中控数组指向的地址
当我们需要尾插的时候 我们在小数组内插入元素
如果说小数组内部的元素被插入满了
那么我们的中控数组就开始指向下一个小数组继续插入数据
往前插同理
deque的优点和缺点都是均衡
它可以做到随机访问 但是访问的过程中实际上还是会经过一定的计算
它可以尽量减少空间的浪费 但是还是会不可避免的浪费掉一定的空间
所以说只有在像栈和队列这种比较需要前插和尾插效率且需要一定的内存命中率的数据结构中 deque才有一席之地
总结
本文主要介绍了Stack和queue的模拟实现以及deque的简单介绍
