环形队列

环形队列是一种数据结构，它在实现上类似于普通的队列，但是它可以更加高效地利用存储空间。在环形队列中，队列的尾部和头部是相连的，形成一个环。当队列的尾部到达数组的末尾时，它会回到数组的开头，从而实现循环。

环形队列通常用数组来实现，其中头指针front指向队列的第一个元素，尾指针rear指向队列最后一个元素的下一个位置。当队列为空时，头指针和尾指针相等；当队列满时，尾指针和头指针相差一个位置。

环形队列的优点在于它可以更加高效地利用存储空间，因为在普通队列中，即使队列的头部已经出队，队列的头指针还是指向出队元素的位置，导致浪费存储空间。而在环形队列中，头指针始终指向队列的第一个元素，不会浪费存储空间。

环形队列的操作和普通队列类似，包括入队、出队、判断队列是否为空、判断队列是否已满等操作。需要注意的是，在环形队列中，入队时需要先判断队列是否已满，出队时需要先判断队列是否为空。

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

#define MAXSIZE 5  // 队列最大容量

typedef struct Queue {
    int *data;  // 数据数组
    int front;  // 队首指针
    int rear;   // 队尾指针
    int size;   // 当前队列大小
} Queue;

// 初始化队列
Queue *initQueue() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * MAXSIZE);
    q->front = 0;
    q->rear = 0;
    q->size = 0;
    return q;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->size == 0;
}

// 判断队列是否已满
int isFull(Queue *q) {
    return q->size == MAXSIZE;
}

// 入队
void enqueue(Queue *q, int val) {
    if (isFull(q)) {
        printf("Queue is full.\n");
        return;
    }
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % MAXSIZE;
    q->size++;
}

// 出队
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    int val = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    q->size--;
    return val;
}

// 打印队列
void printQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue: ");
    for (int i = q->front; i != q->rear; i = (i + 1) % MAXSIZE) {
        printf("%d ", q->data[i]);
    }
    printf("\n");
}

// 测试
int main() {
    Queue *q = initQueue();
    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    printQueue(q);  // Queue: 1 2 3
    dequeue(q);
    printQueue(q);  // Queue: 2 3
    enqueue(q, 4);
    enqueue(q, 5);
    enqueue(q, 6);  // Queue is full.
    dequeue(q);
    dequeue(q);
    dequeue(q);
    dequeue(q);
    printQueue(q);  // Queue is empty.
    return 0;
}

在这个示例中，我们使用了一个结构体来表示队列，包括一个指向数据数组的指针，一个头指针，一个尾指针和一个表示当前队列大小的变量。在初始化队列时，我们分配了一个数组和一个队列结构体，并将头指针、尾指针和大小都初始化为0。在入队操作中，我们将元素添加到数组中，并将尾指针向后移动一个位置。需要注意的是，我们使用了取模操作来实现循环，因为当尾指针到达数组末尾时，它需要回到数组开头。在出队操作中，