《数据结构》实验三： 栈和队列实验

一．.实验目的

???? 巩固栈和队列数据结构，学会运用栈和队列。

1.回顾栈和队列的逻辑结构和受限操作特点，栈和队列的物理存储结构和常见操作。

2.学习运用栈和队列的知识来解决实际问题。

3.进一步巩固程序调试方法。

4.进一步巩固模板程序设计。

二．实验时间

?? 准备时间为第5周到第6周，具体集中实验时间为6周第2次课。2个学时。

三．.实验内容

1.自己选择顺序或链式存储结构，定义一个空栈类，并定义入栈、出栈、取栈元素基本操作。然后在主程序中对给定的N个数据进行验证，输出各个操作结果。

头文件：

#ifndef SEQSTACK_H_INCLUDED
#define SEQSTACK_H_INCLUDED

const int StackSize=10;
template<class DataType>
class SeqStack{
public:
??? SeqStack();
??? ~SeqStack(){}
??? void Push(DataType x);
??? DataType Pop();
??? DataType GetTop();
??? int Empty();
private:
??? DataType data[StackSize];
??? int top;
};

#endif // SEQSTACK_H_INCLUDED

源文件：

#include "SeqStack.h"

template<class DataType>
SeqStack<DataType>::SeqStack(){
??? top=-1;
}

template<class DataType>
void SeqStack<DataType>::Push(DataType x){
??? if(top==StackSize-1)throw"иорГ";
??? top++;
??? data[top]=x;

}

template<class DataType>
DataType SeqStack<DataType>::Pop(){
??? DataType x;
??? if(top==-1)throw"обрГ";
??? x=data[top--];
??? return x;
}

template<class DataType>
DataType SeqStack<DataType>::GetTop(){
??? if(top!=-1)
??????? return data[top];
}

template<class DataType>
int SeqStack<DataType>::Empty(){
??? if(top==-1)
??????? return 1;
??? else
??????? return 0;
}
主函数：

#include<iostream>
#include "SeqStack.cpp"

using namespace std;

int main(){
??? SeqStack<int> S;
??? if(S.Empty())
??????? cout<<"栈为空"<<endl;
??? else
??????? cout<<"栈非空"<<endl;
??? cout<<"对15和10执行入栈操作"<<endl;
??? S.Push(15);
??? S.Push(10);
??? cout<<"栈顶元素为："<<endl;
??? cout<<S.GetTop()<<endl;
??? cout<<"执行一次出栈操作"<<endl;
??? S.Pop();
??? cout<<"栈顶元素为："<<endl;
??? cout<<S.GetTop()<<endl;

运行结果

}

2.自己选择顺序或链式存储结构，定义一个空栈队列，并定义入栈、出栈、取栈元素基本操作。然后在主程序中对给定的N个数据进行验证，输出各个操作结果。

头文件：

#ifndef LINKQUEUE_H_INCLUDED
#define LINKQUEUE_H_INCLUDED

template<class DataType>
struct Node{
??? DataType data;
??? Node<DataType> *next;
};
template<class DataType>
class LinkQueue{
public:
??? LinkQueue();
??? ~LinkQueue();
??? void EnQueue(DataType x);
??? DataType DeQueue();
??? DataType GetQueue();
??? int Empty();
private:
??? Node<DataType> *front,*rear;
};

#endif // LINKQUEUE_H_INCLUDED
源文件：

#include"LinkQueue.h"

template<class DataType>
LinkQueue<DataType>::LinkQueue(){
??? Node<DataType> *s=NULL;
??? s=new Node<DataType>;
??? s->next=NULL;
??? front=rear=s;
}

template<class DataType>
LinkQueue<DataType>::~LinkQueue(){
??? Node<DataType> *p=NULL;
??? while(front!=NULL){
??????? p=front->next;
??????? delete front;
??????? front=p;
??? }
}

template<class DataType>
void LinkQueue<DataType>::EnQueue(DataType x){
??? Node<DataType> *s=NULL;
??? s=new Node<DataType>;
??? s->data=x;
??? s->next=NULL;
??? rear->next=s;
??? rear=s;
}

template<class DataType>
DataType LinkQueue<DataType>::DeQueue(){
??? Node<DataType> *p=NULL;
??? int x;
??? if(rear==front) throw"обрГ";
??? p=front->next;
??? x=p->data;
??? front->next=p->next;
??? if(p->next==NULL)
??????? rear = front;
??? delete p;
??? return x;
}

template<class DataType>
DataType LinkQueue<DataType>::GetQueue(){
??? if(front!=rear)
??????? return front->next->data;
}

template<class DataType>
int LinkQueue<DataType>::Empty(){
??? if(front==rear)
??????? return 1;
??? else
??????? return 0;
}

主函数：

#include <iostream>
#include"LinkQueue.cpp"
using namespace std;

int main(){ ??? LinkQueue<int> Q; ??? if(Q.Empty()) ??????? cout<<"队列为空"<<endl; ??? else ??????? cout<<"队列非空"<<endl; ??? cout<<"元素10和15执行入队操作："<<endl; ??? try{ ??????? Q.EnQueue(10); ??????? Q.EnQueue(15); ??? }catch(char * wrong){ ??????? cout<<wrong<<endl; ??? } ??? cout<<"查看队头元素："<<endl; ??? cout<<Q.GetQueue()<<endl; ??? cout<<"执行出栈操作："<<endl; ??? try{ ??????? Q.DeQueue(); ??? }catch(char *wrong){ ??????? cout<<wrong<<endl; ??? } ??? cout<<"查看队头元素："<<endl; ??? cout<<Q.GetQueue()<<endl; }