循环队列样式结构图：



优点：

解决了顺序队列只能从队尾插入元素而导致空间的浪费；

问题：

在循环队列中，空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性；
解决方法
1、使用额外的标记

（1）引入Size标记

来记录队列的长度，当size为队列最大长度时为满，size=0为空；

（2）引入tag标记

删除时tag=0，插入时tag=1；当front == rear时，如果 tag==0则为空，否则为满；

2、仅使用n-1个数组空间
空闲单元法：


循环队列满的条件：

（rear+1）% N == front；

循环队列空的条件：

（front==rear）；

队列是一个特殊的线性表，队列简称为“对”。

队列有两种存储结构，一种是顺序排列，另一种是链式排列。



下面我们以顺序队列为例。

队列有一特征名为“先进先出”。

队列的入队只允许队尾操作，rear增加一位。队头front不允许修改。

而队列的出队则相反，只允许队头操作，front增加一位，队尾rear不允许修改。
如下队列的直观图，因为队列的入队和出队都指定队列的一端操作，所以当队列有了出队的操作之后，队列的前端会有空位置，即使再进行入队的操作，也是在队列的另一端插入，队列前端的空位置不会被插入。


而且当队列为满时再插入元素，会发生“溢出”的现象，但是这可能并不是真正的溢出，因为队列的前面可能会有空位置，所以这是“假溢出”。

那么如何避免这种“假溢出”的现象发生，充分利用队列的空间呢，这就需要用到循环队列。
如下图我们可以看到在循环队列里面，在对满的情况下，队列里面只会空出一个位置，而对在出队的操作之后在入队，可以把之前的空位置给补上，这样就很好的避免了“假溢出”的信息发生。

