在C语言中，队列是一种先进先出（FIFO, First In First Out）的数据结构，它可以用来实现任务调度、缓冲区等功能。实现队列操作通常包括以下主要函数：

一、 队列的基本概念

队列是一种线性表，具有以下特点：

• 入队（Enqueue）：在队尾插入一个元素。
• 出队（Dequeue）：从队头删除一个元素。
• 队空（isEmpty）：判断队列是否为空。
• 队满（isFull）（适用于循环队列）：判断队列是否已满（对于固定大小的队列）。
• 获取队头元素（Peek/Front）：获取队头元素但不移除。

---

二、 实现队列的常用方法

队列的实现有两种常见方法：

• 基于数组：通过数组和一些指针或索引管理队列。
• 基于链表：通过链表动态管理队列，避免了数组需要固定大小的限制。

1. 基于数组实现队列

在数组实现的队列中，常用循环队列的方法，这样可以高效利用数组空间。

定义队列结构

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];  // 存储队列的数组
    int front;           // 队头指针
    int rear;            // 队尾指针
    int size;            // 当前队列元素个数
} Queue;

• MAX_SIZE：定义队列的最大容量，这里为100。
• data：这是一个数组，实际存储队列中的元素。
• front：指向队头元素的位置，出队时从这里取元素。
• rear：指向队尾的下一个位置，用于插入新元素。循环队列特性使得它可以“回绕”到数组的起始位置。
• size：记录队列中当前的元素个数，方便判断队列是否为空或已满。

初始化队列

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
    q->size = 0;
}

• 作用：初始化队列，将队列置为空。
• 为什么 front 和 rear 都设置为 0？ 因为这是一个空队列，两个指针都从数组的第一个位置开始。

判断队列是否为空

int isEmpty(Queue *q) {
    return q->size == 0;
}

• 逻辑：通过 size 判断队列是否为空。

判断队列是否已满

int isFull(Queue *q) {
    return q->size == MAX_SIZE;
}

• 逻辑：同样通过 size 判断是否已满。

入队操作（Enqueue）

int enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("队列已满，无法入队！\n");
        return 0;
    }
    q->data[q->rear] = value;           // 将元素存入队尾
    q->rear = (q->rear + 1) % MAX_SIZE; // 更新队尾指针（循环队列）
    q->size++;                          // 队列大小+1
    return 1;
}

• 步骤解析：
  • 检查队列是否已满。如果队列已满，打印提示信息并返回 0 。
  • 将 value 存入 rear 所指的位置，完成入队操作。
  • 更新 rear 指针，使其指向下一个位置。如果到达数组末尾，通过 (q->rear + 1) % MAX_SIZE 实现循环。
  • 增加队列的 size ，表示队列元素个数增加。
  • 返回 1，表示入队成功。
• 循环队列：

假设队列的数组大小为5：

队列初始状态：front=0, rear=0, size=0
入队1：data[rear=0]=1 → rear更新为1
入队2：data[rear=1]=2 → rear更新为2
如果rear达到数组末尾，会通过模运算重置为0。

出队操作（Dequeue）

int dequeue(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("队列为空，无法出队！\n");
        return 0;
    }
    *value = q->data[q->front];         // 获取队头元素
    q->front = (q->front + 1) % MAX_SIZE; // 更新队头指针（循环队列）
    q->size--;                          // 队列大小-1
    return 1;
}

• 步骤解析：
  • 检查队列是否为空。如果为空，打印提示信息并返回 0 。
  • 将 front 所指的元素存入 value（通过指针返回出队的值）。
  • 更新 front 指针，使其指向下一个位置。如果到达数组末尾，通过 (q->front + 1) % MAX_SIZE 实现循环。
  • 减少队列的 size ，表示队列元素个数减少。
  • 返回 1 ，表示出队成功。
• 循环队列：
  假设队列的数组大小为5：

初始状态：front=0, rear=3, data=[10, 20, 30]
出队1：front=0，取data[0]=10，front更新为1
出队2：front=1，取data[1]=20，front更新为2
如果front达到数组末尾，通过模运算回绕到0。

获取队头元素（Peek/Front）

int front(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("队列为空，无法获取队头！\n");
        return 0;
    }
    *value = q->data[q->front];
    return 1;
}

