【数据结构与算法（C语言）】循环队列图解

1. 前言

将队列的头尾相接，臆造成环状的顺序存储结构称为循环队列。

普通的顺序存储队列会出现 假溢出 情况。如下面三张图（三个步骤）描述的情况

1.1 普通循环队列假溢出

下面来看看普通队列是如何产生假溢出现象的。

1.1.1 初始化队列

此时队列为空队列。头指针和尾指针都指向第一个空间

1.1.2 插满队列

插入J1、J2、J3、J4、J5、J6，因为q->rear=6，说明队列已满

1.1.3 删除元素后，再插入元素

删除J1，J2，按道理应该是空出两个空间，可以插入新元素，但此时q ->rear指向6号地址，还是判定队列已满，如果再插入元素，q-rear=7,则队列溢出。但实际队列是有空间的

1.2 循环队列

普通的循环队列有上述假溢出缺点。于是乎，循环队列就应运而生了。

循环队列的解决假溢出方法 如下面三张图中展示的步骤：

1.2.1 插入元素，队列已满

还剩一个空间的时候，队列就满了。这样设置的原因是，如果不浪费一个空间的话，当 queue.front=queue.rear，可能会有两种情况，一个是队列为空，一个是队列已满。如果预留一个空间的话，可以用 queue.rear + 1=queue.front 判断队列已满，这样和队列为空的判断方式不冲突。

1.2.2 将元素J1、J2出列，循环队列又空出两个空间

1.2.3 元素J6可以继续入列

2. 存储结构和函数说明

2.1 队列的结构

typedef struct{QElemType * base;  //存储空间 int front;	   //队列头的下标int rear; 	   //队列尾的下标
}SqQueue;     //定义一个队列类型 

2.2 基本操作函数

和上一篇博客中的链式队列差不多，一共8个函数。

Status InitQueue(SqQueue * queue); //初始化队列
void DestroyQueue(SqQueue *queue); //销毁队列
Status ClearQueue(SqQueue * queue);//清空队列
Status QueueEmpty(SqQueue queue);  //判断队列是否为空
Status GetHead(SqQueue queue ,QElemType * e); //获取队列头元素
int QueueLength(SqQueue queue);			//获取队列长度
Status EnQueue(SqQueue  * queue, QElemType e); //元素入列
Status DeQueue(SqQueue * queue ,QElemType * e); //元素出列

2.3 初始化队列

原型：Status InitQueue(SqQueue * queue)
说明：初始化队列,申请一个头结点的内存

/*初始化队列,申请一个头结点的内存*/
Status InitQueue(SqQueue * queue)
{queue->base = (QElemType *) malloc(sizeof(QElemType)*MAXSIZE); //申请一个队列结点作为头结点的内存地址给 队头指针；if(queue->base == NULL)return FALSE;queue->front = queue->rear =0;return TRUE;
}

2.4 销毁队列 DestroyQueue

原型 ：void DestroyQueue(SqQueue *queue)
功能 ：销毁队列，释放队列的数据空间

/*销毁栈，释放队列的数据空间*/
void DestroyQueue(SqQueue *queue)
{free(queue->base);queue->front= queue->rear =0;
}

2.5 清空队列 ClearQueue

原型：Status ClearQueue(SqQueue * queue)
功能 ：清空队列的元素，但队列的空间保留

//将队列queue清空
Status ClearQueue(SqQueue * queue)
{queue->front = queue->rear = 0;return OK;	
}

2.6 获取队列第一个元素 GetHead

原型：Status GetHead(SqQueue queue ,QElemType * e)
功能 ：获取队列第一个元素,注意 不是删除元素

//获取队列第一个元素
Status GetHead(SqQueue queue ,QElemType * e)
{if(QueueEmpty(queue))return FALSE;*e=queue.base[queue.front];return TRUE;
}

2.7 获取队列长度

原型：int QueueLength(SqQueue queue)
功能 ：队列长度

//返回队列长度
int QueueLength(SqQueue queue)
{return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
}

2.8 元素入列 EnQueue

原型：Status EnQueue(SqQueue * queue, QElemType e)
功能 ：元素e 插入队列queue

//元素e 插入队列queue
Status EnQueue(SqQueue  * queue, QElemType e)
{if((queue->rear + 1) % MAXSIZE == queue->front) //队列满，return FALSE ;queue->base[queue->rear]=e;       //e 插入队列尾部，队尾加1queue->rear = (queue->rear + 1) % MAXSIZE;return TRUE;
}

2.9 元素出列 DeQueue

原型：Status DeQueue(SqQueue * queue ,QElemType * e)
功能 ：若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR

//若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status DeQueue(SqQueue * queue ,QElemType * e)
{if(QueueEmpty( *queue))return FALSE;*e = queue->base[queue->front];queue->front= (queue->front + 1) % MAXSIZE;return TRUE;
}

2.10 遍历队列 QueueTraverse

