queue.h

图的常用算法

#ifndef QUEUE_CLASS
#define QUEUE_CLASS

#include <assert.h>

template <class T>
class Queue;

template <class T>
class PQueue;

template <class T>
class QueueNode
{
	friend class Queue<T>;
	friend class PQueue<T>;
	private:
		T data;
		QueueNode<T> * link;
	public:
		QueueNode(T item,QueueNode<T> *next=NULL)
			:data(item),link(next)
		{}
};

template <class T>
class Queue
{
	protected:
		QueueNode<T> *front,*rear;

	public:
		Queue();
		~Queue();

		void EnQueue(const T & item);
		bool DeQueue(T & item);
		bool GetFront(T & item);

		int Length() const;
		void MakeEmpty();
		bool IsEmpty() const;
};

template <class T>
Queue<T>::Queue():front(NULL),rear(NULL)
{}

template <class T>
Queue<T>::~Queue()
{
	MakeEmpty();
}

template <class T>
void Queue<T>::EnQueue(const T& item)
{
	QueueNode<T>* newNode=new QueueNode<T>(item);
	assert(newNode!=NULL);
	if(front==NULL)
		front=rear=newNode;
	else{
		rear->link=newNode;
		rear=newNode;
	}
}

template <class T>
bool Queue<T>::DeQueue(T& item)
{
	if(IsEmpty())
       return false;
	QueueNode<T>* p=front;
	item=p->data;
	front=front->link;
	if(front==NULL)
		rear=NULL;
	delete p;
	return true;
}

template <class T>
bool Queue<T>::GetFront(T & item)
{
	if(IsEmpty())
	{
		item=front->data;
		return true;
	}
	return false;
}

template <class T>
int Queue<T>::Length() const
{
	int size=0;
	QueueNode<T> *temp=front;

	while(temp!=NULL)
	{
		size++;
		temp=temp->link;
	}
	return size;
}

template <class T>
void Queue<T>::MakeEmpty()
{
	QueueNode<T>* p;
	while(front!=NULL)
	{
		p=front;
		front=front->link;
		delete p;
	}
	rear=NULL;
}

template <class T>
bool Queue<T>::IsEmpty()const
{
	return front==NULL;
}

#endif