数据结构-线性表-栈和队列的典型应用

栈在括号匹配中的应用

必须保证括号都是成双成对出现的

最后出现的左括号最先被匹配（LIFO）

和栈的后进先出异曲同工

每出现一个右括号就消耗一个左括号

（消耗对应着出栈）

栈在表达式求值中的应用

中缀表达式

操作数、运算符、界限符（必不可少，反映了计算的先后顺序）

后缀表达式

逆波兰表达式（运算符在两个操作数的后面）

a+b-c写成ab+c-

左优先原则：只要左边的运算符能先计算，就优先算左边的

**先出栈的是右边的操作数

基于栈计算后缀表达式是十分方便的
前缀表达式

波兰表达式（运算符在两个操作数前面）

a+b-c写成-+abc

右优先原则：只要右边的运算符能先计算，就优先算右边的

用栈来实现前缀表达式的计算

1.从右往左扫描下一个元素

2.操作数入栈

3.运算符则出栈计算

**先出栈的是左操作数，后出栈的是右操作数

用栈实现将中缀表达式转化成后缀表达式

运算符的优先级：

乘=除>加=减
左括号直接入栈

右括号弹出栈中运算符直到左括号

中缀表达式的计算（用栈实现）

1.中缀表达式转化成后缀表达式

2.再利用栈对后缀表达式求值

以上两个算法的结合

两个栈：操作数栈和运算符栈

栈在递归中的应用

函数调用的特点：最后被调用的函数最先执行结束（LIFO）

和栈的后进先出异曲同工

函数调用时，需要一个栈存储（内存中的某一片区域）

1.调用返回地址

2.实参

3.局部变量

递归：转化成属性相同，规模较小的问题

阶乘，斐波那契数列

缺点：太多层递归可能会导致栈溢出

队列的应用

在树的层次遍历中的应用

图的广度优先遍历

在操作系统中的应用

FCFS（先来先服务）

和队列的先进先出是一样的

打印数据缓冲区