数据结构——栈和队列的应用

?1.栈在括号匹配中的应用

算法的思想如下;
1)初始设置一个空栈，顺序读入括号。

2)若是右括号，则或使置于栈顶的最急迫期待得以消解，或是不合法的情况(括号序列不
匹配，退出程序)。

3)若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性降了一级。算法结束时，栈为空，否则括号序列不匹配。

2.栈在表达式求值中的应用?

?①中缀变后缀

从左到右遍历，遇到数字直接写下来，遇到符号，优先级大的可以直接放入栈中，遇到同等优先级的先把栈中的出栈，在入栈。

②后缀变中缀?

数字直接入栈，遇到符号，取出两个栈顶元素，与符号进行运算后入栈。

③中缀变前缀

从右向左遍历中序，方法跟中缀变后缀一样，结果也要从右往左写。

④前缀变中缀

从右向左遍历前缀序列 ，方法跟后缀变中缀一样。

?3.栈在递归中的应用

递归是一种重要的程序设计方法。简单地说，若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。

它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。但在通常情况下，它的效率并不是太高。
以斐波那契数列为例，其定义为

?int Fib(int n){

????????if(n==0)

? ? ? ? ? ? ? ? return? 0；

? ? ? ? else? if(n==1)

? ? ? ? ? ? ? ? return 1;

? ? ? ? else

? ? ? ? ? ? ? ? return? Fib(n-1) + Fib(n-2);

}

4.队列在层次遍历中的应用?

?该过程的简单描述如下:

①根结点入队。

②若队空(所有结点都已处理完毕)，则结束遍历:否则重复③操作。

③队列中第一个结点出队，并访问。若其有左孩子则将左孩子入队;若其有右孩子，则将右孩子入队，返回②