【数据结构】之循环队列的实现（C语言）

灰太狼 2023-02-15 12:39 19阅读 0赞

### 文章目录 ###

*   *  顺序存储队列的缺点
     *  循环队列定义
     *   *  完整代码

## 顺序存储队列的缺点 ##

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即时对头，所谓的入队操作，其实就是在队尾追加一个元素，不需要移动任何元素。  
![在这里插入图片描述][20200605122954522.png]  
与栈不同的是，队列出队元素是在对头，即下标为0的位置，那也就意味着，队列中所有的元素都得向前移动，以保证队列的对头，也就是下标为0的位置不为空。  
![在这里插入图片描述][20200605123215720.png]  
为了避免当只有一个元素时，队头和队尾重合使处理变的麻烦，所以引入两个指针，**front指针指向对头元素，rear指针指向队尾元素的下一个位置，这样放front = rear时，此队列为空。**

假设长度为5的数组，初始状态如下左图所示，front与rear指针均指向下标为0的位置。然后入队a1，a2，a3,a4，front指针依然指向下标为0的位置，而rear指针指向下标为4的位置。  
![在这里插入图片描述][20200605123723678.png]  
出队a1,a2,则front指针指向下标为2的位置，rear不变，如下图左图。在入队a5，此时front指针不变，**rear指针移动到数组之外，此时产生数组越界的错误，可实际上，队列的下标0和1的地方还是空闲的，这种现象称为“假溢出”**  
![在这里插入图片描述][20200605123933966.png]

## 循环队列定义 ##

解决假溢出的办法就是后面满了，在重头开始，也就是首尾相接的循环。  
**我们把队列的这种首尾相接的顺序存储结构称为循环队列。**

上面的例子，把rear的指向改为下标为0的位置。  
![在这里插入图片描述][20200605124329268.png]  
接着入队a6，将它放置于下标为0处，rear指针指向下标为1处。若在入队a7，则rear指针就与front指针重合，同时指向下标为2的位置。  
![在这里插入图片描述][20200605124532470.png]  
那么问题来了,此时如何判断队列是空还是满呢？

*  一：设置一个标识变量flag，当front == rear，且flag=0时队列为空，当front==rear，且flag =1时为队满。
 *  二：当队列为空时，条件就是front=rear，队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。如下图所示。  
    ![在这里插入图片描述][20200605125039619.png]

一般采用第二种办法，由于rear可能比front大，也可能比front小，所以尽管他们只相差一个位置时就是满的情况，但是也可能相差整整一圈。  
**设队列的最大容量为QueneSize，那么队满的条件是(rear+1)%QueneSize ==front (取模%的目的视为了整合rear与front大小为一个问题)**

**通用的计算队列的长度公式为  
（rear-front+QueneSize）%QueneSize**

循环队列的顺序存储结构代码如下

typedef int QElemType      //QElemType根据实际定，这里设为int
    //存储结构
    typedef struct
    {
        
    	QElemType data[MAXSIZE];
    	int front; //头指针
    	int rear； //尾指针，若队列不为空，指向队尾元素的下一个位置
    }SqQuene

循环队列的初始化代码

//初始化一个空队列
    Status InitQuene（SqQuene *Q）
    {
        
    	Q->front=0；
    	Q->rear=0;
    	return OK;
    }

求循环队列长度

//返回Q的元素个数，也就是队列的当前长度
    int QueneLength(SqQuene Q)
    {
        
    	return (Q.rear - Q.front +MAXSIZE)%MAXSIZE;
    }

入队操作

Ststus EnQuene(SqQuene *Q,QElemType e)
    {
        
    	if(Q->rear+1%MAXSIZE == Q->front) //判断队满
    		return ERROR;
    	Q->data[Q->rear] =e;            //元素e赋值给队尾
    	Q->rear=（Q->rear+1）%MAXSIZE   //rear指向后移
    	return OK;
    }

出队操作

Ststus DeQuene(SqQuene *Q,QElemType e)
    {
        
    	if(Q->front == Q->rear)  //判断队空
    		return ERROR;
    	*e=Q->data[Q->front]；         //队头元素赋值给e
    	Q->front=(Q->front+1)%MAXSIZE; //front后移
    }

### 完整代码 ###

#include <stdio.h>
    #include <malloc.h>
    typedef int QElemType;
    typedef int Status;
    #define MaxQSize 10
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define OVERFLOW -1
    typedef struct
    {
        
    	QElemType *base;
    	int front, rear;
    }SqQueue;
    //初始化循环队列
    Status InitQueue(SqQueue &Q)
    {
        
    	Q.base = (QElemType*)malloc(MaxQSize*sizeof(QElemType));
    	if (Q.base == NULL)
    	{
        
    		puts("分配内存空间失败！"); 
    		exit(OVERFLOW);
    	}
    	Q.front = Q.rear = 0;
    	return 0;
    }
    //将循环队列清空
    Status ClearQueue(SqQueue &Q)
    {
        
    	Q.front = Q.rear = 0;
    }
    //求队列元素的个数
    Status QueueLength(SqQueue Q)
    {
        
    	return (Q.rear - Q.front + MaxQSize) % MaxQSize;
    }
    //插入元素到循环队列
    Status EnSqQueue(SqQueue &Q, QElemType e)
    {
        
    	if ((Q.rear + 1) % MaxQSize == Q.front){
        puts("队列已满！"); return ERROR; /*队列满*/}
    	Q.base[Q.rear] = e; //元素e入队
    	Q.rear = (Q.rear + 1) % MaxQSize; //修改队尾指针
    	return OK;
    }
    //从循环队列中删除元素
    Status DeSqQueue(SqQueue &Q, QElemType &e)
    {
        
    	if (Q.front == Q.rear)
    	return ERROR;
    	e = Q.base[Q.front]; //取队头元素至e
    	Q.front = (Q.front + 1) % MaxQSize; //修改队头指针,如果超内存，循环 
    	return OK;
    }
    //判断一个循环队列是否为空队列
    Status isQueueEmpty(SqQueue Q)
    {
        
    	if (Q.front == Q.rear)
    	return TRUE;
    	else
    	return FALSE;
    }
    
    int main()
    {
        
    	int i, e;
    	SqQueue Q;
    	InitQueue(Q);
    	for (i=0; i<MaxQSize; i++)	//只有MaxQSize个数据进队列
    		EnSqQueue(Q, i);
    	i = QueueLength(Q);
    	printf("队列里的元素有%d个\n", i);
    	for (i=0; i<3; i++)
    	{
        
    		DeSqQueue(Q, e);
    		printf("%d ", e);
    	}
    	printf("\n");
    	i = QueueLength(Q);
    	printf("队列里的元素有%d个\n", i);
    	for (i=10; i<12; i++)
    		EnSqQueue(Q, i);
    	i = QueueLength(Q);
    	printf("队列里的元素有%d个\n", i);
    	ClearQueue(Q);
    	i = QueueLength(Q);
    	printf("队列里的元素有%d个\n", i);
    	return 0;
    }

[20200605122954522.png]: https://img-blog.csdnimg.cn/20200605122954522.png
[20200605123215720.png]: https://img-blog.csdnimg.cn/20200605123215720.png
[20200605123723678.png]: https://img-blog.csdnimg.cn/20200605123723678.png
[20200605123933966.png]: https://img-blog.csdnimg.cn/20200605123933966.png
[20200605124329268.png]: https://img-blog.csdnimg.cn/20200605124329268.png
[20200605124532470.png]: https://img-blog.csdnimg.cn/20200605124532470.png
[20200605125039619.png]: https://img-blog.csdnimg.cn/20200605125039619.png