queue.h

数据结构各种算法的比较程序

#ifndef QUEUE
#define QUEUE
//队列的向量,链表实现...
#include"doubleEndlist.h"
#include"vector.h"
template<class T> class queue;
template<class T> class Vectorqueue;
template<class T> class Listqueue;
//-----------------------------------------------------------------------------抽象向量队列
template<class T> 
class queue
{
public:
	virtual void deleteAllValuess()=0;
	virtual T dequeue()=0;
	virtual bool enqueue(T value)=0;
	virtual T front()const=0;
	virtual int isEmpty()const=0;
};
//-----------------------------------------------------------------------------抽象向量队列
//---------------------------------------------------------------------------------向量队列
/*template<class T>
class Vectorqueue:public queue<T>
{
public:
	Vectorqueue(unsigned int size);
	Vectorqueue(const Vectorqueue<T>& source);
	virtual void deleteAllValuess();
	virtual T dequeue();
	virtual void enqueue(T value);
	virtual T front()const;
	virtual int isEmpty()const;
protected:
	vector<T> data;
	const unsigned max;
	unsigned nextSlot;
	unsigned nextUse;
};
template<class T> Vectorqueue<T>::Vectorqueue(unsigned int size):max(size),data(size)
{
	deleteAllValuess();
}
template<class T> Vectorqueue<T>::Vectorqueue(const Vectorqueue<T> & source):data(source.data),max(source.max)
{
	nextSlot=source.nextSlot;
	nextUse=source.nextUse;
}
template<class T> void Vectorqueue<T>::deleteAllValuess()
{   
	nextSlot=0;
	nextUse=0;
}
template<class T> T Vectorqueue<T>::dequeue()
{
	assert(!isEmpty());
	int dataloc=nextUse;
	nextUse++;
	if(nextUse>=max)
		nextUse=0;
	return data[dataloc];
}
template<class T> void Vectorqueue<T>::enqueue(T value)
{
	data[nextSlot++]=value;
	if(nextSlot>=max)
		nextSlot=0;
	assert(nextSlot!=nextUse);
}
template<class T> T Vectorqueue<T>::front()const
{
	assert(!isEmpty());
	return data[nextUse];
}
template<class T> int Vectorqueue<T>::isEmpty()const
{
	return nextSlot==nextUse;
}*/

//---------------------------------------------------------------------------------向量队列
//-----------------------------------------------------------------------------------表队列
template<class T> 
class Listqueue:public queue<T>
{
public:
	Listqueue();
	Listqueue(const Listqueue<T> & source);
	virtual void deleteAllValuess();
	virtual T dequeue();
	virtual bool enqueue(T values);
	virtual T front()const;
	virtual int isEmpty()const;
private:
	doubleEndlist<T> data;
};
template<class T> Listqueue<T>::Listqueue():data()
{
	deleteAllValuess();
}
template<class T> Listqueue<T>::Listqueue(const Listqueue<T> & source):data(source.data)
{
}
template<class T> void Listqueue<T>::deleteAllValuess()
{
	data.deleteAllValues();
}
template<class T> T Listqueue<T>::dequeue()
{
	T val=data.firstElement();
	data.removeFirst();
	return val;
}
template<class T> bool Listqueue<T>::enqueue(T value)
{
	data.addToEnd(value);
	return true;
}
template<class T> T Listqueue<T>::front()const
{
	return data.firstElement();
}
template<class T> int Listqueue<T>::isEmpty()const
{
	return data.isEmpty();
}
//-----------------------------------------------------------------------------------表队列
#endif