栈和队列实验报告

数据结构实验报告 顺序栈的实现和基本操作

一、需求分析

（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）顺序栈

◆为了实现程序的功能，在.H 文件中定义了栈的模板类. template

class Stack

{

私有数据成员：

private:

公有成员：

public:

栈的初始化 void InitStack(int capacity=10);

操作结果：初始化一个默认长度为10的空栈

判断栈是否为空 bool IsEmpty() const;

初始条件：栈已存在。 栈的最大长度 int MaxSize; 栈顶位置 int top; 顺序栈首地址 T *theArray;

操作结果：判断栈是否为空。为空则返回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）队列

◆为了实现程序的功能，在.H 文件中定义了队列的模板类.

template

class Queue

{

私有数据成员：

private:

公有成员：

public:

队列的最大长度 int MaxSize; 队列的当前位置 Int currentSize; 队头位置 int front; 队尾位置 int rear; 队列的头指针 T *theArray; 自加函数 void Increment(int &x); 队列的初始化 void InitQueue(int capacity=10);操作结果：初始化一个默认长度为10的空队列 判断队列是否为空 bool IsEmpty() const; 初始条件：队列已存在。

操作结果：判断队列是否为空。为空则返回1。

判断队列是否为满 bool IsFull() const;

初始条件：队列已存在。

操作结果：判断队列是否为满。为满则返回1。

查看队列顶元素 const T & GetFront() const;

初始条件：队列已经存在。

操作结果：查看队列顶元素，且返回其值。

清空队列 void MakeEmpty();

初始条件：队列已存在。

操作结果：清空当前队列中元素。

出队列 T DeQueue();

初始条件：队列已存在。

操作结果：将当前队列顶元素出队。队列为空时提醒

当前队列为空。

入队列 void EnQueue(const T &x);

初始条件：队列已存在。

操作结果：将当前元素入队。队列为满时弹出提醒当

前队列已满。

输出队列 void OutPut();

初始条件：队列已存在

操作结果：按顺序输出队列中元素

};

◆ 模板类中包含了以下函数

初始化队列 void InitQueue(int capacity=10); 判断队列是否为空 bool IsEmpty() const; 判断队列是否为满 bool IsFull() const; 查看队头元素 const T & GetFront() const; 置空队列 void MakeEmpty(); 出对 T DeQueue();

入对 void EnQueue(const T &x); 输出队列 void Output();

◆ 运用main 函数 来调用实现以上功能 ◆ 各个函数之间关系表示如下：

三、详细设计

（1）顺序栈 ◆ 栈的初始化： template

void Stack::InitStack(int capacity)

{

MaxSize=capacity;

theArray=new T[MaxSize];

top=-1;

}

◆ 判断栈空

template

bool Stack::IsEmpty() const

返回1

{

return top==-1;

}

◆判断栈满

template

bool Stack::IsFull() const

返回1

{

return top==MaxSize-1;

} //判断栈是否为空 如果空//判断栈是否为满 如果已满

◆入栈函数

template

void Stack::Push(const T &e) //入栈

{

}

◆出栈函数：

template

void Stack::Pop() //出栈

{

}

◆出栈且返回栈顶元素：

template

T Stack::TopAndPop() //返回栈顶元素且出栈 { if(IsEmpty()) cout

if(IsEmpty()) cout

}

◆查看栈顶元素：

template

const T & Stack::Top() const {

if(IsEmpty()) cout

}

◆输出栈：

template

void Stack::Output()

{

if(IsEmpty()) cout

for(i=0;i

{

cout

} //返回栈顶元素

}

◆ 顺序main 函数

#include

#include"malloc.h"

#include"stdlib.h"

#include"stack.h"

void main()

{

Stack stack; int select; do { cout

cout>select; switch(select) { case 1: { int n; cout>n;

stack.InitStack(n);

system("pause");system("cls"); break;

} case 2: {

if(stack.IsEmpty()==1)

cout

} break; case 3:

{ } if(stack.IsFull()==1) cout>x; stack.Push(x); cout

system("pause");system("cls"); break;

}

case 5:

{ int i,e; e=stack.TopAndPop(); cout

则输入0）"

} cin>>i; if(i=1) cout

}

} } while(select>=1&&select

（2）队列

◆队列初始化

template

void Queue::InitQueue(int capacity) {

MaxSize=capacity;

theArray=new T[MaxSize];

}

◆判空

template

bool Queue::IsEmpty()const {

return currentSize==0; } front=0; rear=-1;

◆判满

template

bool Queue::IsFull() const {

return currentSize==MaxSize; }

template

void Queue::MakeEmpty() {

currenSize=0;

front=0;

rear=-1;

}

◆置空队列

template

void Queue::MakeEmpty() {

} currenSize=0; front=0; rear=-1;

◆查看队头元素

template

const T & Queue::GetFront()const {

}

◆出队函数

template

T Queue::DeQueue()

{

}

◆入队函数

template

void Queue::EnQueue(const T&x) {

if(IsFull()) cout

} theArray[rear]=x; currentSize++;

◆输出队列

template

void Queue::OutPut()

{

}

◆队列main 函数

#include

#include"malloc.h"

#include"stdlib.h"

#include"duilie.h"

void main() if(IsEmpty()) cout

Queue queue; int select; do { cout>select; switch(select) { case 1: { int n; cout>n;

queue.InitQueue(n);

system("pause");system("cls");

break;

} case 2: {

if(queue.IsEmpty()==1)

cout

system("pause");system("cls");

} break; case 3: { } if(queue.IsFull()==1) cout

int x; cout>x; queue.EnQueue(x); cout

system("pause");system("cls");

break;

}

case 5:

{ int i,e; e=queue.DeQueue(); cout

} cin>>i; if(i=1) cout

cout

}

} system("pause");system("cls"); break; case 7: { cout=1&&select

四、使用说明

顺序栈模板类的全部实现内容包含在一个独立的C++头文件stack.h 中。而为了实现该头文件里的函数以及其功能，又建立了一个

main 函数来使用该顺序栈的类头文件。首先，先进行了模板类的实例化。

队列模板类的全部实现内容包含在一个独立的C++头文件stack.h 中。而为了实现该头文件里的函数以及其功能，又建立了一个main 函数来使用该顺序栈的类头文件。首先，先进行了模板类的实例化。

五、测试程序的运行结果

（1）顺序栈

1、选择1 创建栈 输入4，即创建长度为4的顺序栈

2、选择4 入栈。依次操作且输入1.2.3.4.5

3、选择7 输出栈

4、两次选择5 出栈

5、选择7 输出栈

6、选择6 查看 栈顶元素

7、选择7 输出栈

（2）队列

1、选择1 创建队列，输入5 即创建长度为5的队列

2、选择2 判断队列是否为空

3、选择4 入队。依次操作且输入 1.2.3.4.5

4、选择7 输出队列

5、选择5 出队

6、选择6 查看队首元素

7、选择7 输出队列

六、心得体会

学习完队列和栈一章后对其操作以及各个函数的运用有的了解。

本次的程序在调试的方面曾经多次出现问题，特别是开始时输入的数据出现了不能继续操作的情况，在同学的帮助下解决了这一问题，总体来看由于教材上有较多的实例，个人主要是完成主函数和各个函数的衔接，总体来说操作不是很复杂，但是需要时间进行调试。

通过这次试验进一步增强了对栈和队列原理的理解。