数据结构实验二：堆栈与队列.doc

实验二:堆栈与队列(2学时)
一、实验目的:采用数组和链表两种形式分别实现堆栈与队列的功能。要求每个学生充分理解堆栈与队列的相同和相异之处。
二、实验内容:

[问题描述]
将十进制数N和其它d进制数的转换是计算机实现计算的基本问题,其解决方案很多,其中最简单方法基于下列原理:即除d取余法。例如:(1348)10=(2504)8
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
从中我们可以看出,最先产生的余数4是转换结果的最低位,这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。
[基本要求]
对于键盘输入的任意一个非负的十进制整数,打印输出与其等值的八进制数。由于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位,而打印输出,一般来说应从高位到地位进行,恰好和计算过程相反。因此可以先将计算过程中得到的八进制数的各位进栈,待相对应的八进制数的各位均产生以后,再使其按顺序出栈,并打印输出。即得到了与输入的十进制数相对应的八进制数。
[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据。

[问题描述]
试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’,且序列2 是序列1的逆序列。例如,‘a+b&b+a’是属该模式的字符序列,而‘1+3&3-1’则不是。
[实现提示]
首先,序列1进栈,然后序列1出栈并与序列2比较。
[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据,如序列1和序列2均为空串。

[问题描述]
商品货架可以看成一个栈,栈顶商品的生产日期最早,栈底商品的生产日期最近。上货时,需要倒货架,以保证生产日期较近的商品在较下的位置。
[基本要求]
针对一种特定商品,实现上述管理过程。
[实现提示]
用栈模拟货架和周转空间。
[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据,如空栈。

[问题描述]
假设表达式中允许有两种括号:圆括号和方括号,其嵌套的顺序随意,即(()[ ])或
[([ ] [ ])]等为正确格式,[( ])或(((]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如:考虑下列的括号序列:
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
当计算机接受了第1个括号以后,他期待着与其匹配的第8个括号的出现,然而等来的却是第2个括号,此时第1个括号“[”只能暂时靠边,而迫切等待与第2个括号相匹配的第7个括号“)”的出现,类似的,因只等来了第3个括号“[”,此时,其期待的紧迫程度较第2个括号更紧迫,则第2个括号只能靠边,让位于第3个括号,显然第3个括号的期待紧迫程度高于第2个括号,而第2个括号的期待紧迫程度高于第1个括号;在接受了第4个括号之后,第3个括号的期待得到了满足,消解之后,第2个括号的期待匹配就成了最急迫的任务了,……,依次类推。可见这个处理过程正好和栈的特点相吻合。
[基本要求]