2.4 和队列的应用




2.4 和队列的应用

2.4 栈和队列的应用

  在日常生活中,很多问题可以归结到栈和队列的应用问题。例如,排队购物的现象就可以看做是队列。在计算机学科的应用中,栈和队列的应用就更多了,例如,编译系统、消息队列等。

2.4.1 栈的应用

  栈具有相当广泛的实际应用,例如,可以颠倒数据串的次序、为回溯算法提供支持、实现自动机等。
  1.编译应用
  栈可以应用于括号匹配、行编辑器、表达式求值、算法优先文法等编译程序中。例如,在表达式中,一般存在大、中、小三种括号,分别定义为“{}”、“[]”和“()”,要求其只能自我匹配,不能交互匹配,比如“{[()]}”、“[()()()]”等均为正确匹配,而“({]”、“(])[”、“)(]}”等均为错误匹配。使用栈检测括号是否匹配的算法描述如下:

  2.转置应用
  一串数据全部进入栈后再全部出栈,将得到一个次序完全相反的数据串,这是栈的特性之一。因此,栈可以应用于转置操作,例如,数的进制转换等。
  【例2-1】已知线性链表L,请按从表尾到表头的顺序输出元素。
  【解析】从头到尾遍历链表,同时将链表元素入栈,再依次出栈,并打印元素信息即可。其算法描述如下:

  3.迷宫问题
  迷宫问题是指在迷宫中从入口寻找出口的问题。此类问题的本质是将迷宫建模成图,将迷宫中的点建模为图中的点,将迷宫中相连并且相通的两点建模为图中的一条边,一般采用矩阵方式存储图,这样迷宫求解就转化为图的遍历,采用回溯法穷举所有从入口点到出口点之间的路径即可。
  迷宫问题求解算法中一般使用一个栈来存储访问过的顶点信息,栈中元素(即顶点信息)由顶点位置和搜索方向两部分组成,前者记载该顶点在迷宫中的位置,后者记载下一个顶点的访问方向,例如,右、下、左、上四个相连的方向,编程时可分别使用枚举类型enum表示。

2.4 和队列的应用

发表评论

Contact

北京考研中心大厦

Connect

Subscribe

最新考研资料,欢迎联系博主获取。