第四章　栈和队列

爱心 用心 专心1 第四章第四章 栈和队列栈和队列 栈和队列是两种重要的线性结构 从数据结构角度看 栈和队也是线性表 其特殊性存于栈和队的基本操作是线性表操 作的子集 它们是受限制的线性表 一 栈 一 栈 stackstack 栈顶 top 栈底 bottom 空栈 栈又称为后进先出 last in first out 线性表 关于栈的操作有 1 inistack s 初始化操作 设定一个空栈要 S 2 empty s 关栈空函数 空返回 true 3 push s x 入栈操作 4 pop s 出栈函数 5 gettop s 取栈顶元素函数 6 clear s 栈置空操作 7 current size s 求当前栈中元素个数函数 栈的一个重要应用是在程序设计语言中实现递归过程 递归算法作为计算机程序设计中的一种重要的算法 是较难理解的算法之一 简单地 说 递归就是编写这样的一个特殊的过程 该过程体中有一个语句用于调用过程自身 称 为递归调用 递归过程由于实现了自我的嵌套执行 使这种过程的执行变得复杂起来 其执行的流程可以用图 1 所示 图 1 递归过程的执行流程 从图 1 可以看出 递归过程的执行总是一个过程体未执行完 就带着本次执行的结果 又进入另一轮过程体的执行 如此反复 不断深入 直到某次过程的执行遇到终止 递归调用的条件成立时 则不再深入 而执行本次的过程体余下的部分 然后又返回到上 一次调用的过程体中 执行其余下的部分 如此反复 直到回到起始位置上 才最 终结束整个递归过程的执行 得到相应的执行结果 递归过程的程序设计的核心就是参照 这种执行流程 设计出一种适合 逐步深入 而后又逐步返回 的递归调用模型 以解决实 际问题 爱心 用心 专心2 利用递归调用程序设计技术可以解决很复杂但规律性很强的问题 并且可以使程序变 得十分简短 它经常出现在以下几个方面 1 有很多数学函数是递归定义的 如 1 阶乘函数 1 n 0 fact n n fact n 1 n 0 2 菲波拉契数列 Fibonacci 0 n 0 fib n 1 n 1 fib n 1 bib n 2 其它情形 3 阿克曼函数 Ackerman n 1 m 0 ack m n ack m 1 1 n 0 ack m 1 ack m n 1 其它情形 2 有的数据结构本身固有的递归特性 如 二叉树 广义表等 3 还有一类问题 虽则问题本身没有明显的递归结构 但用递归求解比迭代求解更简 单 如 八皇后问题 汉诺塔 Hanoi 问题等 例 4 1 利用递归调用手段编程计算 N 分析 根椐数学知识 1 1 正整数 N 的阶乘为 N N 1 N 2 2 1 该阶乘序 列可转换为求 N N 1 而 N 1 以可转换为 N 1 N 2 直至转换为 2 1 而 1 1 源程序如下 例程见 exm 4 1 pas program exm4 1 var n integer y real function fac n integer real begin if n 0 then fac 1 else fac n fac n 1 end begin write N readln n y fac n writeln n y 1 0 readln end 在函数 fac 中 当 N 1 时 又调用函数 fac 参数为 N 1 这种操作一直持续到 N 1 为止 例如当 N 5 时 fac 5 的值变为 5 fac 4 求 fac 4 又变为 4 fac 3 当 N 1 时递归停止 逐步返回到第一次调用的初始处 返回结果 5 4 3 2 1 即 5 爱心 用心 专心3 练习一 利用递归调用技术求菲波拉契数列的第 N 项 例 4 2 相传在古印度的布拉玛婆罗门圣庙的僧侣在进行一种被称为汉诺塔的游戏 其装置是一块铜板 上面有三根杆 编号 A B C A 杆上自下而上 由大到小按顺序串 上 64 个金盘 如图 3 游戏的目标是把 A 杆上的金盘全部移到 C 杆上 并仍原有顺序叠 好 条件是每次只能移动一个盘 并且在每次移动都不允许大盘移到小盘之上 现要求利 用递归调用技术给出 N 个盘从 A 杆移到 C 杆的移动过程 图 3 N 阶汉诺塔 分析 这个移动过程很复杂与烦琐 但规律性却很强 使用递归调用技术来解决这个 移动过程 先得找到一个递归调用模型 想要得到汉诺塔问题的简单解法 着眼点应该是 移动 A 杆最底部的大盘 而不是其顶部的小盘 不考虑 64 个盘而考虑 N 个盘的一般情况 要想将 A 杆上的 N 个盘移至 C 杆 我们可以这样设想 1 以 C 盘为临时杆 从 A 杆将 1 至 N 1 号盘移至 B 杆 2 将 A 杆中剩下的第 N 号盘移至 C 杆 3 以 A 杆为临时杆 从 B 杆将 1 至 N 1 号盘移至 C 杆 我们看到 步骤 2 只需移动一次就可以完成 步骤 1 与 3 的操作则完全相同 唯一区 别仅在于各杆的作用有所不同 这样 原问题被转换为与原问题相同性质的 规模小一些 的新问题 图 4 即 HANOI N A B C 可转化为 HANOI N 1 A C B 与 HANOI N 1 B A B 其中 HANOI 中的参数分别表示需移动的盘数 起始盘 临时盘与终止盘 这种转换直 至转入的盘数为 0 为止 因为这时已无盘可移了 这就是需要找的递归调用模型 图 4 N 1 阶汉诺塔 源程序如下 例程见 exm 4 2 pas program exm4 2 爱心 用心 专心4 var a b c char n byte procedure hanoi n byte a b c char begin if n 0 then begin hanoi n 1 a c b writeln Move a to c hanoi n 1 b a c end end begin a A b B c C write N readln n hanoi n a b c readln end 如果说例 1 求 N 无法体现递归算法的独特优点的话 那么 上 HONOI 塔的解法则很 能说明问题 因为一般的算法是很难解决这个问题的 而过程 HONOI 只用了 4 个语句就解 决这个难题 不过要说明的是 按照汉诺塔的移动原则 将 N 个盘从 A 杆移动到 C 杆需要 移动盘的次数是 2 的 N 次幂减 1 那么 64 个盘移动次数就是 18446744073709511615 近 19 亿亿次 这是一个天文数字 即使一台功能很强的现代计算 机来解汉诺塔问题 恐怕也需要很长的时间 因此要想得到结果 在运行程序时 输入的 N 可不能太大 据说布拉玛婆罗门圣庙的僧侣声称 汉诺塔游戏结束就标志着世界末日的 到来 现在看来确实是有道理的 因为如果每秒移动一次 64 个盘则大约需近 5800 亿年 而据科学家以能源角度推算 太阳系的寿命只不过 150 亿年而已 二 队列二 队列 队列是限定在一端进行插入 另一端进行删除和特殊线性表 正象排列买东西 排在 前面的人买完东西后离开队伍 删除 而后来的人总是排在队伍未尾 插入 通常把 队列的删除和插入分别称为出队和入队 允许出队的一端称为队头 允许入队的一端称为 队尾 所有需要进队的数据项 只能从队尾进入 队列中的数据项只能从队头离去 由于 总是先入队的元素先出队 先排队的人先买完东西 这种表也称为先进先表 FIFO 表 队列可以用数组 Q 1 来存储 数组的上界 即是队列所容许的最大容量 在队列 的运算中需设两个指针 head 队头指针 指向实际队头元素的前一个位置 tall 队尾指针 指向实际队尾元素所在的位置 一般情况下 两个指针的初值设为 这时队列为空 没有元素 图 1 a 画出了一 个由 个元素构成的队列 数组定义 Q 1 10 Q i i 3 4 5 6 7 8 爱心 用心 专心5 头指针 head 2 尾指针 tail 8 队列中拥有的元素个数为 L tail head 现要让排头的元素出队 则需将头指针加 即 head head 1 这时头指针向上移动一个位置 指向 Q 3 表示 Q 3 已出队 见图 1 b 如果想让一个新元素入队 则需尾指针向上移动一个位置 即 tail tail 1 这时 Q 9 入队 见图 1 c 当队尾已经处理在最上面时 即 tail 10 见图 1 d 如果还要执行入队操作 则要发 生 上溢 但实际上队列中还有三个空位置 所以这种溢出称为 假溢出 克服假溢出的方法有两种 一种是将队列中的所有元素均向低地址区移动 显然这种方 法是很浪费时间的 另一种方法是将数组存储区看成是一个首尾相接的环形区域 当存放 到 n 地址后 下一个地址就 翻转 为 在结构上采用这种技巧来存储的队列称为循环队 列 见图 2 爱心 用心 专心6 循环队的入队算法如下 1 tail tail 1 2 若 tail n 1 则 tail 1 3 若 head tail 尾指针与头指针重合了 表示元素已装满队列 则作上溢出错处理 4 否则 Q tail X 结束 X 为新入出元素 队列和栈一样 有着非常广泛的应用 例 4 3 设有 个人依次围成一圈 从第 个人开始报数 数到第 个人出列 然后 从出列的下一个人开始报数 数到第 个人又出列 如此反复到所有的人全部出列为 止 设 个人的编号分别为 1 2 n 打印出出列的顺序 分析 本题我们可以用数组建立标志位等方法求解 但如果用上数据结构中循环链的思想 则更贴切题意 解题效率更高 人围成一圈 把一人看成一个结点 人之间的关系采用链接方式 即每一结点有 一个前继结点和一个后继结点 每一个结点有一个指针指向下一个结点 最后一个结点指 针指向第一个结点 这就是单循环链的数据结构 当 人出列时 将 结点的前继结点指针指向 结点的后继结点指针 即把 结点驱 出循环链 1 建立循环链表 当用数组实现本题链式结构时 数组 a i 作为 指针 变量来使用 a i 存放下一个结 点的位置 设立指针 j 指向当前结点 则移动结点过程为 j a j 当数到 m 时 m 结点出 链 则 a j a a j 当直接用链来实现时 则比较直观 每个结点有两个域 一个数值域 一个指针域 当数到 m 时 m 出链 将 m 结点的前继结点指针指向其后继结点 2 设立指针 指向当前结点 设立计数器 计数数到多少人 3 沿链移动指针 每移动一个结点 计数器值加 当计数器值为 时 则 结点出 链 计数器值置为 4 重复 直到 n 个结点均出链为止 爱心 用心 专心7 源程序一 用数组实现单链环 例程见 exm 4 3a pas program exm4 3a const n 14 m 4 设有 14 个人 报到 4 的人出列 var a array 1 n of integer i j k p integer begin for i 1 to n 1 do a i i 1 建立链表 a n 1 j n k 1 p 0 第 n 人指向第 1 人 并置初始 repeat j a j k k 1 报数 计数器加 1 if k m then 数到 m m 人出队 计数器置 1 begin write a j 4 p p 1 a j a a j k 1 end until p n 直到 n 个人均出队为止 end 源程序二 指针实现单链环 例程见 exm 4 3b pas program exm4 3b type pointer node node record val integer link pointer end var ptr ptb pointer i j n m integer begin readln n m new ptb ptb val 1 ptr ptb 申请第 1 个结点 for i 2 to n do begin new ptr li