2、 循环队列的结构体定义及基本操作(牺牲一个存储空间)（初始化、判空、入队、出队）。用c语言

在C语言中，我们可以使用动态内存分配创建一个循环队列的数据结构。这里是一个简单的实现，使用了一个数组作为存储容器，同时牺牲了数组的一个元素用于指向当前队头和队尾的位置：

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

#define MAX_SIZE 100 // 队列的最大容量

typedef struct {
    int *queue;   // 存储数据的数组
    int front;    // 队头指针
    int rear;     // 队尾指针
} Queue;

// 初始化队列
Queue* initQueue() {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    if (!q) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    q->queue = (int*)malloc(MAX_SIZE * sizeof(int)); // 分配数组空间
    if (!q->queue) {
        free(q);
        return NULL;
    }
    q->front = q->rear = -1; // 初始状态为空
    return q;
}

// 判空和判满
bool queueEmpty(Queue* q) {
    return q->front == q->rear;
}

bool queueFull(Queue* q) {
    return (q->rear + 1) % MAX_SIZE == q->front; // 使用模运算模拟循环
}

// 入队操作
void enqueue(Queue* q, int value) {
    if (queueFull(q)) {
        printf("Queue is full.\n");
        return;
    }
    if (q->front == -1) { // 如果队列为空，设置队头
        q->front = 0;
    } else {
        q->rear = (q->rear + 1) % MAX_SIZE; // 循环更新队尾
    }
    q->queue[q->rear] = value;
}

// 出队操作
int dequeue(Queue* q) {
    if (queueEmpty(q)) {
        printf("Queue is empty.\n");
        return -1; // 返回特殊值表示错误
    }
    int value = q->queue[q->front];
    if (q->front == q->rear) { // 队列仅剩最后一个元素，需要移动队头
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }
    return value;
}

// 示例
int main() {
    Queue* q = initQueue();
    if (q != NULL) {
        enqueue(q, 1);
        enqueue(q, 2);
        printf("%d ", dequeue(q)); // 输出 1
        printf("%d\n", dequeue(q)); // 输出 2
        free(q->queue);
        free(q);
    }
    return 0;
}