一．.实验目的

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

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

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

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

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

二．实验时间

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

三．.实验内容

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

3.编程实现一个十进制数转换成二进制数。要求，要主程序中输出一个10进度数，输出其对应的2进制数序列。

前两题是必做题，第3题是选做题。

2.1、循环队列代码：

/**循环队列头文件**/
const int MaxSize=100;
template<class DataType>
class Duilie
{
public:
	Duilie();
	~Duilie(){};
	void Insert(DataType x);
	DataType Getdulie();
	DataType Outduilie();
	int Empty();
private:
	DataType data[MaxSize];
	int front,rear;
    int flag;
};

/**循环队列源文件**/
#include<iostream>
using namespace std;
#include"Duilie1.h"

template<class DataType>
Duilie<DataType>::Duilie()
{
	front=rear=MaxSize-1;
}

template<class DataType>
void Duilie<DataType>::Insert(DataType x)
{
	
	if(flag==1&&front==rear)throw"Over"	;
	flag=1;
	rear=(rear+1)%MaxSize;
	data[rear]=x;
}

template<class DataType>
DataType Duilie<DataType>::Getdulie()
{
	if(rear==front)throw"Under";
	int i=(front+1)%MaxSize;
	return data[i];
}

template<class DataType>
DataType Duilie<DataType>::Outduilie()
{
	if(rear==front&&flag==0)throw"Under";
	flag=0;
	front=(front+1)%MaxSize;
	return data[front];
}

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

/**循环队列主函数源文件**/
#include<iostream>
using namespace std;
#include"Duilie1.cpp"

void main()
{
	Duilie<int> D;
	if(D.Empty())
		cout<<"Empty"<<endl;
	else
		cout<<"Not Empty"<<endl;
	cout<<"Insert the number 12 and 18!"<<endl;
		D.Insert(12);
		D.Insert(18);
	cout<<"The head is:"<<D.Getdulie()<<endl;
	cout<<"Let the head-number out!"<<endl;
	D.Outduilie();
    cout<<"Then the new head is:"<<D.Getdulie()<<endl;
	if(D.Empty())
		cout<<"Empty"<<endl;
	else
		cout<<"Not Empty"<<endl;
	
}

2.2,链队列

/***头文件***/
template<class DataType>
struct Node
{
	DataType data;
	Node<DataType> *next;
};

template<class DataType>
class Liandui
{
public:
	Liandui();
	~Liandui();
	void Insert(DataType x);
	DataType OutLian();
	DataType GetLian();
	int Empty();
private:
	Node<DataType> *front,*rear;
};

/***源文件***/
#include"liandui.h"

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

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

template<class DataType>
void Liandui<DataType>::Insert(DataType x)
{
	Node<DataType>*k=NULL;
	k=new Node<DataType>;
	k->data=x;
	k->next=NULL;
	rear->next=k;
	rear=k;
}

template<class DataType>
DataType Liandui<DataType>::OutLian()
{
	Node<DataType>*m=NULL;
	m=new Node<DataType>;
	if(rear==front)throw"下溢";
	m=front->next;
	int x;
	x=m->data;
	front->next=m->next;
	if(m->next==NULL)rear=front;
	delete m;
	return x;
}

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

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


/***主函数***/
#include<iostream>
using namespace std;
#include"liandui.cpp"

void main()
{
	Liandui<int> L;
	if(L.Empty())
		cout<<"队列为空"<<endl;
	else
		cout<<"队列非空"<<endl;
	cout<<"进行插入数值12、18和21操作"<<endl;
	try{
	L.Insert(12);
	L.Insert(18);
	L.Insert(21);}
	catch(char *q)
	{
		cout<<q<<endl;
	}
	cout<<"队头元素为："<<L.GetLian()<<endl;
	cout<<"执行第一次出队操作"<<endl;
	try{
	L.OutLian();
	}
	catch(char *q)
	{
		cout<<q<<endl;}
	cout<<"此时队头元素为："<<L.GetLian()<<endl;
	cout<<"判断队列是否为空：";
	if(L.Empty())
		cout<<"队列为空"<<endl;
	else
		cout<<"队列非空"<<endl;
}

3、十进制转化为二进制数，代码如下：

<span style="font-size:14px;">#include<iostream>
using namespace std;

void main()
{
	int x,z,flag=1;
	int i=0;
	int a[100];
	cout<<"请输入一个十进制的数：";
	cin>>x;
	if(x<=0)
		exit(0);
	while(x>0){
		z=x%2;
		x=x/2;
		a[i]=z;
		i++;
	};
	cout<<"转换后的数值为：";
	for(i=100;i>=0;i--)
		if(a[i]==0||a[i]==1)
		cout<<a[i];
	cout<<endl;
}
</span>

总结：

万变不离其宗，都是算法的问题，掌握好线性表很重要，第二章要花多一点时间，代码要多看几遍，而且通过选做题反映出了我自己一些计算机的基础知识例如数制之间的转换已经忘得差不多了