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

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

一．.实验目的

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

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

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

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

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

二．实验时间

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

三．.实验内容

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

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

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

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

?

顺序栈

#include<iostream>
using namespace std;
const int stacksize=10;
template<class T>
class Seqstack
{
	public:
		Seqstack(){top=-1;}
		~Seqstack(){}
		void ruz(T x);
		T chuz();
		T quzd();
		int empty();
	private:
		T data[stacksize];
		int top;
};

template<class T>
void Seqstack<T>::ruz(T x)
{
	if(top==stacksize-1)throw"上溢错误";
	top++;
	data[top]=x;
}

template<class T>
T Seqstack<T>::chuz()
{
	T x;
	if(top==-1)throw"下溢错误";
	x=data[top--];
	return x;
}

template<class T>
T Seqstack<T>::quzd()
{
	if(top!=-1)
		return data[top];
}

template<class T>
int Seqstack<T>::empty()
{
	if(top==-1)
		return 1;
	else
		return 0;
}

void main()
{
	Seqstack<int> z;
	if(z.empty())
		cout<<"此栈为空!"<<endl;
	else
		cout<<"此栈为非空!"<<endl;
	cout<<"1,2,3,4,5依次入栈!"<<endl;
	z.ruz(1); z.ruz(2); z.ruz(3);
	z.ruz(4); z.ruz(5);
	cout<<"此栈的栈顶元素是：";
	cout<<z.quzd()<<endl;
	cout<<"执行一次出栈操作!"<<endl;
	z.chuz();
	cout<<"现在的栈顶元素是：";
    cout<<z.quzd()<<endl;
	cout<<"再执行一次出栈操作!"<<endl;
	z.chuz();
	cout<<"现在栈顶元素是：";
	cout<<z.quzd()<<endl;
}

截图

?

链队列

#include<iostream>
using namespace std;
template<class T>
struct node
{
	T data;
	node<T> *next;
};
template<class T>
class Linkqueue
{
	public:
		Linkqueue();
		~Linkqueue();
		void rud(T x);
		T chud();
		T qudt();
		int empty();
	private:
		node<T> *front,*rear;
};

template<class T>
Linkqueue<T>::Linkqueue()
{
	node<T> *r=NULL;
	r=new node<T>;
	r->next=NULL;
	front=rear=r;
}

template<class T>
Linkqueue<T>::~Linkqueue()
{
	node<T> *p=NULL;
	while(front!=NULL)
	{
		p=front->next;
		delete front;
		front=p;
	}
}

template<class T>
void Linkqueue<T>::rud(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 Linkqueue<T>::chud()
{
	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 Linkqueue<T>::qudt()
{
	if(front!=rear)
		return front->next->data;
}

template<class T>
int Linkqueue<T>::empty()
{
	if(front==rear)
		return 1;
	else
		return 0;
}

void main()
{
	Linkqueue<int> d;
	if(d.empty())
		cout<<"此队列为空!"<<endl;
	else
		cout<<"此队列为非空!"<<endl;
	cout<<"10,20,30依次入队!"<<endl;
		try
	{
		d.rud(10);  d.rud(20);  d.rud(30);
	}
	catch(char *w)
	{
		cout<<w<<endl;
	}
	cout<<"此队列的队头元素是：";
	cout<<d.qudt()<<endl;
	cout<<"执行一次出队操作!"<<endl;
	try
	{
		d.chud();
	}
	catch(char *w)
	{
		cout<<w<<endl;
	}
	cout<<"现在的队头元素是：";
		cout<<d.qudt()<<endl;
}

截图

?

?

比较总结栈和队列

???????? 栈只能在一端进行插入和删除操作，即后入栈的先出栈。栈有时候可能造成空间的浪费，所以有两栈共享空间，要定义两个栈顶指针。

???????? 队列只允许在一端进行插入操作，在另一端进行删除操作，所以先入队的也先出队。队列有一个重点，就是判断队空和队满的条件。

???????? 栈和队列都是受限制的线性表。