单链表循环队列educoder

单链表循环队列是一种基于单链表实现的队列数据结构，可以实现先进先出的数据存储和读取。它的特点是队列的首尾节点相连，形成一个环形结构，队列的头指针和尾指针都指向环形结构上的某个节点，可以循环利用已经出队的节点。

下面是一个简单的单链表循环队列的实现过程：

1. 定义队列的结构体，包括头指针、尾指针和队列长度等信息。

typedef struct queueNode {
    int data;
    struct queueNode *next;
}QueueNode;

typedef struct {
    QueueNode *head;
    QueueNode *tail;
    int size;
}Queue;

2. 初始化队列，将头指针和尾指针指向同一个节点，即创建一个空的链表。

void initQueue(Queue *queue) {
    queue->head = (QueueNode *)malloc(sizeof(QueueNode));
    queue->tail = queue->head;
    queue->head->next = NULL;
    queue->size = 0;
}

3. 判断队列是否为空。

bool isEmpty(Queue *queue) {
    return queue->size == 0;
}

4. 判断队列是否已满，由于单链表循环队列的长度是固定的，因此只需要判断队列长度是否达到上限即可。

bool isFull(Queue *queue) {
    return queue->size == MAX_QUEUE_SIZE;
}

5. 元素入队，将新元素插入到队列的尾部。

void enQueue(Queue *queue, int data) {
    if (isFull(queue)) {
        printf("Queue is full!\n");
        return;
    }
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    queue->tail->next = newNode;
    queue->tail = newNode;
    queue->size++;
}

6. 元素出队，将队列的头部元素删除并返回。

int deQueue(Queue *queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty!\n");
        return -1;
    }
    QueueNode *temp = queue->head->next;
    int data = temp->data;
    queue->head->next = temp->next;
    if (queue->tail == temp) {
        queue->tail = queue->head;
    }
    free(temp);
    queue->size--;
    return data;
}

7. 获取队列的长度。

int size(Queue *queue) {
    return queue->size;
}

8. 清空队列，将队列中的所有元素删除。

void clear(Queue *queue) {
    while (!isEmpty(queue)) {
        deQueue(queue);
    }
}

以上就是单链表循环队列的基本实现过程。需要注意的是，在每次出队操作时，需要判断队列中是否只有一个元素，若是，则需要将尾指针指向头指针。同时，由于单链表循环队列的长度是固定的，因此在插入新元素时需要判断队列是否已满。