#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;
}