【数据结构】之循环队列的实现（C语言）-蒲公英云

文章目录

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

顺序存储队列的缺点

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即时对头，所谓的入队操作，其实就是在队尾追加一个元素，不需要移动任何元素。
在这里插入图片描述
与栈不同的是，队列出队元素是在对头，即下标为0的位置，那也就意味着，队列中所有的元素都得向前移动，以保证队列的对头，也就是下标为0的位置不为空。

为了避免当只有一个元素时，队头和队尾重合使处理变的麻烦，所以引入两个指针，front指针指向对头元素，rear指针指向队尾元素的下一个位置，这样放front = rear时，此队列为空。

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

循环队列定义

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

上面的例子，把rear的指向改为下标为0的位置。
在这里插入图片描述
接着入队a6，将它放置于下标为0处，rear指针指向下标为1处。若在入队a7，则rear指针就与front指针重合，同时指向下标为2的位置。

那么问题来了,此时如何判断队列是空还是满呢？

一：设置一个标识变量flag，当front == rear，且flag=0时队列为空，当front==rear，且flag =1时为队满。
二：当队列为空时，条件就是front=rear，队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。如下图所示。

一般采用第二种办法，由于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;
}