DA1-循环队列¶

代码实现¶

C
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100  // 队列的最大容量

/**
 * 循环队列的顺序存储结构定义
 */
typedef struct {
    int data[MAXSIZE];  // 存储队列元素的数组
    int front;          // 队头指针（指向队头元素）
    int rear;           // 队尾指针（指向下一个入队位置）
} Queue;

/**
 * 初始化队列
 * @param q 指向队列的指针
 */
void init(Queue* q) {
    q->front = 0;   // 队头指针初始化为0
    q->rear = 0;    // 队尾指针初始化为0
}

/**
 * 判断队列是否为空
 * @param q 队列（传值调用）
 * @return 空队列返回true，非空返回false
 */
bool IsEmpty(Queue q) {
    return q.front == q.rear;
}

/**
 * 判断队列是否已满
 * @param q 队列（传值调用）
 * @return 队满返回true，未满返回false
 */
bool IsFull(Queue q) {
    return (q.rear + 1) % MAXSIZE == q.front;
}

/**
 * 入队操作
 * @param q 指向队列的指针
 * @param x 要入队的元素
 * @return 入队成功返回true，队满返回false
 */
bool enqueue(Queue* q, int x) {
    // 检查队列是否已满
    if ((q->rear + 1) % MAXSIZE == q->front) {
        printf("队列已满，无法入队\n");
        return false;  // 队满，入队失败
    }

    // 在队尾插入元素
    q->data[q->rear] = x;

    // 队尾指针循环移动
    q->rear = (q->rear + 1) % MAXSIZE;

    return true;  // 入队成功
}

/**
 * 出队操作
 * @param q 指向队列的指针
 * @param x 指向存储出队元素的指针
 * @return 出队成功返回true，空队列返回false
 */
bool dequeue(Queue* q, int* x) {
    // 检查队列是否为空
    if (q->front == q->rear) {
        printf("队列为空，无法出队\n");
        return false;  // 空队列，出队失败
    }

    // 获取队头元素
    *x = q->data[q->front];

    // 队头指针循环移动
    q->front = (q->front + 1) % MAXSIZE;

    return true;  // 出队成功
}

/**
 * 获取队列中元素个数
 * @param q 队列
 * @return 队列中元素个数
 */
int getSize(Queue q) {
    return (q.rear - q.front + MAXSIZE) % MAXSIZE;
}

/**
 * 获取队头元素（不删除）
 * @param q 队列
 * @param x 指向存储队头元素的指针
 * @return 获取成功返回true，空队列返回false
 */
bool getFront(Queue q, int* x) {
    if (q.front == q.rear) {
        return false;  // 空队列
    }
    *x = q.data[q.front];
    return true;
}

/**
 * 清空队列
 * @param q 指向队列的指针
 */
void clear(Queue* q) {
    q->front = q->rear = 0;
}

循环队列结构图解¶

循环队列特点：¶

Text Only

普通队列：队满时无法继续插入
┌─────────────────────────┐
│  1  │  2  │  3  │     │     │
├─────────────────────────┤
   ↑              ↑
 front          rear

循环队列：利用数组的循环特性
┌─────────────────────────┐
│  3  │     │     │  1  │  2  │
├─────────────────────────┤
         ↑        ↑
       rear     front

队空和队满判断：¶

Text Only
1 2 3 4 5 6	`队空条件：front == rear 队满条件：(rear + 1) % MAXSIZE == front 为什么牺牲一个存储单元？ - 区分队空和队满状态 - 队满时rear指向的位置不存储数据`

队列操作流程图解¶

初始状态：¶

Text Only
1 2 3	`队列：[ ][ ][ ][ ][ ][ ] ↑ front,rear=0`

入队操作：¶

Text Only

enqueue(1)：
队列：[1][ ][ ][ ][ ][ ]
       ↑  ↑
    front rear=1

enqueue(2)：
队列：[1][2][ ][ ][ ][ ]
       ↑   ↑
    front  rear=2

enqueue(3)：
队列：[1][2][3][ ][ ][ ]
       ↑    ↑
    front   rear=3

出队操作：¶

Text Only
1 2 3 4 5 6 7 8 9	`dequeue(&x)：x=1 队列：[1][2][3][ ][ ][ ] ↑ ↑ front rear=3 dequeue(&x)：x=2 队列：[ ][2][3][ ][ ][ ] ↑ ↑ front rear=3`

