一、stack、queue 的接口
(一)stack 接口说明
- stack()
- 构造空的栈
- empty()
- 检测 stack 是否为空
- size()
- 返回 stack 中元素的个数
- top()
- 返回栈顶元素的引用
- push()
- 将元素 val 压入 stack 中
- pop()
- 将 stack 中尾部的元素弹出
(二)queue 接口说明
- empty():
- 检测队列是否为空
- size():
- 返回队列中有效元素的个数
- front():
- 返回队头元素的引用
- back():
- 返回队尾元素的引用
- push():
- 在队列尾部入队列
- pop():
- 在队列头部出队列
二、stack、queue 的模拟实现
(一)stack、queue 是容器适配器
虽然
stack和queue中也可以存放元素,但在 STL 中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和queue只是对其他容器的接口进行了包装,STL 中stack和queue默认使用deque。
stack、queue 底层默认容器——deque
1、deque 概念及原理
deqeue(双端队列):可以在头尾两端进行插入和删除操作,且时间复杂度为 O(1),与 vector 比较,头插效率高,不需要搬移元素;与 list 比较,空间利用率比较高。
deque 并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际 deque 类似于一个动态的二维数组,其底层结构如下图所示:
双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其'整体连续'以及随机访问的假象,落在了 deque 的迭代器身上
2、stl 中 deque 迭代器的实现(部分)
在 stl 源码实现中,下面截取了迭代器的部分,有很多知识值得学习。
1、普通迭代器和
const 迭代器实现技巧我们知道const对象的实现就是不能修改值,因此只需要在实现迭代器时针对一下->和*的返回值即可,源码库中使用两个模板参数巧妙的解决这个问题。
2、非类型模板参数在模板进阶中我们会讲到非类型模板参数的使用,使用
size_t作为参数相当于一个宏的使用。template <class T, class Ref, class Ptr, size_t BufSiz>
3、重载的复用先实现重载符号 += 接着的 +、-、-=都采用了复用的方式,使得代码更简洁。 在实现++、–时,先实现前置++,前置–,再实现后置++,后置–,这里也可以复用


