//循環(huán)（順序）隊列類
#include <assert.h>
#include <iostream>
using namespace std;
template <class T>
class SeqQueue   //循環(huán)隊列的類定義
{ 
public:
	SeqQueue(int sz = 10); //構(gòu)造函數(shù)
	~SeqQueue() {delete[] elements;} //析構(gòu)函數(shù)
	bool EnQueue(const T& x);
	//若隊列不滿，則將x進(jìn)隊，否則隊溢出處理。
	bool  DeQueue(T& x);
	//若隊列不空，則退出隊頭元素x并由函數(shù)返回true，否則隊空，返回false。
	void makeEmpty() {front = rear = 0;}
	//置空操作：隊頭指針和隊尾指針置0
	bool IsEmpty()const {return (front == rear) ? true : false;}
	//判隊列空否。若隊列空，則函數(shù)返回true；否則返回false。
	bool IsFull()const
	{return ((rear+1)% maxSize == front) ? true : false;}
	//判隊列滿否。若隊列滿，則函數(shù)返回true；否則返回false。
	bool getFront(T& x) const;
	//若隊列不為空，則函數(shù)返回true及隊頭元素的值，否則返回false。
	int getSize()const {return (rear-front+maxSize)% maxSize;}
	//求隊列元素個數(shù)
	friend ostream& operator<<(ostream& os,SeqQueue<T>& Q)
	{
		for (int i = Q.front; i != Q.rear; i = (i+1) % Q.maxSize)
			os << Q.elements[i] <<" ";
		os<<endl;
		return os;
	}
	//輸出隊列中元素的重載操作 <<

protected:

	int rear, front; //隊尾與隊頭指針
	T *elements; //存放隊列元素的數(shù)組
	int maxSize; //隊列最大可容納元素個數(shù)

};

template <class T>
SeqQueue<T>::SeqQueue(int sz) : front(0),rear(0),maxSize(sz) {
	//建立一個最大具有maxSize個元素的空隊列。
	elements = new T[maxSize]; //創(chuàng)建隊列空間
	assert (elements != NULL); //斷言: 動態(tài)存儲分配成功與否
};

template <class T>
bool SeqQueue<T>::EnQueue(const T& x) {
	//若隊列不滿, 則將元素x插入到該隊列的隊尾, 否則出錯處理。
	if (IsFull() == true) return false; //隊列滿則插入失敗,返回
	elements[rear] = x; //按照隊尾指針指示位置插入
	rear = (rear+1) % maxSize; //隊尾指針加1
	return true; //插入成功,返回
};


template <class T>
bool SeqQueue<T>::DeQueue(T& x) {
	//若隊列不空則函數(shù)退掉一個隊頭元素并返回true, 否則函數(shù)返回false。
	if (IsEmpty() == true) return false; //若隊列空則刪除失敗,返回
	x = elements[front];
	front = (front+1) % maxSize; //隊頭指針加1
	return true; //刪除成功,返回
};

template <class T>
bool SeqQueue<T>::getFront(T& x)const {
	//若隊列不空則函數(shù)返回該隊列隊頭元素的值。
	if (IsEmpty() == true) return false; //若隊列空則函數(shù)返回空指針
	x = elements[front]; //返回隊頭元素的值
	return true;
};