1.栈概述

栈是一种特殊的线性表

1.1.栈的定义

栈是一种特殊的线性表，栈的进栈和出栈操作限制在线性表的一端进行。允许进栈和出栈的一端称为栈顶，另一端称为栈底。例如下图所示：

1.2.栈的操作

栈有以下基本运算：

（1）create：创建栈

（2）push：入栈，将新元素插入栈中，使之成为栈顶元素

（3）pop：出栈，返回栈顶元素值，删除栈顶元素

（4）top：返回栈顶元素值，不进行出栈操作。

（5）isEmpty：判断栈是否为空

1.3.栈的使用场景

适用于先进后出的场景，比如有效括号的匹配、递归实现等。

2.栈的数组实现

栈的元素存放在连续存储空间的数组中。例如下图所示：

数组index为0的元素是栈底，是不变的。而栈顶是动态变化的。

2.1.进栈操作——push

将新的元素An放入栈顶后一个位置，并成为新的栈顶。如下图所示：

当栈深度达到maxSize后，数组需要resize进行扩容。

入栈操作时间复杂度为O(1)

2.2.出栈操作——pop

将栈顶元素删除，栈顶指针指向前一个元素。例如下图所示：

出栈操作时间复杂度为O(1)

3.栈的链表实现

为了解决数组带来空间浪费的问题，可以使用链表来实现栈。例如下图所示：

栈顶相当于头节点，栈底为尾结点，出栈和入栈的时间复杂度都是O(1)。