队列：只允许在一端进行插入操作(队尾)，在另一端进行删除操作(队头)。 队列的特征就是： 先进先出。
队列的思想及实现也同样非常简单。在生活中的各种常常都需要排队进行，键盘中缓存区、操作系统中的作业调度等都有用到队列先进先出的思想。在这里同样用一个示意图展示队列的基本思想。
下面笔者才用数组存储元素，实现了一个循环队列。
队列中最重要的一个方法就是队列是否满的判断，
判断队列是否为满。队满： rear + 2 = front 或 front + maxSize -2 = rear
判断队列是否为空。队空： rear + 1 = front 或 front + maxSize -1 = rear
/** 判断队列是否为空。队空： rear + 1 = front 或 front + maxSize -1 = rear
*  通过数组容量比队列数据项的最大值大一，来区分对空和对满。
*/
public boolean isEmpty(){
return (rear + 1 == front || front + maxSize -1 == rear);
}
/**判断队列是否为满。 队满： rear + 2 = front 或 front + maxSize -2 = rear
* 通过数组容量比队列数据项的最大值大一，来区分对空和对满。
*/
public boolean isFull(){
return (rear + 2 == front || front + maxSize -2 == rear);
}
获取队列大小(元素个数)：可以通过队头队尾计算出队列的大小，也可以通过一个计数器，当入队是加1，出队是减1.
/** 获取队列的大小
*/
public int queueSize(){
if(rear >= front){
return rear - front +1;
}else {
return maxSize - front + (rear + 1);
}
}
出队入队查看队头元素：
入队                           出队
全部代码及测试：
package org.TT.Queue;
/**
* 循环队列： 先进先出
*        队列同样是个概念上的辅助工具。这里采用数组完成队列的操作，仍然采用泛型
*        队列的数据项的入队、出队时间复杂度为常数 O(1)。
*        通过队头队尾指针的移动保存所有数据位置不动，而不是移动数据项。
*        在这里，数组的大小比队列存放数据元素大1，主要是为了方便队满的判断。
*/
public class Queue{
private int maxSize;   // 队列最多容纳数量
private Object[] queueArray;
private int front;   // 队头
private int rear;// 队尾
private int size;
public Queue(int length) {
maxSize = length;
queueArray = new Object[maxSize];
front = 0;
rear = -1;
size = 0;
}
/**入队： 先将rear(队为指针) 加1， 后将数据项存入rear的位置。
*当rear 指向maxSize -1 的位置时，将rear 设置为-1(循环队列)，加1 后存入数据项。
*/
public void enQueue(T str){
if(isFull()){    // 入队之前先检查队列是否已满，已满则抛出异常。
throw new RuntimeException("队列已满，" + str + " 不能入队！");
}
if(rear == maxSize -1){
rear = -1;
}
queueArray[++rear] = str;  // 先将 rear 加1，后取值
size++;
}
/**出队： 先取出front 的值，然后将front 减1
* 如果 front 超过了数组的顶端，将 front 设置为 0(循环队列)
*/
@SuppressWarnings("unchecked")
public T deQueue(){
if(isEmpty()){   // 出队之前先检查队列是否为空， 为空则抛出异常。
throw new RuntimeException("队列为空，不能出队！");
}
T str = (T) queueArray[front++];  // 先去 queueArray[front] 的值，后将front 加1
if(front == maxSize){
front = 0;
}
size--;
return str;
}
/**查看对头数据项
*/
@SuppressWarnings("unchecked")
public T peek(){
if(isEmpty()){   // 查看队头时，判断是否为空， 为空则抛出异常。
throw new RuntimeException("队列为空！");
}
return (T) queueArray[front];
}
/** 判断队列是否为空。队空： rear + 1 = front 或 front + maxSize -1 = rear
*  通过数组容量比队列数据项的最大值大一，来区分对空和对满。
*/
public boolean isEmpty(){
return (rear + 1 == front || front + maxSize -1 == rear);
}
/**判断队列是否为满。 队满： rear + 2 = front 或 front + maxSize -2 = rear
* 通过数组容量比队列数据项的最大值大一，来区分对空和对满。
*/
public boolean isFull(){
return (rear + 2 == front || front + maxSize -2 == rear);
}
/** 获取队列的大小
*/
public int queueSize(){
/* 可以通过队头队尾计算出队列的大小，也可以通过一个计数器，当入队是加1，出队是减1.
if(rear >= front){
return rear - front +1;
}else {
return maxSize - front + (rear + 1);
}
*/
return size;
}
public static void main(String[] args) {
Queuequeue = new Queue<>(5);
queue.enQueue("a");
queue.enQueue("b");
queue.enQueue("c");
queue.enQueue("d");
queue.deQueue();
queue.deQueue();
System.out.println("队列是否为空： " + queue.isEmpty() + "  队列是否满： " + queue.isFull());
System.out.println("队列大小：" + queue.queueSize());
int size = queue.queueSize();
for(int i = 0; i < size; i++){
String str = queue.deQueue();
System.out.print(str + " ");
}
}
}
结果
关于链队列只是在单链表的基础上多了简单的修改，在单链表中添加一个尾指针即可，每次入队、出队只分别对单链表的队尾和队首进行插入和删除在操作，由于链队没有队满的限制，所以相对于非常简单，而判空操作只需判断 front == rear 是否成立。 在这里笔者就不列出链队列。在java库中也有队列相关的接口及实现并且还有双端队列、优先队列等类。

循环队列的动态回收方法
题目描述
源代码
最后

题目描述
队列的运算特性是先进先出。队列是一种重要的数据类型，队列在各种类型的系统中应

用广泛。讨论队列的结构特征与操作实现特点，有着重要的意义。实现了循环队列存储空间

的动态增长。但是存储空间在开辟并使用后若闲置， 并且用户不能确定在之后的操作中用

到这些闲置空间时，需要想出一种办法将这部分空间回收。设置循环队列闲置空间达到

QUEUE_FREESIZE 时，按 50%的比例回收大小为 UEUE_FREESIZE*50%的这部分空间。

下面给出了部分的初始定义供设计时参考。
# define QUEUE_INIT_SIZE 5 //队列存储空间的初始分配量
# define QUEUE_INCREMENT 5 //队列存储空间的分配增量
# define QUEUE_FREESIZE 10 //队列存储空间的回收预定值
# define PERCENT 0.5 //队列闲置空间的回收比例**
typedef struct //循环队列类型
{
ElementType *element; //初始化的动态分配存储空间
int front; //队头指针， 若队列非空，指向队列头元素
int rear; //队尾指针， 若队列非空，指向队尾元素的下一个位置
int QueueSize; //当前分配的存储空间（以 sizeof(ElementType)为单位）
}SeqQueue;

