提问时间到

  • C++中stack /queue是容器么？

——不是，STL中栈/队列往往不被归类为容器，而被归类为container adapter（容器适配器）。

  • 我们使用的stack/deque是属于那个版本的STL？

——SGI STL

  • 我们使用的STL中stack/deque是如何实现的？

——栈是以底层容器完成其所有的工作，对外提供统一的接口。
SGI STL栈的底层结构默认是deque。deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。
我们也可以指定vector为栈的底层实现，初始化语句如下：
std::stack<int, std::vector > third; // 使用vector为底层容器的栈
SGI STL中队列一样是以deque为缺省情况下的底部结构。
也可以指定list 为起底层实现，初始化queue的语句如下：
std::queue<int, std::list> third; // 定义以list为底层容器的队列

  • stack 提供迭代器来遍历stack空间么？

——先进后出的原则，所以不提供
——对外提供统一接口，所以也不能使用迭代器。
——队列 先进先出的数据结构，同样不允许有遍历行为，不提供迭代器,

  • 栈里面的元素在内存中是连续分布的么？

——陷阱题！

  • 陷阱1：栈是容器适配器，底层容器使用不同的容器，决定栈内数据在内存中是不是连续分布。
  • 陷阱2：缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？答案是：不连续的。

can u give an answer？

科普时间

C++中的STL

STL=标准模板库
目前有三个最为普遍的STL版本：

  1. HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
  2. P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
  3. SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

下文介绍的是SGI STL中的栈数据结构。

栈/队列

栈/队列的实现

image.png

  • 栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则

所以栈不提供走访遍历功能，也不提供迭代器(iterator)。

  • 队列同理。

    底层容器

    image.png
    栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的

    可插拔：可控制使用哪种容器来实现栈的功能

SGI STL栈的底层结构默认是deque。deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。
我们也可以指定vector为栈的底层实现，初始化语句如下：
std::stack<int, std::vector > third; // 使用vector为底层容器的栈

递归

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
PS：在企业项目开发中，尽量不要使用递归！在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归（或者递归层级过深），造成栈溢出错误（这种问题还不好排查！）**

优先队列

定义

优先级队列是一种常见的数据结构，在《STL源码剖析》中给出的定义是：priorty_queue是以个带权值观念的queue，它允许加入新元素，移除旧元素，审视元素值等功能。
优先级队列中的元素并非依照被推入队列的顺序排列。而是自动依照元素的权值排列。缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

堆

堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。
如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
因为优先级队列的内部是用堆来维护，所以很多时候我们要使用堆的情况下会选择用优先级队列来代替，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。