从栈的操作特性上看，栈是一种”操作受限”的线性表，只允许在一端插入和删除数据。并且满足先进后出、后进先出的特性。
实现栈
栈主要包含两个操作：入栈push()，在栈顶插入一个数据；出栈pop()，从栈顶删除一个数据。
用数组实现的栈-顺序栈。
用链表实现的栈-链式栈。
空间复杂度为O(1)
时间复杂度为O(1)
动态扩容的顺序栈的入栈操作的均摊时间复杂度为O(1)
实际应用
- 函数调用栈
操作系统给每个线程分配了一块独立的内存空间，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成返回之后，将这个函数对应的栈帧出栈。 - 表达式求值
通过两个栈实现，其中一个保存操作数的栈，另一个是保存运算符的栈。从左向右遍历表达式，遇到数字就压入操作数栈；遇到操作符与运算符栈的栈顶元素进行比较，
比运算符栈顶元素的优先级高，将当前运算符压入栈；
比运算符栈顶元素的优先级低或者相同，从运算符中取栈顶运算符，从操作数栈顶取两个操作数，进行计算，把计算结果压入操作数栈。 - 匹配括号
用栈保存未匹配的左括号，从左到右依次扫描字符串。扫描到左括号压入栈；扫描到右括号，从栈顶取出一个左括号进行匹配。 - 浏览器前进&后退
两个栈实现，浏览页面依次压入栈X，后退时，从栈X中出栈，压入栈Y;前进时，从栈Y中出栈，压入栈X.
扩展
JVM内存管理中堆栈