2010数据结构实验指导书48

实验二 栈

【实验目的】

1、 掌握栈的LIFO（后进先出）特点和栈的存储结构； 2、熟悉栈的各种操作；

3、掌握栈的应用方法，理解栈的重要应用；

4、根据实验要求设计并完成程序，把理论的基本操作知识转化到实际的实践应用中。

【实验原理】

栈是一种特殊的线性表，这种线性表只能在固定的一端（称为栈顶（top））进行插入和删除操作。由

于只允许在栈顶进行插入和删除操作，所以栈的操作是按照“后进先出”（Last In First Out，缩写为LIFO）原则进行的。本实验要求用栈作为基本的数据结构解决各实验课题。

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

实验课题一： 将一个十进制数转换成另外一个P进制数字符串（可以是二进制到十六进制）。转换函数的原型为：

void Convert (int n, char str[], unsigned P); n：输入，待转换的数

str：输出，转换好的P进制字符串

P：输入，要转换的进制，取值可从2到16。如果在这范围之外，可认为输入错，不做转换。 将一个整数转换成P进制的数，我们可以采用如下的方法：

例：十进制转换成八进制（P等于8）：(66)10=(102)8 66/8=8 余 2 8/8 =1 余 0 1/8 =0 余 1

当商为0时转换结束，转换结果为上述过程余数序列的逆序：102。

先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的LIFO性质，故可用栈来实现数制转换。

*实验课题二：用2个栈实现一个队列，并对使用这种方法实现的队列执行入队、出队操作的时间进行分析。

用C实现的同学，应该实现教科书第76页Figure 3.56（参考代码的queue.h）中定义的队列类型的那些操作函数；

用C++实现作为ADT的队列，应以以下抽象类VQueue作为与用户的界面接口： template <typename Object> class VQueue { public: