栈

什么是栈？

栈就类似放盘子，盘子一块一块叠起来，如果我们拿盘子的话只能拿到刚刚放下去的盘子。

总结来说就是，先进者后出，后进者先出，的一种数据结构

栈对比数组和链表

我们从栈的特点上，我们知道它的操作对比数组和链表，受到了很强的限制，增加和修改都只有单一的方式，没有数组和链表那样的灵活性。

栈的两种实现方式

顺序栈：用数组实现的

链式栈：用链表实现的

可动态扩容的顺序栈-复杂度分析

当插入数据，顺序栈没有空间的时候，就会重新请求一块2背的内存，然后进行原来的数据的搬运，然后在插入数据。

当顺序栈的内存够用

出栈的时间复杂度都为O(1)

但是入栈的话要考虑到内存满的时候，这个时候就满足了均摊的时间复杂度了，内存还有的话，时间复杂度一直为O(1)，只有当内存满了的时候时间复杂度为O(n),但是均摊下来，时间复杂度就是O(1)

一般均摊时间复杂度=最好情况时间复杂度

栈的实际应用

栈在函数调用的应用-函数调用栈

我们知道真正执行代码的是我们的线程，每个线程都有一块独立的内存空间，这个内存就是栈这种结构，用来存储函数调用的时候的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数函数执行完成，返回之后，将这个函数的对应的栈帧出栈

int main(){
	int a = 1;
	int ret = 0;
	int res = 0;
	ret = add(3,5);
	res = a + ret;
	return 0;
}

int add(int a,int y){
	int sum = 0;
	sum = x + y;
	return sum;
}

栈图

栈在数学计算的应用

通过两个栈实现，一个栈保存数据，一个栈保存运算符

从左到右识别，遇到数字就直接入栈，遇到运算符，如果栈为空就直接入栈，如果不为空，就和栈顶运算符比较优先级。

如果栈顶的优先级高，就压入栈；如果低，就取出两个数字进行计算，然后把数据继续压入，继续判断

括号匹配

{}()[}]例如这种

直接从左向右扫描，如果出现了一个括号就把这个括号入栈，继续从左向右扫描，如果发现了匹配的值就，吧之前的出栈，如果没有找到就是不匹配括号的。

浏览器的前进和后退

浏览器的前进和后退就是利用了两个栈，x是浏览的记录，当后退的时候，x出栈，y入栈，当访问新的界面会先清空y