数据结构：基于数组的环形队列（循环队列）实现

1 前言

队列是一种先进先出的线性表，简称为FIFO。它只允许在队尾插入成员，在队头删除成员，就像现实生活中排队上车一样。
队列的实现可以通过链表或数组完成，一般来说都推荐使用链表来实现队列，使用数组实现队列时每次有新的成员入队都需要对数组其它位置重新赋值，当队列相当大的时候这一过程非常耗时导致效率低下。该过程可以用如下图片表示：
在这里插入图片描述
上面就是一个典型的使用数组实现队列的数据结构，可以看到，每次在队尾插入一个新的成员，需要对整个数组进行赋值。
为了解决常规数组实现队列效率低下的问题，可以将数组修改为环形队列（循环队列）提高效率。

2 环形队列实现

2.1 环形队列结构体

#define MAX_QUEUE_LEN 5
typedef struct
{
    int head; /* 队列头 */
    int tail; /* 队列尾 */
    int memberCnt; /* 队列成员数 */
    char queueBuff[MAX_QUEUE_LEN]; /* 队列buffer */
} RingQueue_t;

我们这里定义队列头和队列尾指针，用于追踪队列头和队列尾，队列成员数记录当前队列是否存满，队列buffer记录队列成员。

2.2 初始化环形队列

/**
 * @brief 初始化环形队列
 * 
 * @param ringQueue 需要初始化的环形队列的地址
 */
void init_ring_queue(RingQueue_t *ringQueue)
{
    ringQueue->head = 0;
    ringQueue->tail = 0;
    ringQueue->memberCnt = 0;
}

初始化环形队列非常简单，就是将队列头、队列尾、队列成员数都设置为0，表示当前环形队列为空。

2.3 环形队列成员入队

/**
 * @brief 环形队列添加一个成员
 * 
 * @param ringQueue 需要添加一个成员的环形队列的地址
 * @param member 需要添加的成员
 */
void rq_add_member(RingQueue_t *ringQueue, char member)
{
    ringQueue->memberCnt++;
    if (ringQueue->memberCnt >= (MAX_QUEUE_LEN + 1))
    {
        ringQueue->memberCnt = MAX_QUEUE_LEN + 1;
    }

    if (ringQueue->memberCnt <= MAX_QUEUE_LEN)
    {
        ringQueue->head = 0;
        ringQueue->tail = MAX_QUEUE_LEN - 1;
        ringQueue->queueBuff[ringQueue->memberCnt - 1] = member;
    }
    else
    {
        ringQueue->tail++;
        if (ringQueue->tail >= MAX_QUEUE_LEN)
        {
            ringQueue->tail = 0;
        }
        ringQueue->queueBuff[ringQueue->tail] = member;

        ringQueue->head++;
        if (ringQueue->head >= MAX_QUEUE_LEN)
        {
            ringQueue->head = 0;
        }
    }
}

环形队列成员入队可以分为2个过程：
（1）队列由空到恰好满（无人出队）
（2）队列满（有人出队）

2.3.1 队列由空到恰好满（无人出队）

在这里插入图片描述
如果队列成员计数小于等于队列容量，则将队列头一直设置为0，队列尾一直设置为容量-1。

2.3.2 队列满（有人出队）

在这里插入图片描述
当队列恰好满了时，我们的队列头和队列尾指向了正确的对头、队尾位置。在队列满之后，新成员入队按照先入先出的原则只需要将队尾指针循环右移，然后将入队成员保存到该位置，同时将队头指针循环右移即可。

2.4 查看队列

/**
 * @brief 查看环形队列成员及数量
 * 
 * @param ringQueue 需要查看的环形队列的地址
 */
void view_ring_queue(RingQueue_t *ringQueue)
{
    int i, j;
    if (ringQueue->memberCnt <= MAX_QUEUE_LEN)
    {
        for (i = 0; i < ringQueue->memberCnt; i++)
        {
            printf("%02d->", ringQueue->queueBuff[i]);
        }
        printf("\r\n");
    }
    else
    {
        j = ringQueue->head;
        for (i = 0; i < MAX_QUEUE_LEN; i++)
        {
            printf("%02d->", ringQueue->queueBuff[j]);
            j++;
            if (j >= MAX_QUEUE_LEN)
            {
                j = 0;
            }
        }
        printf("\r\n");
    }
}

查看队列需要判断队列成员数，如果成员数小于等于容量，则按照成员数打印，如果成员数大于容量，则根据队头、队尾指示，打印队列所有成员。

3 测试

测试的程序如下：

int main(void)
{
    int i;
    RingQueue_t ringQueue;
    init_ring_queue(&ringQueue);
    for (i = 1; i < 10; i++)
    {
        rq_add_member(&ringQueue, i);
        view_ring_queue(&ringQueue);
    }
}