链接队列.cpp

数据结构：轮渡管理

//进行模板类定义和实现的程序文件“链接队列.cpp”
#include<iostream.h>
#include<stdlib.h>

//结点的模板结构定义
template<class ElemType>
struct sNode{
	ElemType data;    //值域
	sNode* next;      //链接指针域
};

//链接队列的模板定义
template<class ElemType>
class QueueLK{
	sNode<ElemType>* front;  //队首指针
	sNode<ElemType>* rear;   //队尾指针
public:
	//置队首和队尾指针分别为空
	QueueLK(){front=rear=NULL;}
	//元素进队函数，把item插入到队尾
	void EnQueue(ElemType item);
	//元素出队函数，删除队首元素并返回
	ElemType OutQueue();
	//返回队首元素的值，但不改变队列状态
	ElemType PeekQueue();
	//判空函数，若队列为空返回真，否则返回假
	bool EmptyQueue(){return front==NULL;}
	//释放队列中动态存储空间
	~QueueLK();
	//返回队首指针
	sNode<ElemType>* GetFront(){return front;}
	//返回队尾指针
	sNode<ElemType>* GetRear(){return rear;}
};

//向链队中插入一个元素
template<class ElemType>
void QueueLK<ElemType>::EnQueue(ElemType item)
{
	//得到一个由newptr指针所指向的新结点
	sNode<ElemType>* newptr=new sNode<ElemType>;
	if(newptr==NULL){
		cerr<<"内存空间用完！"<<endl;
		exit(1);
	}
	//把item的值赋给新结点的值域，把新结点的指针域置为空
	newptr->data=item;
	newptr->next=NULL;
	//若链队为空，则新结点既是队首结点又是队尾结点
	if(rear==NULL)
		front=rear=newptr;
	//若链队非空，则依次修改队尾结点的指针域和队尾指针，使之指向新的队尾结点
	else 
		rear=rear->next=newptr;
}

//从队列中删除一个元素
template<class ElemType>
ElemType QueueLK<ElemType>::OutQueue()
{
	//若链队为空则终止运行
	if(front==NULL){
		cerr<<"链队为空无法删除！"<<endl;
		exit(1);
	}
	//暂存队首元素以便返回
	ElemType temp=front->data;
	//暂存队首指针以便回收队首结点
	sNode<ElemType>* p=front;
	//使队首指针指向下一个结点
	front=p->next;
	//若删除后链队变为空，则需同时使队尾指针变为空
	if(front==NULL) rear=NULL;
	//回收原队首结点，返回被删除的队首元素
	delete p;
	return temp;
}

//读取队首元素
template<class ElemType>
ElemType QueueLK<ElemType>::PeekQueue()
{
	//若链队为空则中止执行
	if(front==NULL)
	{
		cerr<<"链队为空无队首元素！"<<endl;
		exit(1);
	}
	//返回队首元素
	return front->data;
}

//析构函数
template<class ElemType>
QueueLK<ElemType>::~QueueLK()
{
	//队首指针赋给p
	sNode<ElemType>* p=front;
	//依次删除队列中的每一个结点，并最后使队首指针为空
	while(p!=NULL){
		front=front->next;
		delete p;
		p=front;
	}
	//置队尾指针为空
	rear=NULL;
}