• 作用：获取队头的值，但不移除元素。
• 逻辑：
  • 检查队列是否为空。如果为空，打印提示信息并返回 0。
  • 通过 front 指针直接读取队头元素。
  • 返回 1，表示操作成功。

2. 基于链表实现队列

链表实现队列更加灵活，因为链表不需要预定义大小，可以动态增长。

定义链表节点和队列结构

typedef struct Node {
    int data;           // 数据域，用于存储队列元素
    struct Node *next;  // 指针域，指向下一个节点
} Node;

typedef struct {
    Node *front;  // 队头指针，指向队列的第一个节点
    Node *rear;   // 队尾指针，指向队列的最后一个节点
    int size;     // 队列元素个数
} Queue;

• Node：
  • data：用于存储队列中的一个元素。
  • next：指向下一个节点的指针，用来链接下一个队列元素。
• Queue：
  • front：指向队列的头节点（第一个节点）。
  • rear：指向队列的尾节点（最后一个节点）。
  • size：记录当前队列中的元素个数，方便操作。

初始化队列

void initQueue(Queue *q) {
    q->front = NULL;  // 队头指针初始化为NULL（空队列）
    q->rear = NULL;   // 队尾指针初始化为NULL（空队列）
    q->size = 0;      // 队列大小初始化为0
}

• 逻辑：
  • front 和 rear 都为 NULL，表示队列为空。
  • size 设置为 0。

判断队列是否为空

int isEmpty(Queue *q) {
    return q->size == 0;  // 如果队列大小为0，则为空队列
}

• 逻辑：通过 size 判断队列是否为空。

入队操作（Enqueue）

int enqueue(Queue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));  // 分配内存创建新节点
    if (newNode == NULL) {  // 检查内存分配是否成功
        printf("内存分配失败，无法入队！\n");
        return 0;
    }
    newNode->data = value;  // 将数据存入新节点
    newNode->next = NULL;   // 新节点的下一个指针为NULL（队列尾节点）

    if (isEmpty(q)) {       // 如果队列为空
        q->front = newNode; // 队头和队尾都指向新节点
    } else {
        q->rear->next = newNode; // 队尾节点的next指向新节点
    }
    q->rear = newNode;      // 更新队尾指针为新节点
    q->size++;              // 队列大小增加
    return 1;  // 入队成功
}

• 步骤解析：
  • 使用 malloc 分配一个新节点的内存。
  • 检查分配是否成功，如果失败，打印错误信息并返回。
  • 初始化新节点的值和指针（data 存储入队值，next 置为 NULL）。
  • 如果队列为空（isEmpty 返回 1），将 front 和 rear 都指向新节点，因为这是队列的第一个元素。
  • 如果队列非空，将当前队尾的 next 指向新节点，然后更新 rear 指针为新节点。
  • 增加 size，表示队列中元素的数量。

出队操作（Dequeue）

int dequeue(Queue *q, int *value) {
    if (isEmpty(q)) {  // 如果队列为空
        printf("队列为空，无法出队！\n");
        return 0;  // 出队失败
    }

    Node *temp = q->front;  // 保存当前队头节点
    *value = temp->data;    // 获取队头节点的数据
    q->front = q->front->next;  // 更新队头指针为下一个节点

    if (q->front == NULL) { // 如果出队后队列为空
        q->rear = NULL;     // 队尾指针也需要置为NULL
    }

    free(temp);  // 释放原队头节点的内存
    q->size--;   // 队列大小减少
    return 1;    // 出队成功
}

• 步骤解析：
  • 检查队列是否为空，如果为空，打印错误信息并返回。
  • 保存 front 指针所指向的节点（当前队头节点），用 temp 暂存。
  • 获取队头数据，并通过指针返回给调用者。
  • 更新 front 指向下一个节点。
  • 如果更新后 front 为 NULL（队列变空），需要将 rear 也置为 NULL。
  • 释放原队头节点的内存（free(temp)）。
  • 减少 size 。
  • 返回 1 ，表示出队成功。

获取队头元素（Peek/Front）

int front(Queue *q, int *value) {
    if (isEmpty(q)) { // 检查队列是否为空
        printf("队列为空，无法获取队头！\n");
        return 0;  // 操作失败
    }
    *value = q->front->data; // 获取队头数据
    return 1;  // 操作成功
}

• 逻辑：
  • 检查队列是否为空，如果为空，返回失败。
  • 如果队列非空，直接读取 front 所指向节点的数据。
  • 返回成功。