栈的基本知识及应用

栈的基本知识及应用栈的基本知识及应用 1 栈的概念和特性 栈的概念和特性 栈 stack 是一种特殊的线性表 作为一个简单的例子 可以把食堂里冼净的一摞碗 看作一个栈 在通常情况下 最先冼净的碗总是放在最底下 后冼净的碗总是摞在最顶上 而在使用时 却是从顶上拿取 也就是说 后冼的先取用 后摞上的先取用 好果我们 把冼净的碗 摞上 称为进栈 压栈 把 取用碗 称为出栈 弹出 那么 上例的特点是 后进栈的先出栈 然而 摞起来的碗实际上是一个表 只不过 进栈 和 出栈 都在最顶 上进行 或者说 元素的插入和删除是在表的一端进行而已 一般而言 栈是一个线性表 其所有的插入和删除均是限定在表的一端进行 允许插 入和删除的一端称栈顶 Top 不允许插入和删除的一端称栈底 Bottom 若给定一个栈 S a1 a2 a3 an 则称 a1为栈底元素 an为栈顶元素 元素 ai位于元素 ai 1之上 栈 中元素按 a1 a2 a3 an 的次序进栈 如果从这个栈中取出所有的元素 则出栈次序 为 an an 1 a1 也就是说 栈中元素的进出是按后进先出的原则进行 这是栈结构的 重要特征 因此栈又称为后进先出 LIFO Last In First Out 表 我们常用一个图来形象地表示栈 其形式如下图 通常 对栈进行的运算主要有以下几种 在使用栈之前 首先需要建立一个空栈 称建栈 往栈顶加入一个新元素 称进栈 压栈 删除栈顶元素 称出栈 退栈 弹出 查看当前的栈顶元素 称读栈 注意与 的区别 在使用栈的过程中 还要不断测试栈是否为空或已满 称为测试栈 2 栈的存储结构 栈的存储结构 栈是一种线性表 在计算机中用向量作为栈的存储结构最为简单 因此 当用编程语 言写程序时 用一维数组来建栈十分方便 例如 设一维数组 STACK 1 n 表示一个栈 其中 n 为栈的容量 即可存放元素的最大个数 栈的第一个元素 或称栈底元素 是存放 在 STACK 1 处 第二个元素存放在 STACK 2 处 第 i 个元素存放在 STACK i 处 另外 由于栈顶元素经常变动 需要设置一个指针变量 top 用来指示栈顶当前位置 栈中没有 元素即栈空时 令 top 0 当 top n 时 表示栈满 如果一个栈已经为空 但用户还继续做出栈 读栈 操作 则会出现栈的 下溢 如 果一个栈已经满了 用户还继续做进栈操作 则会出现栈的 上溢 两种情况统称为栈的 溢出 3 对栈的几种运算的实现方法 对栈的几种运算的实现方法 1 建栈 这比较简单 只要建立一个一维数组 再把栈顶指针置为零 栈的容量根据具体的应 用要求而定 比如 type arraytype array 1 n of integer var stack arraytype top integer 再在程序开始时 置 top 0 2 测试栈 测试栈顶指针的值 若 top 0 则栈空 若 top n 则栈满 3 读栈 若 top 0 则栈空 无栈顶元素可读 出错 若 top0 则回送栈顶元素的值 STACK top 4 进栈 push 将栈顶指针加 1 后 再把新元素送到栈顶 假设新元素 x 为整型 栈的最大深度为 n x 和 n 设置为值型参 而栈和栈顶指针要设置成变量型参 procedure push var stack arraytype var top integer n integer x integer begin if top n then begin writeln Stack full halt end else begin top top 1 stack top x end end 5 退栈 pop 取得栈顶元素的值后 再把栈顶指针 top 减 1 注意都用变量型参 procedure pop var stack arraytype var top integer var x integer begin if top 0 then begin writeln Stack empty halt end else begin x stack top top top 1 end end 注意 由于栈本身和栈顶指针是密不可分的 所以有时我们把他们定义成一个记录来处理 如 type stack record vec array 1 n of integer n 为栈可达到的最大深度 top integer end 则以上几种运算的实现只要稍做修改即可 procedure push var s stack x integer begin if s top n then begin writeln Stack full halt end else begin s top s top 1 s vec s top x end end procedure pop var s stack var x integer begin if s top 0 then begin writeln Stack empty halt end else begin x s vec s top s top s top 1 end end 出栈有时也可用函数实现 如 function pop var s stack integer begin if s top 0 then begin writeln Stack empty halt end else begin pop s vec s top s top s top 1 end end 栈在计算机科学领域有着广泛的应用 比如在编译和运行计算机程序的过程中 就需 要用栈进行语法检查 如检查 begin 和 end 和 等是否匹配 计算表达式的值 实现过程和函数的递归调用等 下面举例说明栈在这些方面的应用 例 1 假设一个表达式有英文字母 小写 运算符 和左右小 圆 括 号构成 以 作为表达式的结束符 请编写一个程序检查表达式中的左右圆括 号是否匹配 若匹配 则返回 YES 否则返回 NO 表达式长度小于 255 左 圆括号少于 20 个 分析 假设输入的字符串存储在 c 中 var c string 255 我们可以定义一个栈 var s array 1 maxn of char top integer 用它来存放表达式中从左往右的左圆括号 算法的思路为 顺序 从左往右 扫描表达式的每个字符 c i 若是 则让它 进栈 若遇到的是 则让栈顶元素出栈 当栈发生下溢或当表达式处理完毕而栈非空 时 表示不匹配 返回 YES 否则表示匹配返回 NO 程序代码如下 var c string function doit c string boolean var s array 1 20 of char top i integer ch char begin top 0 i 1 ch c i while ch do begin if ch or ch then case ch of begin top top 1 s top end if top 0 then top top 1 else begin doit false exit end end i i 1 ch c i end if top 0 then doit true else doit false end begin assign input in txt reset input readln c writeln doit c close input end 2 背包问题 问题 假设有 n 件质量分配为 w1 w2 wn的物品和一个最多能装载总质量为 T 的 背包 能否从这 n 件物品中选择若干件物品装入背包 使得被选物品的总质量恰好等于背 包所能装载的最大质量 即 wi1 wi2 wik T 若能 则背包问题有解 否则无解 算法思想 首先将 n 件物品排成一列 依次选取 若装入某件物品后 背包内物品的 总质量不超过背包最大装载质量时 则装入 进栈 否则放弃这件物品的选择 选择下一 件物品试探 直至装入的物品总和正好是背包的最大转载质量为止 这时我们称背包装满 若装入若干物品的背包没有满 而且又无其他物品可以选入背包 说明已装入背包的 物品中有不合格者 需从背包中取出最后装入的物品 退栈 然后在未装入的物品中挑选 重复此过程 直至装满背包 有解 或无物品可选 无解 为止 具体实现 设用数组 weight 1 N stack 1 N 分别存放物品重量和已经装入背包 栈 的物品序号 MaxW 表示背包的最大装载量 每进栈一个物品 就从 MaxW 中减去该物 品的质量 设 i 为待选物品序号 若 MaxW weight i 0 则该物品可选 若 MaxW weight i n 则需退栈 若此时栈空 则说明无解 本题作为课后作业 具体程序请大家自行完成 栈的应用举例栈的应用举例 1 若已知一个栈的入栈顺序是 1 2 3 n 其输出序列为 P1 P2 P3 Pn 若 P1 是 n 则 Pi 是 A i B n 1 C n i 1 D 不确定 2 以下哪一个不是栈的基本运算 A 删除栈顶元素 B 删除栈底的元素 C 判断栈是否为空 D 将栈置为空栈 3 设栈 S 和队列 Q 初始状态为空 元素 e 1 e 2 e 3 e 4 e 5 e 6依次通过栈 S 一个元素出栈后即进入队列 Q 若出队的顺序为 e 2 e 4 e 3 e 6 e 5 e 1 则栈 S 的容量至少应该为 A 2 B 3 C 4 D 5 4 设栈 S 的初始状态为空 现有 5 个元素组成的序列 1 2 3 4 5 对该序列在 S 栈上依次进 行如下操作 从序列中的 1 开始 出栈后不在进栈 进栈 进栈 进栈 出栈 进栈 出栈 进栈 问出 栈的元素序列是 栈顶指针的值为 栈顶元素为 5 设栈 S 和队列 Q 初始状态为空 元素 e 1 e 2 e 3 e 4 e 5 e 6依次通过栈 S 一个元素出栈后即进入队列 Q 若出队顺序为 e 2 e 4 e