循环队列 (Circular Queue)
基于定长数组实现的环形缓冲区，头尾指针在数组内循环移动。enqueue/dequeue 均为 O(1)。
结构定义
typedef struct {
int *data;
size_t front; /* 队头下标 */
size_t rear; /* 队尾下标（指向下一个空位） */
size_t capacity; /* 数组容量 */
size_t size; /* 当前元素数（也可通过 (rear - front + cap) % cap 推导） */
} CQueue;函数签名
| 函数 | 复杂度 | 说明 |
|---|---|---|
void cq_init(CQueue *q, size_t cap) | O(1) | 初始化，分配 cap 大小数组 |
int cq_enqueue(CQueue *q, int val) | O(1) | 入队，满时返回 -1 |
int cq_dequeue(CQueue *q) | O(1) | 出队，空时返回 -1（或未定义行为） |
int cq_front(CQueue *q) | O(1) | 查看队头 |
int cq_empty(CQueue *q) | O(1) | 判空 |
int cq_full(CQueue *q) | O(1) | 判满 |
void cq_free(CQueue *q) | O(1) | 释放 |
核心实现
int cq_enqueue(CQueue *q, int val) {
if (cq_full(q)) return -1;
q->data[q->rear] = val;
q->rear = (q->rear + 1) % q->capacity;
q->size++;
return 0;
}
int cq_dequeue(CQueue *q) {
if (cq_empty(q)) return -1;
int val = q->data[q->front];
q->front = (q->front + 1) % q->capacity;
q->size--;
return val;
}判空/判满策略
| 策略 | 判空 | 判满 |
|---|---|---|
| 牺牲一个槽位 | front == rear | (rear + 1) % cap == front |
| 额外 size 字段 | size == 0 | size == capacity |
| 标志位 | empty == 1 | empty == 0 && front == rear |
推荐使用 size 字段：逻辑清晰，额外存储可忽略。
典型应用
- 消息队列（生产者-消费者模型）
- BFS 广度优先搜索的待访问节点队列
- 滑动窗口（TCP 接收缓冲区）
- 键盘缓冲区