源代码
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include <windows.h> 
# define QUEUE_INIT_SIZE 5       //队列存储空间的初始分配量
# define QUEUE_INCREMENT 5  //队列存储空间的分配增量
# define QUEUE_FREESIZE 10      //队列存储空间的回收预定值
# define PERCENT 0.5                  //队列闲置空间的回收比例
#define ElementType int
using namespace std;
typedef struct  //循环队列类型
{
	ElementType* element = NULL;    //一个的数组头指针
	int front;         //队头指针,若队列非空，指向队列头元素
	int rear;       //队尾指针，若队列非空，指向队尾元素的下一个位置
	int QueueSize;     //当前分配的存储空间(以sizeof(ElementType)为单位) ,队列中多余空出来的空间？ 
	int QueueLength; //队列长度(有数据的) 
}SeqQueue;
bool InitQueue(SeqQueue* Q)     //构造一个空队列Q
{
	free(Q->element); 
	Q->element = (ElementType*)malloc(QUEUE_INIT_SIZE * sizeof(ElementType));//相当于int element[5];
	if (!Q->element)
		return false;    //内存开辟失败,报告错误并退出程序
	Q->front = Q->rear = 0;
	Q->QueueSize = QUEUE_INIT_SIZE;       //给队列一个初始空间
	Q->QueueLength = 0;
	return true;
}
//int QueueLength(SeqQueue* Q)  //求队列的长度 
//{
//	int n = ((abs((Q->rear) - (Q->front))) % Q->QueueSize) ;
	int n = (Q->rear-Q->front+Q->QueueSize)%Q->QueueSize; 
//	return n;
//}

int ENQueue(SeqQueue* Q, ElementType e)//入队
{
	ElementType* New_Base;// = (ElementType*)malloc(QUEUE_INIT_SIZE * sizeof(ElementType)) 
	
//	if (((Q->rear + 1) % Q->QueueSize) == Q->front) //判断是否队满 
	if(Q->QueueSize <= Q->QueueLength )//判断是否队满
	{
		New_Base = (int*)malloc( (Q->QueueSize + QUEUE_INCREMENT) * sizeof(ElementType));
		if (!New_Base)
			return -1;
			
		for(int i=0;i<Q->QueueSize;i++){ //把值复制过去 
			New_Base[i] = Q->element[i];
		}
		Q->element = New_Base;
		Q->QueueSize += QUEUE_INCREMENT; 
		
		if (Q->rear < Q->front) // section 3 ，右边部分往右移，修改front的值
		{
			int i = Q->QueueSize -QUEUE_INCREMENT - 1; //
			int j = Q->QueueSize   - 1;
			for (; i >= Q->front; i--, j--)
				Q->element[j] = Q->element[i];
		}
//		cout<<"Q->QueueLength"<<Q->QueueLength<<" Q->QueueSize"<<Q->QueueSize<<endl;
		if(Q->QueueLength   == Q->QueueSize - QUEUE_INCREMENT) // 队列满了
		{
			Q->rear =  Q->QueueLength;
		}
			
	}
//	cout<<"###rear:"<<Q->rear<<endl;
	Q->element[Q->rear] = e; //真正的入队 
	Q->QueueLength++; //队列长度加1 
	Q->rear = (Q->rear + 1) % Q->QueueSize; //rear向下移一位 
//	cout<<"front:"<<Q->front<<" rear:"<<Q->rear<<endl;
	return 0;
}

