数据结构实验指导(3)

实验3 栈和队列的存储结构的实现

实验目的

1． 掌握栈的存储结构及基本操作。 2． 掌握队列的存储结构及基本操作。

3． 通过具体的应用实例，进一步熟悉和掌握栈和队列的实际应用。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

实验内容（基础题必做，应用题任选）

1. 基础题：

（1）按照教材中抽象数据类型栈的定义，采用顺序存储结构（用动态数组）或链式存储结构，编写主函数演示顺序栈/链栈的基本操作。

（2）按照教材中抽象数据类型队列的定义，采用顺序存储结构（循环队列）或链式存储结构，编写主函数演示循环队列/链队列的基本操作。

2. 应用题：

（1）算符优先算法为表达式求值

（2）舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。设计一个函数partner()，模拟上述舞伴配对问题。 基本要求：

1) 由键盘输入数据，每对数据包括姓名和性别；

2) 输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称

和队头者的姓名；

17

实验步骤参考：

1.打开FileView双击stack.h，完成头文件的编写。stack.h主要含结构体的定义和函数的实现。

18

19

2.打开FileView双击stack.cpp，完成源文件的编写。stack.cpp主要含main()函数的实现。

20