栈和队列实验报告.doc

文档介绍：数据结构实验报告
顺序栈的实现和基本操作
一、需求分析
(1)顺序栈
◆栈的典型操作是入栈和出栈,前者将新元素压入栈中,后者弹出栈顶元素。栈只提供对栈顶元素的访问操作,由top ( )完成。Push ( )和Pop ( )还有Top ( )共同构成了栈的最小功能接口。此外,为了方便使用,栈还有判空,判满和输出栈等功能。
◆输入形式及范围:输入形式为整型,范围为0~65535。
◆输出形式:在顺序栈的初始化后显示初始化成功,在判断栈是否为空时显示当前栈为空,入栈后显示入栈成功或者栈已满。出栈时显示出栈元素或者栈为空。输出栈时依次显示栈中元素。
◆程序功能:初始化栈,判断栈是否为空,判断栈是否为满,入栈,出栈,取栈顶元素,出栈同时返回栈顶元素和输出栈等功能。
◆测试数据:初始化后输入栈的长度为4。
判断栈是否为空。
进行5次入栈操作。分别输入1 2 3 4 5
输出栈。
执行2次出栈操作。
输出栈。
查看栈顶元素。
输出栈。
(2)队列
◆队列的典型操作是入队和出队,前者将新元素压入队列中,后者弹出队首头元素。队列只提供对队头元素和队尾元素的操作,由DeQueue ( ) 和EnQueue( )完成。DeQueue还有EnQueue ( )共同构成了队列的最小功能接口。此外,为了方便使用,队列还有判空,判满和输出队列等功能。
◆输入形式及范围:输入形式为整型,范围为0~65535。
◆输出形式:在顺序队列的初始化后显示初始化成功,在判断队列是否为空时显示当前队列为空,入队列后显示入队成功或者队列已满。出队列时显示出队首元素或者队列为空。输出队列时依次显示队列中元素。
◆程序功能:初始化队列,判断队列是否为空,判断队列是否为满,入队,出队,取队首元素,输出队列等功能。
◆测试数据:初始化后输入队列的长度为54。
判断队列是否为空。
进行5次入队操作。分别输入1 2 3 4 5
输出队列。
执行2次出队操作。
输出队列。
查看队首元素。
输出队列。
二、概要设计
(1)顺序栈
◆为了实现程序的功能,.
template <class T>
class Stack
{
私有数据成员:
private:
栈的最大长度 int MaxSize;
栈顶位置 int top;
顺序栈首地址 T *theArray;
公有成员:
public:
栈的初始化 void InitStack(int capacity=10);
操作结果:初始化一个默认长度为10的空栈

判断栈是否为空 bool IsEmpty() const;
初始条件:栈已存在。
操作结果:判断栈是否为空。为空则返回1。
判断栈是否为满 bool IsFull() const;
初始条件:栈已存在。
操作结果:判断栈是否为满。为满则返回1。
查看栈顶元素 const T &Top() const;
初始条件:栈已经存在。
操作结果:查看栈顶元素,且返回其值。
清空栈 void MakeEmpty() {top=-1;}
初始条件:栈已存在。
操作结果:清空当前栈中元素。
出栈 void Pop();
初始条件:栈已存在。
操作结果:将当前栈顶元素出栈。栈为空时提醒当前栈为空。
入栈 void Push(const T &e);
初始条件:栈已存在。
操作结果:将当前元素入栈。栈为满时弹出提醒当前栈已满。
出栈且返回栈顶元素T TopAndPop();
初始条件:栈已存在。
操作结果:当前栈顶元素出栈且返回其值。
输出栈 void Output();
初始条件:栈已存在
操作结果:按顺序输出栈中元素
};
◆模板类中包含了以下函数
初始化栈 void InitStack(int capacity=10);
判断栈空 bool IsEmpty() const;
判断栈满 bool IsFull() const;
查看栈顶元素 const T &Top() const;
置空栈 void MakeEmpty() {top=-1;}
出栈 void Pop();
入栈 void Push(const T &e);
出栈且返回栈顶元素 T TopAndPop();
输出栈 void Output();
(2)队列
◆为了实现程序的功能,.
template <class T>
class Queue
{
私有数据成员:
private:
队列的最大长度 int MaxSize;
队列的当前位置 Int