#pragma once

template<class DT>
struct SqQueue
{
	DT* base;														// 存储空间基地址
	int front;														// 队头指针，指向队首元素
	int rear;														// 队尾指针，指向队尾元素的后面
	int queuesize;													// 队列容量
};

template<class DT>													// 算法3.14 初始化队列
bool InitQueue(SqQueue<DT>& Q, int m)								// 创建容量为m的空队列
{
	Q.base = new DT[m];												// 1. 申请一组连续的内存空间
	if (!Q.base) exit(1);											// 申请失败，退出
	Q.front = Q.rear = 0;											// 2. 申请成功，为队列属性赋值
	Q.queuesize = m;
	return true;													// 3. 返回true
}

template<class DT>													// 算法3.15 销毁队列
void DestroyQueue(SqQueue<DT>& Q)									// 销毁循环队列
{
	delete[] Q.base;												// 1. 释放循环队列占用的内存空间
	Q.front = Q.rear = 0;											// 2. 为队列属性赋值
	Q.queuesize = 0;
}

template<class DT>													// 算法3.16 入队
bool EnQueue(SqQueue<DT>& Q, DT e)									// 在队尾插入一个新元素
{
	if ((Q.rear + 1) % Q.queuesize == Q.front)						// 1. 队满的情况
		return false;												// 无法入队，返回false
	Q.base[Q.rear] = e;												// 2. 元素e放在队尾指针处
	Q.rear = (Q.rear + 1) % Q.queuesize;							// 队尾指针增1
	return true;													// 3. 返回true
}

template<class DT>													// 算法3.17 出队
bool DeQueue(SqQueue<DT>& Q, DT& e)									// 删除队头元素
{
	if (Q.front == Q.rear)											// 1. 队空的情况
		return false;												// 无法出队，返回false
	e = Q.base[Q.front];											// 2. 取队头元素，赋值给e
	Q.front = (Q.front + 1) % Q.queuesize;							// 队头指针加1
	return true;													// 3. 返回true
}

template<class DT>													// 算法3.18 取队头元素
bool GetHead(SqQueue<DT> Q, DT& e)									// 取队头元素
{
	if (Q.front == Q.rear)											// 1. 队空的情况
		return false;												// 无队头元素，返回false
	e = Q.base[Q.front];											// 2. 取队头元素，赋值给e
	return true;													// 3. 返回true
}

template<class DT>
bool GetTail(SqQueue<DT> Q, DT& e)									// 取队尾元素
{
	if (Q.front == Q.rear)											// 1. 队空的情况
		return false;												// 无队尾元素，返回false
	e = Q.base[(Q.rear - 1 + Q.queuesize) % Q.queuesize];			// 2. 取队尾元素，赋值给e
	return true;													// 3. 返回true
}

template<class DT>
int QueueLength(SqQueue<DT> Q)										// 测表长
{
	return (Q.rear - Q.front + Q.queuesize) % Q.queuesize;
}

template<class DT>
bool QueueEmpty(SqQueue<DT> Q)										// 判队空
{
	return Q.front == Q.rear;
}

template<class DT>
bool QueueFull(SqQueue<DT> Q)										// 判队满
{
	return (Q.rear + 1) % Q.queuesize == Q.front;
}

template<class DT>
void ClearQueue(SqQueue<DT>& Q)										// 清空队
{
	Q.front = Q.rear = 0;
}

template<class DT>
void DispQueue(SqQueue<DT> Q)										// 显示队
{
	int i = Q.front;
	while (i != Q.rear)
	{
		cout << Q.base[i] << " ";
		i = (i + 1) % Q.queuesize;
	}
	cout << endl;
}