data structure

若要熟练掌握栈和队列 ,需要实操 。

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

假设括号序列 :([]())

可以发现右括号总是和右边 “最近” 的左括号匹配 。“最近” 表示最新 ,这和栈的思想一致 ,遇到一个左括号 push 一次 。匹配一次右括号 pop 一次,如果其中一个右括号没有匹配到,说明序列有误 。

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

假设表达式 :A+B*(C-D)-E/F

3 栈在递归中的应用

若在一个函数 、过程或数据结构的定义中又应用了它本身,则这个函数 、过程或数据结构称为是递归定义的 ,简称递归 。

递归可将一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解 ,递归策略只需少量的代码就可以描述解题过程所需要的多次重复计算 ,大大减少了程序的代码量 。但是通常情况下,效率不高 。

例如斐波那契数列 。

注意:递归模型不可循环定义 ,必须满足两条件

所以递归的精髓在于能否将原始问题转化为属性相同但规模较小的问题 。递归需要存储中间过程的工作栈,因此递归次数过多容易造成栈溢出。

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

在信息处理中有一大类问题需要逐层或逐行处理 ,这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行进行预处理 ,把处理顺序安排好,待当前层或当前行处理完毕,就可以处理下一层或下一行 。使用队列是为了保存下一步的处理顺序 。

例如二叉树的层次遍历 。

5. 队列在计算机系统中的应用

队列在计算机系统中的应用非常广泛,这里仅从两方面简述 。

  1. 解决主机与外部设备之间速度不匹配的问题 。

    缓冲区原理 。例如主机和打印机之间速度不匹配 ,若直接把输出的数据送给打印机显然是不行的(打印机反应慢,会漏掉很多数据),解决方法是设置一个打印数据缓冲区,主机把要打印的数据传到缓冲区,缓冲区满了主机就去做其他事 ;打印机从缓冲区中取数据,数据没了向主机请求 。

  2. 解决由多用户引起的资源竞争问题 。

    CPU 某一时刻只能运行一个程序,其他程序需要排队等候(就绪队列)