linqueue.h

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

template <class T> class LinQueue;	//前视定义,否则友元无法定义

template <class T> 
class QueueNode
{
	friend class LinQueue<T>;		//定义类LinQueue<T>为友元
private:
	QueueNode<T> *next;	    		//指针
	T data;							//数据元素
public:
	//构造函数	
	QueueNode(const T& item, QueueNode<T> *ptrNext = NULL)
		:data(item), next(ptrNext){}

	~QueueNode(){};					//析构函数
};

template <class T> 
class LinQueue
{
private:
	QueueNode<T> *front;			//队头指针
	QueueNode<T> *rear;				//队尾指针
	int count;						//计数器
public:
	LinQueue(void);					//构造函数
	~LinQueue(void);				//析构函数

	void Append(const T& item);		//入队列
	T Delete(void);       			//出队列
	T GetFront(void)const; 			//取队头数据元素
	int NotEmpty(void)const  		//非空否
		{return count != 0;};
};
 
//队列类的实现  
template <class T> 
LinQueue<T>::LinQueue()				//构造函数
{
	front = rear = NULL;			//无头结点
	count = 0;						//count的初值为0
}

template <class T>
LinQueue<T>::~LinQueue(void)		//析构函数
{ 
	QueueNode<T> *p, *q;

	p = front;						//p指向第一个结点
	while(p != NULL)				//循环直至全部结点空间释放
	{
       	q = p;
		p = p->next;
		delete q;
	}

	count = 0;						//置为初始化值0
	front = rear = NULL;
}

template <class T>
void LinQueue<T>::Append(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;

	count++;						//计数器加1
}

template <class T>
T LinQueue<T>::Delete(void)	     	//出队列
//把队头结点删除并由函数返回
{
	if(count == 0) 
	{
		cout << "队列已空！" << endl;
		exit(0);
	}
	
	QueueNode<T> *p = front->next;	//p指向新的队头结点
	T data = front->data;			//保存原队头结点的data域值
	delete front;					//释放原队头结点空间
	front = p;						//front指向新的队头结点
	count--;						//计数器减1
	return data;					//返回原队头结点的data域值
}

template <class T>
T LinQueue<T>::GetFront(void)const		//取队头数据元素
{
	if(count == 0) 
	{
		cout << "队列已空！" << endl;
		exit(0);
	}

	return front->data;
}