什么是栈

栈是一种操作受限的线性表.基本特性是先进后出,后进先出.

栈的实现

栈可以用数组来实现叫做顺序栈,也可以用链表来实现叫做链式栈.

栈的复杂度

出栈和入栈的时间复杂度为O(1).
栈的空间复杂度为O(1),栈的空间复杂度不是指它所需要的存储空间,而是除了必须存储空间之外,算法运行所需要的存储空间.

栈在函数中的应用

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

栈在表达式求值中的应用

表达式求值,编译器是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
例:3+6×8-9=?
1. 申请两个名字为啊a 和 b的栈,a负责存储数组,b负责存储运算符.
2. 3是数组放入a中
3. +是运算符放入b中
4. 6是数字放入a中
5. ×是运算符并且优先级高于+,所以放入b中
6. 8是数字放入a中
7. -是运算符且优先级低于,所以取出b中的栈顶运算符,取出a中的两个栈顶数字8和6,进行运算 8*6=48,将48放入a中
8. 然后继续比较-和b中栈顶的优先级,此时b的栈顶运算符为+,和-是平级运算符所以取出b中的栈顶运算符+,取出a中的两个栈顶数字48和3,进行运算 48+3=51,将51放入a中.
9. 这时-放入b中
10. 9放入a中
11. 表达式进行最后的运算,51-9=42.
练习:有效括号