栈(stack)

什么是栈？

栈是一种线性的数据结构，其是一种运算受限（限定仅在表尾进行插入和删除的线性表）的线性表。栈的结构类似下图的容器：

如上图所示，栈的结构就像一个端封闭，另一端开口的容器，往容器放入小球（对应栈中的元素），先放入的小球就越靠近容器的底部，最早进入的小球对应的位置就是栈底（bottom），最后放入的小球对应的位置就是栈顶（top），放入小球的动作就叫做入栈（push）；取出小球的时候，只能按照放入顺序相反的顺序来取，即先取后放入的，再去先放入的，每次取小球的动作就叫做出栈（pop）。由于栈的单端口进出的限制，决定了栈中的元素只能先进后出（FILO, First In Last Out）。栈的数据结构可以使用数组来实现，也可以用链表来实现，具体如下图所示：

栈的基本操作和应用

入栈（push)

入栈就是把元素存放入栈中，由于栈的结构只允许从一次存放元素，所以新元素的存入后所在的位置就是该栈新的栈顶，我们以栈的数组实现为例，入栈的过程如下图所示：

出栈（pop)

出栈就是把元素从栈中弹出，同样的由于栈结构单端进出的限制，出栈时候的元素就是栈顶对应的元素，取出元素后，出栈元素前面的那个元素对应的位置将变成新的栈顶。出栈的过程如下：

入栈和出栈的复杂度和应用场景

由于栈的后进先出的特性，使得入栈和出栈只会影响到栈中最后一个元素，不会涉及到其他元素的移动，因此入栈和出栈的时间复杂都为。同样的，栈的先入后出的特性，也使得栈不能拥有遍历、随机访问和随机插入的功能。

由于栈的特殊结构，栈常用于以下场景：

• 逆序输出：由于栈先入后出的特性，使用栈结构可以轻松实现逆序输出的操作。

• 语法检测：对于一些成对出现的符号，如"[]"、"()"等，凡是遇到符号的前半部分，即入栈（push）该符号，凡是遇到括号后半部分的，就与栈顶元素进行匹配，如果匹配成功，则出栈（pop），否则就是匹配失败，语法错误。

• 数字进制转换：顺序计算，继续结果逆序输出。

栈的应用场景还有很多，这里就不一一举例，实际上栈的应用都是基于栈的先入后出的特性。

类模板std::satck

stack类是C++标准库提供的一个容器适配器，它给使用者提供了栈的功能，实现的栈的先进后出（FILO）的数据结构，并提供了特定的函数集合，其定义如下所示：

该类模板在头文件<stack>中定义。

形参T和Container

• T：代表存储元素的类型

• Container：用于存储元素的底层容器类型。该类型必须满足序列容器的要求，同时该容器类型能够提供通常语义下的back()、push_back()和pop_back()函数。默认情况下使用标准容器std::deque。满足该要求的标准容器还有std::vector和std::list。

成员函数

元素访问

访问栈顶元素使用top()函数，该函数的定义如下：

该函返回栈中栈顶元素的引用。实际上调用的就是底层容器的back()。

栈的容量

• size：返回底层容器中的元素数 。实际上调用的就是底层容器的size()。

• empty：检查底层容器是否为空，如果为空返回true，否则false。实际上调用的就是底层容器的empty()。

栈的修改

• push：向栈中推入元素。其函数声明如下：

  


• emplace：推入新元素到栈中，与push不同的是该函数是原位构造元素（直接在容器内构造对象，不用拷贝一个复制品再使用），既不进行也不进行复制操作。其函数声明如下：

• pop：从栈中移除站定元素。实际上调用的就是底层元素的pop_back()。

• swap：交换栈与另一个栈中的内容，其函数声明如下：

用法示例

输出结果：