王道考研数据结构--4.2循环队列

**循环队列**

循环队列是一种特殊的线性表，它的尾部与头部相连，形成一个环状结构。这种数据结构在计算机科学中非常重要，因为它可以高效地实现各种操作，如入队、出队、查找等。

**4.2.1 循环队列的定义**

循环队列是一种线性表，它的尾部与头部相连，形成一个环状结构。每个元素都有一个索引值，表示其在队列中的位置。

**4.2.2 循环队列的操作**

循环队列支持以下几种基本操作：

* **入队（Enqueue）**: 将新元素添加到队列尾部。
* **出队（Dequeue）**: 移除并返回队列头部元素。
* **查找（Search）**: 根据索引值找到指定元素。

**4.2.3 循环队列的实现**

循环队列可以使用数组或链表来实现。下面是使用数组实现的例子：

c#include <stdio.h>

#define MAX_SIZE10typedef struct {
 int data[MAX_SIZE];
 int front, rear;
} CircularQueue;

void init(CircularQueue *q) {
 q->front = q->rear = -1;
}

int is_empty(const CircularQueue *q) {
 return q->front == -1;
}

int is_full(const CircularQueue *q) {
 return (q->rear +1) % MAX_SIZE == q->front;
}

void enqueue(CircularQueue *q, int value) {
 if (is_full(q)) {
 printf("队列已满
");
 return;
 }
 if (is_empty(q)) {
 q->data[q->rear++] = value;
 q->front++;
 } else {
 q->rear = (q->rear +1) % MAX_SIZE;
 q->data[q->rear] = value;
 }
}

int dequeue(CircularQueue *q) {
 if (is_empty(q)) {
 printf("队列为空
");
 return -1;
 }
 int value = q->data[q->front];
 q->front = (q->front +1) % MAX_SIZE;
 return value;
}

int search(const CircularQueue *q, int index) {
 if (index < 0 || index >= MAX_SIZE) {
 printf("索引值越界
");
 return -1;
 }
 return q->data[index];
}