相信大家对栈和队列的原理应该都不陌生了。队列是先进先出，栈是先进后出。如图：所以这里我列出四个关于栈的问题，大家可以思考一下。下面以C++为例。相信使用其他编程语言的同学也应该想一想自己使用的编程语言中栈和队列是什么样子的。堆栈是C++中的容器吗？我们使用的堆栈属于哪个版本的STL？我们使用的STL中栈是如何实现的呢？栈是否提供遍历栈空间的迭代器？相信这四个问题都不是那么容易回答的。因为有的同学使用数据结构停留在表面的应用上，如果问的深一点，就会感觉好像懂了，或者好像不懂。有的同学可能只知道有栈、队列等数据结构，却不知道底层实现，不知道所用的栈和队列与STL的关系。所以在这里，我正在为您扫描基础知识。首先你要知道栈和队列是STL（C++标准库）中的两种数据结构。C++标准库有多个版本。要知道我们使用的是哪个版本的STL，就可以知道对应的栈和队列的实现原理。那么我来介绍一下最常见的三个STL版本：HPSTL其他版本的C++STL一般都是基于HPSTL实现的。HPSTL是C++STL的第一个实现版本，并且是开源的。P.J.PlaugerSTL是P.J.Plauger参考HPSTL实现的，被VisualC++编译器采用，非开源。SGISTL是SiliconGraphicsComputerSystems参考HPSTL实现的，被LinuxC++编译器GCC采用。SGISTL是开源软件，源代码可读性很强。接下来介绍的栈和队列也是SGISTL中的数据结构。只有知道使用的版本，才能知道对应的底层实现。再来说说栈，栈是先进后出的，如图：栈提供了push、pop等接口，所有的元素都必须符合先进后出的规则，所以堆栈不提供访问函数，也不提供迭代器。与set或map不同的是，迭代器iterator是提供遍历所有元素的。栈使用底层容器完成所有工作，对外提供统一的接口。底层容器是可插拔的（也就是说，我们可以控制使用哪个容器来实现栈的功能）。因此，STL中的栈往往不被归类为容器，而是容器适配器（containeradapter）。那么问题来了，STL中用什么容器来实现栈呢？从下图可以看出，栈的内部结构和栈的底层实现可以是vector、deque和list，主要是数组和链表。底层实现。我们常用的SGISTL，如果不指定底层实现，deque默认是栈的默认底层结构。Deque是双向队列。只要封住一段，打开另一端，就可以实现栈的逻辑。SGISTL中队列的底层实现也是默认使用deque实现的。我们也可以指定vector作为栈的底层实现。初始化语句如下：std::stack
