基本概念

栈

定义：限制仅在表的一端（表尾）进行操作（插入和删除）的线性表，一种后进先出的数据结构，LIFO(Last in First Out)
栈顶：即表尾，允许插入和删除
栈底：即表头，无法进行操作
入/出栈：即插入或删除栈尾元素，时间复杂度、空间复杂度均为O(1)
1.jpg

队列

定义：限制仅在一端进行插入操作，另一端进行删除操作的线性表。元素先进先出，FIFO(First in First out)
队头：允许插入元素的一端
队尾：允许删除元素的一端
入/出队列：即插入、删除元素
1.jpg

存储结构

栈

栈的存储分为顺序存储和链式存储。

顺序存储

顺序栈通过数组实现，数组下标为0的一端为栈底，使用top指示栈顶，默认top=-1为空栈。
顺序栈的元素个数是固定值，存在栈满的情况。
1.jpg

链式存储

链栈通过单链表实现存储，一般尾节点为栈底，使用头指针指向的节点作为栈顶，不需要头节点。top = NULL 为空栈。
链栈不存在满栈的情况，除非内存溢出。
1.jpg

队列

队列也分为顺序存储和链式存储。

顺序存储

顺序存储的队列通过数组实现，下标为0的一端为对头，通过head指向，队尾用tail指向。当head=tail时队列为空。
同样，顺序队列存储的元素数目固定。
1.jpg
顺序栈在操作过程中会出现索引越界的情况，对于次有两种处理方法：移动队列至数组头部、环形队列。
方法1：移动队列至数组头部
当tail=n时，将所有元素移至从下标0开始。
该方法入队时间复杂度为O(1)或O(n)，平均时间复杂度为O(1)；出队时间复杂度为O(1)
1.jpg
方法2：循环队列
队列头尾相合，设定(tail+1)%n == head时为满队列，即牺牲一个存储位，该方法入队、出队时间复杂度均为O(1)
1.jpg

链式存储

使用带头结点的单链表进行存储，头结点指向队头，**head**指向头结点，**tail**指向队尾。
**head**和**tail**都指向头结点时队列为空。
存储元素个数不限
1.jpg

C++实现

栈和队列是STL（C++标准库）里面的两个数据结构
C++标准库是有多个版本的

  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是开源软件，源码可读性甚高。

    栈的实现

    栈提供 push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是 set 或者 map 提供迭代器 iterator 来遍历所有元素。
    1.jpg
    栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
    所以STL中栈往往不被归类为容器，而被归类为 container adapter（容器适配器）。
    常用的SGI STL，如果没有指定底层实现的话，默认是以**deque**为缺省情况下栈的低层结构。
    deque 是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。
    SGI STL中 队列底层实现缺省情况下一样使用 **deque** 实现的。
    我们也可以指定 vector 为栈的底层实现，初始化语句如下：
    1. std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

    队列的实现

    队列是先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以 **deque** 为缺省情况下的底部结构。
    也可以指定 list 为起底层实现，初始化 queue 的语句如下：
    std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
    所以STL 队列也不被归类为容器，而被归类为 container adapter（ 容器适配器）。