循环特性：¶

Text Only
1 2 3 4 5 6 7	`继续入队直到接近队满：队列：[ ][ ][3][4][5][6] ↑ ↑ front rear=0 此时：(rear+1)%MAXSIZE = (0+1)%6 = 1 == front 队列已满，无法继续入队`

复杂度分析¶

时间复杂度：O(1)¶

所有操作：初始化、判空、判满、入队、出队
原因：都是直接通过数组下标访问或指针移动
总体时间复杂度：O(1)

空间复杂度：O(n)¶

队列空间：数组data[MAXSIZE]占用O(MAXSIZE)空间
辅助变量：front、rear等常数个变量
总体空间复杂度：O(n)

算法优化版本¶

C
/**
 * 优化版本：使用计数器避免牺牲存储单元
 */
typedef struct {
    int data[MAXSIZE];
    int front;
    int rear;
    int count;  // 队列中元素个数
} OptimizedQueue;

void init_optimized(OptimizedQueue* q) {
    q->front = 0;
    q->rear = 0;
    q->count = 0;
}

bool enqueue_optimized(OptimizedQueue* q, int x) {
    if (q->count == MAXSIZE) {
        return false;  // 队满
    }

    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;
    q->count++;
    return true;
}

bool dequeue_optimized(OptimizedQueue* q, int* x) {
    if (q->count == 0) {
        return false;  // 队空
    }

    *x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    q->count--;
    return true;
}

bool IsEmpty_optimized(OptimizedQueue q) {
    return q.count == 0;
}

bool IsFull_optimized(OptimizedQueue q) {
    return q.count == MAXSIZE;
}

int getSize_optimized(OptimizedQueue q) {
    return q.count;
}

安全版本¶

C
/**
 * 安全版本：添加完整的错误处理
 */
bool enqueue_safe(Queue* q, int x) {
    // 参数检查
    if (q == NULL) {
        printf("队列指针为空\n");
        return false;
    }

    // 队满检查
    if ((q->rear + 1) % MAXSIZE == q->front) {
        printf("队列已满\n");
        return false;
    }

    // 入队操作
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;

    return true;
}

bool dequeue_safe(Queue* q, int* x) {
    // 参数检查
    if (q == NULL || x == NULL) {
        printf("参数错误\n");
        return false;
    }

    // 队空检查
    if (q->front == q->rear) {
        printf("队列为空\n");
        return false;
    }

    // 出队操作
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;

    return true;
}

循环队列与普通队列对比¶

特性	普通队列	循环队列
存储利用率	低（假溢出）	高（充分利用）
实现复杂度	简单	中等
空间浪费	可能很大	固定浪费1个单元
适用场景	简单应用	高效应用

测试用例¶

C
/**
 * 测试函数
 */
void test_queue_operations() {
    Queue q;
    init(&q);

    printf("队列初始化完成\n");
    printf("队列是否为空：%s\n", IsEmpty(q) ? "是" : "否");

    // 测试入队
    for (int i = 1; i <= 5; i++) {
        if (enqueue(&q, i)) {
            printf("入队：%d\n", i);
        } else {
            printf("入队失败：%d\n", i);
        }
    }

    printf("队列大小：%d\n", getSize(q));

    // 测试出队
    int x;
    while (dequeue(&q, &x)) {
        printf("出队：%d\n", x);
    }

    printf("队列是否为空：%s\n", IsEmpty(q) ? "是" : "否");
}

算法特点¶

核心思想：利用数组下标的循环特性，实现队列的循环存储，避免假溢出现象。

关键技术： 1. 循环下标：(index + 1) % MAXSIZE 2. 状态判断：通过front和rear的关系判断队空队满 3. 空间优化：充分利用数组存储空间

优势： - 高效操作：所有基本操作都是O(1)时间复杂度 - 空间利用：避免假溢出，提高存储效率 - 实现简单：逻辑清晰，易于理解和维护

应用场景： - 操作系统任务调度 - 网络数据包缓冲 - 广度优先搜索算法 - 生产者消费者问题 - 缓冲区管理

循环队列是队列数据结构的经典实现，在实际应用中具有很高的实用价值。