栈和队列原理

栈和队列原理

栈和队列是STL库里面的两个数据结构。STL有多个版本，知道STL的具体版本才能知道对应的栈和队列的实现原理。

三个常见的STL版本：

（1）HP STL

HP STL是C++ STL的第一个实现版本，而且开放源代码，其他版本的C++ STL一般是以HP 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是开源软件，源码可读性甚高。

我们一般使用的STL是SGI STL，此版本下栈和队列的实现如下：

1.栈

栈先进后出，如下图所示：

栈提供了 push 和 pop接口。所有的元素都要符合前进后出原则，所以栈不提供访问功能，也不提供迭代器，不像set 或者map 提供迭代器iterator来遍历所有元素。

栈以底层容器完成所有的工作，而底层容器是可拔插的，所以栈往往不归类为容器，而是被归类为容器适配器（container adapter）。

栈的底层实现可以是数组(vector)、链表(list)、队列(deque) 中的任意一种，主要是数组和链表。

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为低层结构。

deque是双向队列，只要封住一端，开通另一端就可以实现栈的逻辑。

其他类型的底层实现需要初始化，初始化语句如下：

//指定vector为栈的底层实现
std::stack> third;

//指定list为栈的底层实现
std::stack> third;

2.队列

队列先进先出，如下图所示：

 队列同样不允许有遍历行为，不提供迭代器，SGI STL中队列一样是以deque为缺省情况下的底部结构。

队列以底层容器完成所有的工作，而底层容器是可拔插的，所以队列也不归类为容器，而是被归类为容器适配器（container adapter）。

与栈相同，队列也可以指定vector 和 list为底层实现，初始化语句如下：

//指定vector为队列的底层实现
std::queue> third;

//指定list为队列的底层实现
std::queue> third;