circlequene.cpp

用模板实现环形队列

#include <malloc.h>
#include <iostream.h>
#include <string>
#include <memory.h>
using namespace std ;

template<class T>      
class CircleQuene{  
protected:   int head;   //队头指针   
			 int tail;   //队尾指针 
			 int qsize;    //队列长度
			 T *elements;//存放队列元素的数组   
			 int maxsize;//队列最大可容纳元素个数     
public:   CircleQuene(int i=10);    //构造函数   
		  ~CircleQuene();    //析构函数   
		    
		  void PushTail(T);  //将新元素插入在队尾   
		  bool PopFront(T&);  //从队头取一个元素   
 
		  bool IsFull()const     //判队列是否为满   
		  {
			  return (tail+1)%maxsize==head;
		  }   
		  bool IsEmpty()     //判队列是否为空   
		  {
			  return head==tail;
		  }
		  bool append();          //当空间满时追加分配空间
		  int get_maxsize()
		  {
			  return maxsize-1;
		  }
		  int get_qsize()
		  {
			  return qsize;
		  }
		  
};

template <class T>
CircleQuene<T>::CircleQuene(int i)
{
	head=tail=0;   //将队列设置为空队列  
	maxsize=i<10?10:i; //设置队列的最大长度，最小为 10  
	qsize=0;  
	elements=new T[maxsize];//给队列分配内存空间 
	if(elements==0)  //失败，警告
	{
		cout<<"内存分配失败"<<endl;
	}
}

template <class T>
CircleQuene<T>::~CircleQuene()
{
	delete []elements;
} 


template <class T>
void CircleQuene<T>::PushTail(T element)
{
	if(IsFull())   //若队满，追加空间
	{
		append();
	}
    
	tail=(tail+1)%maxsize;  //尾指针加 1  
	elements[tail]=element;   //给队尾赋值
	qsize++;     //队长加 1
}

template <class T>
bool CircleQuene<T>::PopFront(T &element)
{
	if(IsEmpty())
	{
		cout<<"队列为空"<<endl;    //若队空，警告，出错处理
		return false;
	}
	head=(head+1)%maxsize;  //头指针加 1  
	element=elements[head];    //取出队头元素  
	qsize--;      //队长减 1  
	return true; 
}

template <class T>
bool CircleQuene<T>::append()
{
	T *p,*temp;
	p=new T[maxsize+10];        //每次追加10个内存空间
	if(!p)
	{
		cout<<"内存追加失败"<<endl;
		return false;
	}
    memmove(p,elements,sizeof(T)*maxsize);
	temp=elements;
	elements=p;
	delete []temp;
	maxsize=maxsize+10;
	return true;
}

void main()
{
/////////测试队列元素为char类型////////////////////////////////////
	CircleQuene<char> char_quene(15);
	char p[]="1234567890123456";
	int i;
	for(i=0;i<15;i++)
		char_quene.PushTail(p[i]);
	char a;
	for(i=0;i<16;i++)
	{
		if(char_quene.PopFront(a))
			cout<<" "<<a;
		else 
			break;
	}
	cout<<endl;
	cout<<"环形队列存储元素最大值:"<<char_quene.get_maxsize()<<endl;
	cout<<"当前的有效个数:"<<char_quene.get_qsize()<<endl;
/////////测试队列元素为double类型////////////////////////////////////
	CircleQuene<double> double_quene(15);
	double input=1.1;
	for(i=0;i<14;i++)
	{
		double_quene.PushTail(input);
		input+=1.0;
	}
	double d;
	for(i=0;i<16;i++)
	{
		if(double_quene.PopFront(d))
			cout<<"  "<<d;
		else 
			break;
	}
	cout<<endl;
	cout<<"环形队列存储元素最大值:"<<double_quene.get_maxsize()<<endl;
	cout<<"当前的有效个数:"<<double_quene.get_qsize()<<endl;

/////////测试队列元素为string类型///////////////////////////////////
	CircleQuene<string> string_quene(4);
	string str("text");
	for(i=0;i<9;i++)
		string_quene.PushTail(str);
	string str2;
	for(i=0;i<8;i++)
	{
		if(string_quene.PopFront(str2))
			cout<<" "<<str2.c_str();
		else 
			break;
	}
	cout<<endl;
	cout<<"环形队列存储元素最大值:"<<string_quene.get_maxsize()<<endl;
	cout<<"当前的有效个数:"<<string_quene.get_qsize()<<endl;
}