什么是栈？
写在前边
对于栈的认识，相信每个学习数据结构的小伙伴多多少少有一定的认识和了解。很多刚刚学习的小伙伴说学习数据结构在实际中没怎么见到应用，那是因为你没有去仔细的观察，而且像栈这常用到的数据结构通常会使用在实际开发中，比如：表达式的运算、花括号的匹配以及浏览器的前进后退等等很多。
这些实际开发的实现如果不去研究，你永远不知道数据结构在实际中的应用，当你学习完今天的栈数据结构时，然后去研究下实际中已经使用到的应用，才能让你在今后的实际开发中用到栈这种数据结构，从而使你的开发更加灵活、多变。
思维导图
这篇文章将要学习到的内容。
1 基本常识
1.1 什么是栈
我们用一种最简单的生活常识描述一下，比如我们往柜子里放东西，先放的东西是需要放到柜子最里边，后放的东西在柜子的最外边；如果我们要取东西，先要取柜子最外边的东西，才能取到柜子最里边的东西。这种先进后出，后进先出的结构称为“栈”。
1.2 栈的特点
“先进后出，后进先出”。
1.3 栈的操作
栈的操作就两种，分别为出栈和入栈。那我们上边的例子，我们往柜子里放东西的过程称为入栈；我们在柜子里拿东西的过程称为出栈。
PS：柜子只有一个出口和入口，而且出口和入口是一样的。如果两端都有开口，就变成了队列，后期的文章会讲到。
2 栈的实现
我们前边的文章也讲过，所有的数据结构基本都是由数组和链表演化而来的，所以今天讲的栈这种数据结构也不例外。
栈的实现主要有两种，一种是数组的实现，叫做顺序栈，另外一种是链表的实现，叫做链式栈。如下：
2.1 顺序栈
2.2 链表栈
2.3 代码实现
顺序栈（Java）
1/**
2 * 功能:基于数组的顺序栈
3 * @author:小鹿
4 *
5 */
6public class ArrayStack {
7
8 private String[] items; // 数组
9 private int count; // 栈中元素个数
10 private int n; // 栈的大小
11
12 // 初始化数组，申请一个大小为 n 的数组空间
13 public ArrayStack(int n) {
14 this.items = new String[n];
15 this.n = n;
16 this.count = 0;
17 }
18
19 /**
20 * 功能:入栈
21 * 说明:数组入栈的入口为数组尾部
22 * @param item :入栈数据元素
23 * @return:是否入栈成功
24 */
25 public boolean push(String item) {
26 // 数组空间不够了，直接返回 false，入栈失败。
27 if (count == n) return false;
28 // 将 item 放到下标为 count 的位置
29 items[count] = item;
30 //数组长度+1
31 ++count;
32 //入栈成功
33 return true;
34 }
35
36 /**
37 * 功能:出栈
38 * @return:返回出栈元素
39 */
40 public String pop() {
41 // 栈为空，则直接返回 null
42 if (count == 0) return null;
43 // 返回下标为 count-1 的数组元素
44 String tmp = items[count-1];
45 //数组长度-1
46 --count;
47 //返回出栈数据元素
48 return tmp;
49 }
50}
链式栈（Java）
1/**
2 * 功能:基本链表实现栈，入栈、出栈、输出栈
3 * @author : 小鹿
4 *
5 */
6public class StackBasedLinkedList {
7 //定义栈顶指针
8 private Node top = null;
9
10 //定义栈结点
11 private static class Node {
12 //栈结点数据域
13 private int data;
14 //栈结点指针域
15 private Node next;
16 //构造函数
17 public Node(int data, Node next) {
18 this.data = data;
19 this.next = next;
20 }
21 //get 获取数据域方法
22 public int getData() {
23 return data;
24 }
25 }
26
27 /**
28 * 功能:入栈
29 * @param value:要入栈的数据元素
30 */
31 public void push(int value) {
32 //创建一个栈结点
33 Node newNode = new Node(value, null);
34 // 判断栈是否为空
35 if (top == null) {
36 //如果栈为空，就将入栈的值作为栈的第一个元素
37 top = newNode;
38 } else {
39 //否则插入到top栈结点前（所谓的就是单链表的头插法）
40 newNode.next = top;
41 top = newNode;
42 }
43 }
44
45 /**
46 * 功能 : 出栈
47 * @return: -1 为栈中没有数据
48 */
49 public int pop() {
50 // 如果栈的最顶层栈结点为null,栈为空
51 if (top == null) return -1;
52
53 //否则执行出栈操作，现将栈顶结点的数据元素赋值给 Value
54 int value = top.data;
55 //将 top 指针向下移动
56 top = top.next;
57 //返回出栈的值
58 return value;
59 }
60
61 /**
62 * 功能:输出栈中所有元素
63 */
64 public void printAll() {
65 //将栈顶指针赋值给p
66 Node p = top;
67 //循环遍历栈(遍历单链表)
68 while (p != null) {
69 System.out.print(p.data + " ");
70 //指向下一个结点
71 p = p.next;
72 }
73 System.out.println();
74 }
75}
3 栈的性能
我们从上边学到了栈的基本结构和特点，还有栈的基本操作。如果我们学习一种数据结构，主要分析它的性能如何。还记得怎么分析数据结构性能吗？主要从两方面入手，第一，时间效率（时间复杂度）；第二，空间上的消耗（空间复杂度）。我们就从以上两个方面分析一下栈这种数据结构的性能。
3.1 时间复杂度
时间上的消耗主要分析栈的操作所消耗的时间，我们共两种操作，入栈和出栈，其实在数组中中，我们操作尾部的数据就相当于入栈和出栈，直接根据下标取得相应的元素就好（JS 中数组的 pop 和 push 方法），所以时间复杂度是 O（1）。
3.2 空间复杂度
空间复杂度的判断是所需要开辟的临时空间，顺序栈和链式栈只需要大小为 n 的空间就可以，入栈和出栈需要一个临时空间来存储变量，空间复杂度为 O(1)。
3.3 栈的动态扩容
大家有没有想过这样一种情况，如果栈满的时候，再进行入栈操作，栈内就放不下了，我们需要动态扩容。主要是顺序栈的动态扩容比较麻烦，和我么你之前的数组的文章动态扩容一样的，对于动态扩容的性能，可以自己尝试一下。
4 栈的实际应用
既然我们把栈的性能分析透了，理解透了，那么我们看看栈在实际中有哪些应用吧。
4.1 应用一 ：栈在函数中的应用
函数我们每个人再熟悉不过了，你是不是很纳闷，栈怎么会在函数中能够应用的到呢，我学了这几年函数，我咋不知道函数中还有栈的操作。
加入我们程序开始执行代码，执行到我们声明的函数时，计算机内部会发生什么呢？首先，会为该函数开辟一块临时的内存空间，这块内存空被组织成“栈”这种数据结构，作用主要用来存储函数内部声明的临时变量。
每执行一个函数，系统就将函数中的临时变量组织成栈帧，执行入栈操作，当函数被调用完成的时候，临时变量已经用不到了，所以要在内存中释放，执行出栈操作。如以下函数：
1 function main(){
2 let i = 0;
3 let j = 1;
4 i++;
5 j++;
6 console.log(i+j)
7}
8main();
具体的动画如下：
我们这时要想一个问题，那为什么函数会使用栈这种数据结构呢，为什么不用队列、链表或者其他数据结构？全体注意，重点来了，以后分析其他的问题也用到一下的方法分析。
因为函数调用的执行顺序符合后进者先出，先进者后出的特点。
比如函数中的局部变量声明的时间顺序，早先定义的变量在内存中保存的时间长，后定义的变量在内存中保存的时间短，所有有一个先后的问题。我们再去脑海中把这种问题的特点抽象成数据结构，只有使用“栈”结构，才符合这种问题。
4.2 栈在表达式中应用
计算机中数字的运算也是使用栈这种数据结构的，我们举个例子，我们要计算如下表达式：
1 + 2 × 4 - 6
如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。动画如下（动图太大，我把它拆分成两部分了）：
4.3 其他应用
关于栈的应用，还有很多，比如花括号的匹配问题，有关练习去 LeedCode 实践。这里就不多举例子。