原型：Status QueueTraverse(SqQueue queue,void (*visit)())
功能 ：遍历队列，对队列的每个元素调用Visit函数

//遍历队列，对队列的每个元素调用Visit函数
Status QueueTraverse(SqQueue queue,void (*visit)())
{int i = queue.front;if(QueueEmpty(queue))return FALSE ;if(queue.front < queue.rear)	while(i < queue.rear)visit(queue.base[i++]);else{while(i< MAXSIZE)visit(queue.base[i++]);i=0;while(i<queue.rear)visit(queue.base[i++]);}return TRUE;
}

3. 完整源码和测试代码

#include <stdio.h>
#include <stdlib.h>#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0
#define MAXSIZE 6 //最大值设置为6typedef  int Status;typedef  int QElemType; //定义元素类型为整型typedef struct{QElemType * base;  //存储空间 int front;	   //队列头的下标int rear; 	   //队列尾的下标
}SqQueue;     //定义一个队列类型 Status InitQueue(SqQueue * queue);
void DestroyQueue(SqQueue *queue);
Status ClearQueue(SqQueue * queue);
Status QueueEmpty(SqQueue queue);
Status GetHead(SqQueue queue ,QElemType * e);
int QueueLength(SqQueue queue);
Status EnQueue(SqQueue  * queue, QElemType e);
Status DeQueue(SqQueue * queue ,QElemType * e);/*初始化队列,申请一个头结点的内存*/
Status InitQueue(SqQueue * queue)
{queue->base = (QElemType *) malloc(sizeof(QElemType)*MAXSIZE); //申请一个队列结点作为头结点的内存地址给 队头指针；if(queue->base == NULL)return FALSE;queue->front = queue->rear =0;return TRUE;
}/*销毁队列，释放队列的数据空间*/
void DestroyQueue(SqQueue *queue)
{free(queue->base);queue->front= queue->rear =0;
}//将队列queue清空
Status ClearQueue(SqQueue * queue)
{queue->front = queue->rear = 0;return OK;	
}//判断队列是否为空
Status QueueEmpty(SqQueue queue)
{return queue.front == queue.rear? TRUE:FALSE; 
}//获取队列第一个元素
Status GetHead(SqQueue queue ,QElemType * e)
{if(QueueEmpty(queue))return FALSE;*e=queue.base[queue.front];return TRUE;
}//返回队列长度
int QueueLength(SqQueue queue)
{return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
}//元素e 插入队列queue
Status EnQueue(SqQueue  * queue, QElemType e)
{if((queue->rear + 1) % MAXSIZE == queue->front) //队列满，return FALSE ;queue->base[queue->rear]=e;       //e 插入队列尾部，队尾加1queue->rear = (queue->rear + 1) % MAXSIZE;return TRUE;
}//若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status DeQueue(SqQueue * queue ,QElemType * e)
{if(QueueEmpty( *queue))return FALSE;*e = queue->base[queue->front];queue->front= (queue->front + 1) % MAXSIZE;return TRUE;}
void Visit(QElemType e)
{printf("%3d",e);
}
//遍历队列，对队列的每个元素调用Visit函数
Status QueueTraverse(SqQueue queue,void (*visit)())
{int i = queue.front;if(QueueEmpty(queue))return FALSE ;if(queue.front < queue.rear)	while(i < queue.rear)visit(queue.base[i++]);else{while(i< MAXSIZE)visit(queue.base[i++]);i=0;while(i<queue.rear)visit(queue.base[i++]);}return TRUE;
}int main()
{QElemType e;SqQueue queue;InitQueue(&queue);printf("队头分别插入数字3、4、5、6、7后:");//此时队列已经满了，设置maxsize=6,实际只能存储5个，//因为只剩一个空间，代表队列已满。即 front= (rear+1)%maxsize//如果不留一个空间空着，那么队列满和队列空都是 front=rear,很难分辨EnQueue(&queue,3);EnQueue(&queue,4);EnQueue(&queue,5);EnQueue(&queue,6);EnQueue(&queue,7);QueueTraverse(queue,Visit);printf("\n继续插入数字8");if(EnQueue(&queue,8))printf("\n出问题了，队列满了，还能插入!");elseprintf("\n队列已满，无法插入!");printf("\n删除队头数字后:");DeQueue(&queue,&e);	    //删除后的队列中还剩4个元素QueueTraverse(queue,Visit);printf("\n继续插入8数字后：");EnQueue(&queue,8);	    //数字8被存放到queue.base[5]中了QueueTraverse(queue,Visit);printf("\n清空队列");ClearQueue(&queue);printf("\n队列长度:%d\n",QueueLength(queue));DestroyQueue(&queue);getchar();return 0;
}

4. 测试结果

5. 小结

循环队列的优缺点

5.1 优点：

(a) 解决了普通的顺序存储队列的假溢出问题。
(b) 读取方便、快捷

5.2 缺点

存储空间大小固定，无法根据需要进行扩展。