//循环队列中元素的出队操作,出队操作按上面分析结果,实现算法如下:
bool DeleteQueue(SeqQueue* Q)//出队操作的实现算法
{
	int i, j, cnt;
	
	int hsgs = int(QUEUE_FREESIZE * PERCENT);    //回收个数为限定值QUEUE_FREESIZE的50% , 5

	ElementType* newbase;
	if (Q->QueueLength<=0) //Q->rear == Q->front     =-============================!!!!!!!!!!!!
		return false;     //队列为空则报告错误并退出程序
		
	Q->front = (Q->front + 1) % Q->QueueSize;//队头出队 
	Q->QueueLength--;
	
	if (  Q->QueueSize - Q->QueueLength  >= QUEUE_FREESIZE )    //判断闲置空间是否达到定值 ,Q->QueueSize - LEN  >= QUEUE_FREESIZE -1 
	{
		if (Q->front > Q->rear)    //判断队头指针与队尾指针的相对位置,情形3
		{
			for (i = Q->QueueSize - hsgs - 1, j = Q->QueueSize - 1; j >= Q->front; i--, j--)
				Q->element[i] = Q->element[j];    //移动Q->front开始到Q->QueueSize结束的cnt个元素
			
			cnt = Q->QueueSize - Q->front; // 情况三下，右边部分有多少个 
			Q->front = Q->QueueSize - hsgs - cnt;    //修改队头指针
		}
		
		else{
		
			if (Q->QueueSize -(Q->rear )< hsgs)   //判断队尾指针后的闲置空间是否不够回收,情形2 ,Q->QueueSize - (Q->rear + 1) < hsgs
			{
				for (i = 0, j = Q->front; j < Q->rear; i++, j++)
					Q->element[i] = Q->element[j];   //移动所有元素的位置
				Q->front = 0;   //令队头指针指向队列首位置
				Q->rear = Q->front + Q->QueueLength;   //队尾指针指向最后一个元素的后一个位置
			}
		}
		newbase = (ElementType*)realloc(Q->element, (Q->QueueSize - hsgs) * sizeof(ElementType));    //回收空闲空间
		if (!newbase)
			return false;   //内存分配失败，报告错误并退出程序

		Q->element = newbase;
		Q->QueueSize = Q->QueueSize - hsgs;    //修改存储空间的大小
	}
	return true;
}
void meun(){
	cout<<"==========================="<<endl
		<<"| 1. 入队		  |"<<endl
		<<"| 2. 出队      		  |"<<endl
		<<"| 3. 查看队列	  	  |"<<endl 
		<<"| 4. 重置队列	  	  |"<<endl
		<<"| 0. 退出		  |"<<endl
		<<"==========================="<<endl;
}
int main()
{
	int n ;
	ElementType x;
	SeqQueue Q;
	InitQueue(&Q); // 初始化循环队列,并且分配空间
	
	while(true){
		int select;
		system("Cls");
		meun();
		cout<<"请选择: ";
		cin>>select; 
		switch(select){
			case 1:
				cout<<"你要入队几个数据: ";
				cin>>n; // 11
				cout<<"请输入这些数据: ";
				for (int i = 0; i < n; i++)// 入队 
				{
					cin >> x;
					ENQueue(&Q, x); 
				}
				cout<<"* 初始:"<<endl; 
				cout << "队列长度：" <<  Q.QueueLength << endl; //11-7 
				cout << "空闲空间长度：" << Q.QueueSize - Q.QueueLength << endl; // 
				system("pause");
				break;
			case 2:
				cout<<"你要出队几个数据：";
				cin>>n; 
				for(int i=0;i<n;i++){
					DeleteQueue(&Q);
					cout<<"======================"<<endl;
					cout<<"* 出队"<<i+1<<"个后："<<endl;
					cout << "队列长度：" <<  Q.QueueLength << endl; //
					cout << "空闲空间长度：" << Q.QueueSize - Q.QueueLength << endl; //  
				}
				system("pause");
				break;
			case 3:
				cout<<"//tips: 有效数据外显示@"<<endl;
				cout<<"front:"<<Q.front<<" rear:"<<Q.rear<<endl;
				cout<<"QueueLength:"<<Q.QueueLength<<" QueueSize:"<<Q.QueueSize<<endl;
				if(Q.QueueLength<Q.QueueSize){ // 如果队列没满 
					if(Q.front<= Q.rear) 
						for(int i=0;i<Q.QueueSize;i++){
							if(i>=Q.front && i<=Q.rear-1)
								cout<<Q.element[i]<<" ";
							else cout<<"@ ";
						}
					else 
						for(int i=0;i<Q.QueueSize;i++){
							if(i >= Q.rear && i < Q.front )
								cout<<"@ ";
							else cout<<Q.element[i]<<" ";
						}
				}
				else 
					for(int i=0;i<Q.QueueSize;i++){
						cout<<Q.element[i]<<" ";
					}
				cout<<endl;
//				for(int i=0;i<Q.QueueSize;i++)
//					cout<<Q.element[i]<<" "; 
				system("pause");
				break;
			case 4:
				InitQueue(&Q);
				cout<<"重置完毕！"<<endl;
				system("pause");
				break;
			case 0:
				return 0;
			default:
				cout<<"error! 请重新选择!"<<endl;
				system("pause");
				break;
				
		}
	}

}


最后
在某些频繁入队又出队又入队出队等情况的多种组合下，功能3还是会有bug存在，以后有空再改吧。。。