实验四--栈和队列验证实验.docVIP

实验四 栈和队列操作验证 1. 实验目的 （1）掌握栈的顺序存储结构； （2）掌握栈的操作特性； （3）掌握基于顺序栈的基本操作的实现方法。 （4）掌握队列的链接存储结构； （5）掌握队列的操作特性； （6）掌握基于链队列的基本操作的实现方法。 2. 实验内容 （1）建立一个空栈； （2）对已建立的栈进行插入、删除、取栈顶元素等基本操作； （3）建立一个空队列； （4）对已建立的队列进行插入、删除、取队头元素等基本操作。 3. 编码 头文件zgy1123.h const int StackSize=10; template class T //定义模板类SeqStack class SeqStack { public: SeqStack( ); //构造函数，初始化一个空栈 ~SeqStack(){} void Push(T x); //将元素x入栈 T Pop( ); //将栈顶元素弹出 T GetTop( ); //取栈顶元素（并不删除） private: T data[StackSize]; //存放栈元素的数组 int top; //栈顶指针，指示栈顶元素在数组中的下标 }; template class T struct Node { T data; NodeT *next; }; template class T class LinkQueue { public: LinkQueue( ); //构造函数，初始化一个空的链队列 ~LinkQueue( ); //析构函数，释放链队列中各结点的存储空间 void EnQueue(T x); //将元素x入队 T DeQueue( ); //将队头元素出队 T GetQueue( ); //取链队列的队头元素 private: NodeT *front, *rear; //队头和队尾指针，分别指向头结点和终端结点 }; 函数实现文件zgy112354.cpp #includeiostream #includezgy1123.h using namespace std; template class T SeqStackT::SeqStack() { top=-1; } template class T void SeqStackT::Push(T x) { if (top==StackSize-1) throw 上溢; top++; data[top]=x; } template class T T SeqStackT:: Pop( ) { if (top==-1) throw 下溢; T x=data[top--]; return x; } template class T T SeqStackT::GetTop( ) { if (top==-1) throw 下溢; T x=data[top]; return x; } template class T LinkQueueT::LinkQueue( ) { NodeT *s=new NodeT; s-next=NULL; //创建一个头结点s front=rear=s; //将队头指针和队尾指针都指向头结点s } template class T LinkQueueT::~LinkQueue( ) { while(front!=NULL) { NodeT *q=front; front=front-next; delete q; } } template class T void LinkQueueT::EnQueue(T x) { NodeT *s=new NodeT; s-data=x; //申请一个数据域为x的结点s s-next=NULL; rear-next=s; //将结点s插入到队尾 rear=s; } template class T T LinkQueueT::DeQueue( ) { if (rear==front) throw 下溢; NodeT *p=front-next; T x=p-data; //暂存队头元素 front-next=p-next; //将队头元素所在结点摘链 if (p-next==NULL) rear=front; //判断出队前队列长度是否为1