详解数据结构C语言实现之循环队列

什么是循环队列

循环队列是一种数据结构，它可以存储一组固定大小的元素，并且支持在队列尾部插入元素和在队列头部删除元素，当队列尾部没有空间时可以将队列头部空余的位置用来插入元素，实现循环的效果。循环队列的主要优点在于插入和删除元素的时间复杂度均为O(1)，而不是O(n)。

如何实现循环队列

循环队列可以使用数组来实现，需要定义队列的元素类型和队列的大小。队列还需要记录队首和队尾元素的下标，以及队列中元素的数量。以下是循环队列的基本结构。

#define MAX_SIZE 10

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队首元素的下标
    int rear;   // 队尾元素的下标
    int count;  // 队列中元素的数量
} CirQueue;

队列中元素的数量可以用rear和front之间的差值来表示，即count = (rear - front + MAX_SIZE) % MAX_SIZE。这样的计算可以避免数组越界的问题。

循环队列的插入和删除操作

插入操作

循环队列的插入操作有两个步骤：将元素存储到队列尾部，更新队尾元素的下标。

以下是循环队列的插入代码实现。

int InsertCirQueue(CirQueue *pCQ, int x) {
    if (pCQ->count >= MAX_SIZE) {   // 队列已满
        return 0;
    }
    pCQ->data[pCQ->rear] = x;
    pCQ->rear = (pCQ->rear + 1) % MAX_SIZE;
    pCQ->count++;
    return 1;
}

删除操作

循环队列的删除操作有两个步骤：获取队首元素，更新队首元素的下标。

以下是循环队列的删除代码实现。

int DeleteCirQueue(CirQueue *pCQ, int *px) {
    if (pCQ->count <= 0) {  // 队列为空
        return 0;
    }
    *px = pCQ->data[pCQ->front];
    pCQ->front = (pCQ->front + 1) % MAX_SIZE;
    pCQ->count--;
    return 1;
}

循环队列的完整实现

下面是循环队列的完整实现。包括初始化，判断队列是否为空或已满，输出队列元素等操作。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队首元素的下标
    int rear;   // 队尾元素的下标
    int count;  // 队列中元素的数量
} CirQueue;

void InitCirQueue(CirQueue *pCQ) {
    pCQ->front = 0;
    pCQ->rear = 0;
    pCQ->count = 0;
}

int IsEmptyCirQueue(CirQueue *pCQ) {
    return pCQ->count <= 0;
}

int IsFullCirQueue(CirQueue *pCQ) {
    return pCQ->count >= MAX_SIZE;
}

int InsertCirQueue(CirQueue *pCQ, int x) {
    if (IsFullCirQueue(pCQ)) {   // 队列已满
        return 0;
    }
    pCQ->data[pCQ->rear] = x;
    pCQ->rear = (pCQ->rear + 1) % MAX_SIZE;
    pCQ->count++;
    return 1;
}

int DeleteCirQueue(CirQueue *pCQ, int *px) {
    if (IsEmptyCirQueue(pCQ)) {  // 队列为空
        return 0;
    }
    *px = pCQ->data[pCQ->front];
    pCQ->front = (pCQ->front + 1) % MAX_SIZE;
    pCQ->count--;
    return 1;
}

void PrintCirQueue(CirQueue *pCQ) {
    int i, j;
    j = pCQ->count;
    for (i = pCQ->front; j > 0; i = (i+1) % MAX_SIZE) {
        printf("%d ", pCQ->data[i]);
        j--;
    }
    printf("\n");
}

void main() {
    CirQueue CQ;
    int x;

    InitCirQueue(&CQ);
    InsertCirQueue(&CQ, 1);
    InsertCirQueue(&CQ, 2);
    InsertCirQueue(&CQ, 3);
    printf("队列元素：");
    PrintCirQueue(&CQ);

    DeleteCirQueue(&CQ, &x);
    DeleteCirQueue(&CQ, &x);
    printf("队列元素：");
    PrintCirQueue(&CQ);
}

示例说明

示例1：在初始化一个循环队列后，插入3个元素，并打印队列中的元素。

CirQueue CQ;
InitCirQueue(&CQ);
InsertCirQueue(&CQ, 1);
InsertCirQueue(&CQ, 2);
InsertCirQueue(&CQ, 3);
printf("队列元素：");
PrintCirQueue(&CQ);  // 输出队列元素

示例2：在一个循环队列中删除2个元素，并打印队列中的元素。

CirQueue CQ;
int x;
InitCirQueue(&CQ);
InsertCirQueue(&CQ, 1);
InsertCirQueue(&CQ, 2);
InsertCirQueue(&CQ, 3);
DeleteCirQueue(&CQ, &x);
DeleteCirQueue(&CQ, &x);
printf("队列元素：");
PrintCirQueue(&CQ);  // 输出队列元素