栈，一种操作受限的线性表，只允许在一端实现插入和删除
注:形状和操作，非常类似我们一叠累起来的盘子
1.为什么要使用栈呢，这种操作受限的线性表，直接使用数组和链表不就行了，操作多而且更灵活？
答:使用功能上，确实能用数组和链表代替栈，但是特定的数据结构是对特定的场景的抽象，而且数组链表暴露了太多操作接口，操作上灵活了，使用上就不可控，自然更容易出错
注:存在有意义，术业有专攻，更加高效低错，也说明了栈是继承抽象的具体使用，数组和链表是抽象
2.使用场景和实现栈
答:只在某数据集合，只在某一端插入删除数据，且具有后进先出(逆序)特性，可用栈实现，数组结构的栈叫顺序栈，链表结构的栈叫链式栈
3.动态扩容的顺序栈
答:原理直接来自动态扩容数组，空间不够时，申请更大空间，然后copy数据过去，由此可知，入栈时间复杂度最好o(1)，最差o(n)因为是要扩容搬迁，但平均是o(1)，可用均摊法论证(大多数情况o(1)极少情况o(n))
注:设满栈k，申请新空间2k，入栈操作k+k，平摊o(1)
4.栈的操作出栈入栈
只支持入栈出栈操作，而且可由数组链表实现，故确实是一个操作受限的线性表结构，最大特点后进先出
注:top指针一直是虚指向，故
arr[top++]=x;
arr[--top]=x;
5.栈的经典使用
a.栈在函数调用中应用
执行按照先输入后执行，先执行的函数只有等到内部调用的其他函数都执行后才能执行(jvm内存管理中有堆栈概念，方法栈就用来存局部方法和方法中的局部变量)，递归实现也是，被调用函数的局部变量的作用域也是(局部方法调用时，被调用函数中变量建立，被调用函数结束时，复位给调用函数)，递归
b.栈在表达式求值中应用
运算符有优先次序，需要逆序，双栈实现
入栈规则:数据栈直接入栈，运算栈仅优先级越高才进(可保证优先输出)
出栈规则:仅当运算栈不能进入(运算符入栈低于等于栈内运算符)时，弹出运算栈，直到能进入为止；此时数字栈两个一弹出，执行后数字存入数字栈
括号处理:可以把右括号看成是优先级最高
c.栈在括号匹配中应用
右左入栈，右出栈，判空
6.浏览器前进后退操作实现原理
你要实现在一系列进栈出栈操作中，一直保存这几个页面，就需要对入栈x存，出栈y存，故需要双栈实现，栈x负责后退弹出，栈y负责前进弹出
注:
负责页面前进操作逆序，退出操作逆序，需双栈
栈x负责用户查看入栈，退后操作出栈；
栈y负责x出栈的数据入栈，前进操作出栈
双向链表也可以实现同样功能
