2010数据结构实验指导书48

3、掌握队列的应用方法，理解队列的重要应用； 4、根据实验要求设计并完成程序。

【实验原理】

队列是限定只能在表的一端进行插入，而在表的另一端进行删除的线性表。是一种“先进先出”（First

In First Out，缩写为 FIFO）的线性表。队列可以有多种实现形式，本实验要求将队列作为一个抽象数据类型（ADT）来解决各实验课题。

【实验要求】（实验课题一必做，课题二选做）

实验课题一：回文（palindrome）是指一个字符串从前面读和从后面读都一样，仅使用若干栈和队列、栈和队列的ADT函数以及若干个int类型和char类型的变量，设计一个算法来判断一个字符串是否为回文。假设字符串从标准输入设备一次读入一个字符，算法的输出结果为true或者false。 可以用一些字符串测试输出结果，如： "abcdeabcde"， "madamimadam" 等

实验课题二：打印扬辉三角形。

打印二项式 ( a + b )i 的展开系数，也就是扬辉三角，国外叫做Pascal's trian gle。如右下图为扬辉三角的前8行数据。

1 0

按照如右图所示的方式，完成对应杨辉三角的打印输出。 1 1 1

1 2 1 2

1 3 3 1 3

1 4 6 4 1 4

1 5 10 10 5 1 5 1 6 15 20 15 6 1 6 1 7 21 35 35 21 7 1 7

杨辉三角

队列的ADT接口：

用C++描述的教科书中没给队列的ADT，可以根据上次实验给出的抽象类VQueue写一个实现，也可以用以下Queue类模版：

template <typename Object> class Queue { public:

bool empty( ) const