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

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

一．.实验目的

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

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

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

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

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

二．实验时间

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

三．.实验内容

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

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

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

四、实验

（一）、顺序栈的实现

1、主要操作运算算法图

2、源程序

#include<iostream>
using namespace std;
const int maxsize=5;
template<class T>
class seqstack
{
public:
	seqstack(){top=-1;}
	~seqstack(){}
	void push();
	T pop();
	T gettop(){if(top!=-1) return data[top];}
	int emtpy();
private:
	T data[maxsize];
	int top;
};
template<class T>
void seqstack<T>::push()
{
	T x;
	if(top==maxsize-1)throw"上溢！";
	else 
	 for(;top<maxsize-1;)
	 {
		 cin>>x;
		 data[++top]=x;
	 }

}

template<class T>
T seqstack<T>::pop()
{
	T x;
	if(top==-1)throw"下溢";

		x=data[top--];
	return x;
}
template<class T>
int seqstack<T>::emtpy()
{
	if(top==-1) return 1;
	else return 0;
}
void main()
{
    seqstack<int> s;
	if(s.emtpy())
		cout<<"Empty seqstack!"<<endl;
	else
		cout<<"NO Emtyp seqstack!"<<endl;
	cout<<"please input your number:"<<endl;
	s.push();
	cout<<"the number of top seqstack:"<<endl;
	cout<<s.gettop()<<endl;
	cout<<"执行一次出栈操作!"<<endl;
	s.pop();
	cout<<"出栈后栈顶元素为："<<endl;
	cout<<s.gettop()<<endl;
}

3、执行结果

2、源程序

#ifndef linkqu_H
#define linkqu_H
template<class T>
struct node
{
	T data;
	node<T>*next;
};
template<class T>
class linkqu
{
	public:
		linkqu();
		~linkqu();
		void enqu(T x);
		T dequ();
		T getqu();
		int empty();
	private:
		node<T>*front,*rear;
};
#endif;
#include"linkqu.h"
template<class T>
linkqu<T>::linkqu()
{
	node<T>*s=NULL;
	s=new node<T>;
	s->next=NULL;
	front=rear=s;
}
template<class T>
linkqu<T>::~linkqu()
{
	node<T> *p=NULL;
	while(front!=NULL)
	{
		p=front->next;
		delete front;front=p;
	}
}
template<class T>
void linkqu<T>::enqu(T x)
{
	node<T> *s=NULL;
	s=new node<T>;
	s->data=x;
	s->next=NULL;
	rear->next=s;rear=s;
}
template<class T>
T linkqu<T>::dequ()
{
	node<T>*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 T>
T linkqu<T>::getqu()
{
	if(front!=rear)
		return front->next->data;
}
template<class T>
int linkqu<T>::empty()
{
	if(front==rear) return 1;
	else return 0;
}
#include<iostream>
using namespace std;
#include"linkqu.cpp"
void main()
{
	linkqu<int>Q;
	if(Q.empty())
		cout<<"队列为空！"<<endl;
	else
		cout<<"队列非空！"<<endl;
	cout<<"将元素10和15执行入队操作："<<endl;
	try
	{
		Q.enqu(10);	Q.enqu(15);
	}
	catch(char *wrong)
	{
		cout<<wrong<<endl;
	}
	cout<<"查看队头元素："<<endl;
	cout<<Q.getqu()<<endl;
	cout<<"执行一次出队操作！"<<endl;
	try
	{Q.dequ();}
	catch(char*wrong)
	{
		cout<<wrong<<endl;
	}
	cout<<"查看对头元素："<<endl;
	cout<<Q.getqu()<<endl;
}