栈和队列及其应用实验报告.docx

栈和队列及其应用实验报告

实验类型：●验证性实验○综合性实验○设计性实验

一、实验目的或任务

通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。

二、实验教学基本要求

1.了解实验目的及实验原理；

2.编写程序，并附上程序代码和结果图；

3.总结在编程过程中遇到的问题、解决办法和收获。

三、实验教学的内容或要求

1.编写函数,采用链式存储实现栈的初始化、入栈、出栈操作

2.编写函数,采用顺序存储实现栈的初始化、入栈、出栈操作

3.编写函数,采用链式存储实现队列的初始化、入队、出队操作

4.编写函数,采用顺序存储实现队列的初始化、入队、出队操作

5.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法

四、实验内容

实验代码：

1.栈的进出

#include

usingnamespacestd;

constintStackSize=20;

template<c<span="">lassDataType></c<>

classSeqStack

{

public:

SeqStack();

~SeqStack(){};

voidPush(DataTypex);

DataTypePop();

DataTypeGetTop();

intEmpty();

private:

DataTypedata[StackSize];

inttop;

};

template

SeqStack::SeqStack()

{

top=-1;

}

template

voidSeqStack::Push(DataTypex)

{

if(top==StackSize-1)throw"上溢";

top++;

data[top]=x;

}

template

DataTypeSeqStack::Pop()

{

DataTypex;

if(top==-1)throw"下溢";

x=data[top--];

returnx;

}

template

DataTypeSeqStack::GetTop()

{

if(top!=-1)

returndata[top];

}

template

intSeqStack::Empty()

{

if(top==-1)return1;

elsereturn0;

}

intmain()

{

SeqStackS;

if(S.Empty())

{cout<<"栈为空"<<endl;<span=""></endl;<>

}

else

{cout<<"栈非空"<<endl;<span=""></endl;<>

}

cout<<"对12和11执<span="">行入栈操作"<<endl;<span=""></endl;<>

S.Push(12);

S.Push(11);

cout<<"栈顶元素为："<<endl;<span=""></endl;<>

cout<<s.gettop()<<endl;<span=""></s.gettop()<<endl;<>

cout<<"进行出栈操作"<<endl;<span=""></endl;<>

S.Pop();

cout<<"栈顶元素为："<<endl;<span=""></endl;<>

cout<<s.gettop()<<endl;<span=""></s.gettop()<<endl;<>

}

2.队列的进出

#include"stdlib.h"

#include"stdio.h"

typedefstructQueue

{

intdata;

structQueue*next;

}Queue,*QueuePtr;

typedefstruct

{

QueuePtrfront;

QueuePtrrear;

}LinkQueue;

voidInitQueue(LinkQueue&Q)

{

Q.front=Q.rear=(QueuePtr)malloc(sizeof(Queue));