栈的应用：括号匹配，递归

1.栈的应用

1.括号匹配问题

①可用栈实现该特性：最后出现的左括号最先被匹配（LIFO)。
②出栈：每出现一个右括号，就“消耗”一个左括号。
③匹配失败情况：左括号单身；右括号单身；左右括号不匹配。

算法实现

①定义顺序栈（也可以动态使用链栈实现）：

②基本操作：

③检验括号合法性的函数：

2. 递归

递归就是函数调用的过程。
函数调用的特点:最后被调用的函数最先执行结束（(LIFO)

函数调用时，需要用一个栈存储:
①调用返回地址
②实参
③局部变量

栈在递归中的应用

适合用“递归”算法解决:可以把原始问题转换为属性相同，但规模较小的问题。（计算阶乘，斐波拉契数列等）

递归调用时，函数调用栈可称为“递归工作栈”。
每进入一层递归，就将递归调用所需信息压入栈顶。
每退出一层递归，就从栈顶弹出相应信息。
缺点：
①太多层递归可能会导致栈溢出。（空间复杂度变高）
②可能包含很多重复计算。

可以自定义栈将递归算法改造成非递归算法。

3.队列的应用

①树的层次遍历
②图的广度优先遍历
③在操作系统中：多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service,先来先服务)是一种常用策略。可用队列实现。
④打印机数据缓冲区