C语言实现队列：从基础到实践

简介

队列（Queue）是一种特殊的线性数据结构，它遵循先进先出（FIFO，First In First Out）的原则。在许多编程场景中，队列都发挥着重要作用，比如任务调度、广度优先搜索（BFS）等。本文将深入探讨如何使用C语言实现队列，并分享相关的使用方法、常见实践以及最佳实践。

目录

1. 队列的基础概念
   • 定义
   • 操作
2. C语言实现队列的方法
   • 数组实现
   • 链表实现
3. 常见实践
   • 任务调度模拟
   • 广度优先搜索
4. 最佳实践
   • 内存管理
   • 错误处理
5. 小结
6. 参考资料

队列的基础概念

定义

队列是一种有序的数据集合，新元素从队列的“尾部”添加，已存在的元素从队列的“头部”移除。这就像日常生活中的排队，先到的人先接受服务。

操作

• 入队（Enqueue）：将一个元素添加到队列的尾部。
• 出队（Dequeue）：从队列的头部移除一个元素，并返回该元素。
• 获取队头元素（Front）：返回队列头部的元素，但不移除它。
• 获取队尾元素（Rear）：返回队列尾部的元素，但不移除它。
• 判断队列是否为空（Is Empty）：检查队列中是否没有元素。
• 判断队列是否已满（Is Full）：对于基于数组实现的队列，需要检查队列是否已达到最大容量。

C语言实现队列的方法

数组实现

使用数组实现队列时，我们需要定义一个数组来存储元素，以及两个变量front和rear分别表示队列的头部和尾部。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == -1;
}

// 判断队列是否已满
int isFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 入队操作
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("队列已满\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->data[q->rear] = value;
}

// 出队操作
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("队列已空\n");
        return -1;
    }
    int value = q->data[q->front];
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }
    return value;
}

// 获取队头元素
int front(Queue *q) {
    if (isEmpty(q)) {
        printf("队列已空\n");
        return -1;
    }
    return q->data[q->front];
}

// 获取队尾元素
int rear(Queue *q) {
    if (isEmpty(q)) {
        printf("队列已空\n");
        return -1;
    }
    return q->data[q->rear];
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("队头元素: %d\n", front(&q));
    printf("队尾元素: %d\n", rear(&q));

    printf("出队元素: %d\n", dequeue(&q));
    printf("队头元素: %d\n", front(&q));

    return 0;
}

链表实现

链表实现的队列更加灵活，因为它不需要预先分配固定大小的内存。每个节点包含数据和指向下一个节点的指针。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
    Node *rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = NULL;
    q->rear = NULL;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == NULL;
}

// 入队操作
void enqueue(Queue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(q)) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队操作
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("队列已空\n");
        return -1;
    }
    Node *temp = q->front;
    int value = temp->data;
    q->front = q->front->next;
    free(temp);
    if (q->front == NULL) {
        q->rear = NULL;
    }
    return value;
}

// 获取队头元素
int front(Queue *q) {
    if (isEmpty(q)) {
        printf("队列已空\n");
        return -1;
    }
    return q->front->data;
}

// 获取队尾元素
int rear(Queue *q) {
    if (isEmpty(q)) {
        printf("队列已空\n");
        return -1;
    }
    return q->rear->data;
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("队头元素: %d\n", front(&q));
    printf("队尾元素: %d\n", rear(&q));

    printf("出队元素: %d\n", dequeue(&q));
    printf("队头元素: %d\n", front(&q));

    return 0;
}

常见实践

任务调度模拟

队列在任务调度中非常有用。例如，操作系统中的任务调度器可以使用队列来管理等待执行的任务。

#include <stdio.h>
#include <stdlib.h>

typedef struct Task {
    int taskId;
    struct Task *next;
} Task;

typedef struct {
    Task *front;
    Task *rear;
} TaskQueue;

// 初始化任务队列
void initTaskQueue(TaskQueue *q) {
    q->front = NULL;
    q->rear = NULL;
}

// 判断任务队列是否为空
int isTaskQueueEmpty(TaskQueue *q) {
    return q->front == NULL;
}

// 添加任务到队列
void enqueueTask(TaskQueue *q, int taskId) {
    Task *newTask = (Task *)malloc(sizeof(Task));
    newTask->taskId = taskId;
    newTask->next = NULL;

    if (isTaskQueueEmpty(q)) {
        q->front = newTask;
        q->rear = newTask;
    } else {
        q->rear->next = newTask;
        q->rear = newTask;
    }
}

// 从队列中取出任务
int dequeueTask(TaskQueue *q) {
    if (isTaskQueueEmpty(q)) {
        printf("任务队列为空\n");
        return -1;
    }
    Task *temp = q->front;
    int taskId = temp->taskId;
    q->front = q->front->next;
    free(temp);
    if (q->front == NULL) {
        q->rear = NULL;
    }
    return taskId;
}

int main() {
    TaskQueue taskQueue;
    initTaskQueue(&taskQueue);

    enqueueTask(&taskQueue, 1);
    enqueueTask(&taskQueue, 2);
    enqueueTask(&taskQueue, 3);

    printf("执行任务: %d\n", dequeueTask(&taskQueue));
    printf("执行任务: %d\n", dequeueTask(&taskQueue));

    return 0;
}

广度优先搜索

在图的广度优先搜索算法中，队列用于存储待访问的节点。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

typedef struct {
    int vertices[MAX_VERTICES];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == -1;
}

// 入队操作
void enqueue(Queue *q, int value) {
    if (q->rear == MAX_VERTICES - 1) {
        printf("队列已满\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear++;
    q->vertices[q->rear] = value;
}

// 出队操作
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("队列已空\n");
        return -1;
    }
    int value = q->vertices[q->front];
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front++;
    }
    return value;
}

// 邻接矩阵表示图
int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];

// 广度优先搜索
void bfs(int start) {
    Queue q;
    initQueue(&q);

    visited[start] = 1;
    enqueue(&q, start);

    while (!isEmpty(&q)) {
        int current = dequeue(&q);
        printf("%d ", current);

        for (int i = 0; i < MAX_VERTICES; i++) {
            if (graph[current][i] &&!visited[i]) {
                visited[i] = 1;
                enqueue(&q, i);
            }
        }
    }
}

int main() {
    // 初始化图和访问数组
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = 0;
        }
        visited[i] = 0;
    }

    // 添加边
    graph[0][1] = 1;
    graph[1][0] = 1;
    graph[0][2] = 1;
    graph[2][0] = 1;
    graph[1][2] = 1;
    graph[2][1] = 1;

    bfs(0);

    return 0;
}

最佳实践

内存管理

在使用链表实现队列时，要注意内存的分配和释放。每次入队时分配新的节点，每次出队时释放相应的节点，避免内存泄漏。

错误处理

在实现队列的操作时，要进行充分的错误处理。例如，在入队前检查队列是否已满，在出队前检查队列是否为空，以避免程序崩溃。

小结

本文详细介绍了队列的基础概念、使用C语言实现队列的两种常见方法（数组和链表），并通过实际案例展示了队列在任务调度和广度优先搜索中的应用。同时，还分享了一些在实现队列时的最佳实践，如内存管理和错误处理。希望这些内容能帮助读者更好地理解和使用C语言实现队列。

参考资料

• 《C Primer Plus》
• 《数据结构与算法分析（C语言描述）》
• GeeksforGeeks
• LeetCode