linqueue.h

数据结构c++-书的一些源代码

#include <iostream.h>
#include <stdlib.h>

template <class T> class LinQueue;			//前视定义,否则友元无法定义
template <class T> class QueueNode
{
		friend class LinQueue<T>;			//定义类LinQueue<T>为友元
		private:
			QueueNode<T> *next;	    		//指向下一结点的指针
		public:
			T data;							//定义为公有成员方便使用
			//构造函数和析构函数	
			QueueNode(const T& item, QueueNode<T> *ptrNext = NULL);
			~QueueNode(){};
};

template<class T>
QueueNode<T>::QueueNode(const T &item, QueueNode<T> *ptrNext)
{
	data = item;
	next = ptrNext;
}

template <class T> class LinQueue
{
		private:
			QueueNode<T> *front;			//指向队头的指针
			QueueNode<T> *rear;				//指向队尾的指针
			int size;						//队列的结点个数
   		public:
    		LinQueue(void);					//构造函数
			~LinQueue(void);				//析构函数

			void QInsert(const T& item);	//入队列
			T QDelete(void);       			//出队列
			T QFront(void)const; 			//读队头元素值
			int QueueEmpty(void)const  		//判队列是否为空
        			{return front == NULL;};
			void ClearQueue(void);           //清空队列
			int GetSize(void)const     		//取队列元素个数
        			{return size;};
};
 
//队列类的实现  
template <class T> 
LinQueue<T>::LinQueue()				//构造函数
{
		front = rear = NULL;		//头指针指向头结点
		size = 0;					//定义size的初值为0
}

template <class T>
LinQueue<T>::~LinQueue(void)		//析构函数
{ 
		ClearQueue();				//释放所有结点
		front = rear = NULL;
}

template <class T>
void LinQueue<T>::QInsert(const T& item)
//把数据域值为item的结点插入栈顶
{
		//构造新结点newNode，newNode的data域值为item，next域值为NULL
		QueueNode<T> *newNode = new QueueNode<T>(item, NULL);

		if(rear != NULL) rear->next = newNode;	
		rear = newNode;				//新结点为队尾结点

		if(front == NULL) front = newNode;

		size++;						//结点个数加1
}

template <class T>
T LinQueue<T>::QDelete(void)	//把栈顶结点出栈并返回栈顶元素
{
		if(size == 0) 
		{
			cerr << "队列已空无元素可删！" << endl;
			exit(1);
		}
		
		QueueNode<T> *p = front->next;	//p指向新的栈顶结点
		T data = front->data;			//保存原队头结点的data域值
		delete front;					//释放原队头结点空间
		front = p;						//front指向新的队头结点
		size--;							//结点个数减1
		return data;					//返回原队头结点的data域值
}

template <class T>
T LinQueue<T>::QFront(void)const		//返回队头结点的data值
{
		return front->data;
}

template <class	T>	
void LinQueue<T>::ClearQueue(void)		//清空队列为初始化状态
{
		QueueNode<T> *p, *p1;

		p = front;						//p指向第一个结点
		while(p != NULL)				//循环释放结点空间直至初始化状态
		{
        	p1 = p;
			p = p->next;
			delete p1;
		}
		size = 0;						//结点个数置为初始化值0
}