算法网课笔记（四）——栈

栈

先进后出，后进先出，栈是一种操作受限的线性表，只允许在一段插入和删除

如何实现一个栈

顺序栈：用数组实现的栈 链式栈：用链表实现的栈

# 创建一个栈的class # 定义入栈和出栈操作

空间复杂度：入栈和出栈都是O(1) 时间复杂度：即使是支持动态扩容的栈，按照均摊时间复杂度算，也是O(1)

函数调用栈

操作系统会给每个线程分配一块独立的内存空间，这块内存被组织成栈结构，用来存储函数调用时的临时变量。每进入一个函数，先将其需要的临时变量作为一个栈帧入栈，当函数执行完成，返回值后，将该函数对应的栈帧出栈。

int main() { int a = 1; //a入栈 int ret = 0; //ret入栈 int res = 0; //res入栈 ret = add(3, 5); //为add开辟栈空间，然后调用add res = a + ret; printf("%d", res); reuturn 0; } int add(int x, int y) { //y入栈，x入栈 int sum = 0; //sum入栈 sum = x + y; return sum; }

栈在表达式求值中的应用

编译器如何利用栈实现表达式求值？ 对于四则运算34+13*9+44-12/3，需要利用2个栈来实现运算： （1）开辟2个栈，一个用于保存操作数，一个用于保存运算符 （2）从左到右遍历算是，遇到操作数，入栈 （3）遇到运算符，先与位于栈顶的运算符比较优先级 （3.1）如果优先级高于栈顶运算符，则继续入栈 （3.2）如果优先级低于等于栈顶运算符，则取出栈顶运算符，和其所需的操作数，进行计算，并且将计算结果压回操作数栈中。

栈在括号匹配中的应用

利用栈来检查表达式中括号是否匹配 思路：用栈来保存未配对的括号，当配对成功时将这对括号弹出，最后栈空则为匹配

用栈实现浏览器的前进后退功能

利用2个栈即可，一个保存“前边”的浏览记录，一个保存“后边”的。

思考题

1.为什么用栈保存函数调用的临时变量，而不是其他数据结构？ 答：只要是满足“后进先出”的数据结构都可以，目的是在函数调用时，通过后进先出机制来创造一个新的“作用域”，即“一段栈空间”，以此来保证，函数调用结束后，通过将栈顶复位，来回到上一个作用域（即调用函数之前的作用域）。

2.JVM内存管理中的“堆栈”和数据结构中的“栈”有什么区别？ 答：

leetcode

20,155,232,844,224,682,496