一、栈：
1、定义：后进先出、先进后出。从栈的操作特性上来看， 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
2、分类：栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
3、无论顺序栈还是链式栈，存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)。不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是O(1)。
4、顺序栈：固定大小的栈，在初始化栈时需要事先指定栈的大小。当栈满之后，就无法再往栈里添加数据了。
5、链式栈：支持动态扩容的栈。
二、栈的方法：
三、栈的应用：
1、栈在函数调用中的应用：
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
2、 为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？
因为函数调用的执行顺序符合后进者先出，先进者后出的特点。比如函数中的局部变量的生命周期的长短是先定义的生命周期长，后定义的生命周期短；还有函数中调用函数也是这样，先开始执行的函数只有等到内部调用的其他函数执行完毕，该函数才能执行结束。正是由于函数调用的这些特点，根据数据结构是特定应用场景的抽象的原则，我们优先考虑栈结构。
3、栈在表达式求值中的应用：
编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。3+5*8-6这个表达式的计算过程如图所示，
4、栈在括号匹配中的应用：
假设表达式中只包含三种括号，圆括号()、方括号[]和花括号{}，并且它们可以任意嵌套。比如， {[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。现在有一个包含三种括号的表达式字符串，如何检查它是否合法呢？这里也可以用栈来解决。我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配， “[”跟“]”匹配， “{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。 LeetCode题目链接：https://leetcode-cn.com/problems/valid-parentheses/
