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

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

一．.实验目的

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

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

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

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

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

二．实验时间

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

三．.实验内容

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

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

四．参考资料

??? 实验教材P183到192

1.栈的实现

头文件

# ifndef Seqstack_H

# define Seqstack_H

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

源代码

# include<iostream>

using namespace std;

# 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;

}

void main()

{

?????? SeqStack<int>S;

?????? if(S.empty())

????????????? cout<<"栈为空"<<endl;

?????? else

????????????? cout<<"栈为空"<<endl;

?????? cout<<"对9和13进行入栈操作:"<<endl;

?????? S.Push(9);

?????? S.Push(13);

?????? cout<<"栈顶元素为:"<<endl;

?????? cout<<S.GetTop()<<endl;

?????? cout<<"执行第一次出栈操作:"<<endl;

?????? S.pop();

?????? cout<<"栈顶元素为:"<<endl;

?????? cout<<S.GetTop()<<endl;

}

2.链队列的实现

头文件

# ifndef LinkQueue_H

# define LinkQueue_h

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

# include<iostream>

using namespace std;

# 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;

}

void 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;

}