使用C语言实现队列：基础与实践

队列（Queue）是一种常见的数据结构，遵循“先进先出”（FIFO，First In First Out）的原则。队列在许多计算机科学领域中有着广泛的应用，例如任务调度、缓冲区管理等。本文将以C语言为例，详细介绍如何实现一个简单的队列，包括两种主要实现方式：基于数组和基于链表的实现。

队列的基本操作

一个队列通常包括以下几种基本操作：

1. 初始化队列（Initialize）：创建一个空的队列。
2. 入队（Enqueue）：将一个元素添加到队列的末尾。
3. 出队（Dequeue）：移除并返回队列的头部元素。
4. 检查队列是否为空（IsEmpty）：判断队列是否为空。
5. 获取队列头部元素（Peek）：获取但不移除队列的头部元素。

基于数组实现队列

优点和缺点

基于数组的队列实现简单且直观，但需要预先定义数组的大小，可能导致内存浪费或溢出问题。

实现代码

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

#define MAX_SIZE 100

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

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

// 检查队列是否为空
bool isEmpty(Queue *q) {
    return q->front == q->rear;
}

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

// 入队
bool enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("队列已满，无法入队！\n");
        return false;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}

// 出队
bool dequeue(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("队列为空，无法出队！\n");
        return false;
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return true;
}

// 获取队列头部元素
bool peek(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("队列为空，无法获取头部元素！\n");
        return false;
    }
    *value = q->data[q->front];
    return true;
}

// 打印队列
void printQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("队列为空！\n");
        return;
    }
    printf("队列元素：");
    int i = q->front;
    while (i != q->rear) {
        printf("%d ", q->data[i]);
        i = (i + 1) % MAX_SIZE;
    }
    printf("\n");
}

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

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

    printQueue(&q);

    int value;
    dequeue(&q, &value);
    printf("出队元素：%d\n", value);

    printQueue(&q);

    return 0;
}

基于链表实现队列

优点和缺点

基于链表的队列不需要预定义大小，内存使用更加灵活，适用于元素数量动态变化的场景。但实现相对复杂，需要额外的内存管理。

实现代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.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;
}

// 检查队列是否为空
bool isEmpty(Queue *q) {
    return q->front == NULL;
}

// 入队
void enqueue(Queue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败！\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    if (isEmpty(q)) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队
bool dequeue(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("队列为空，无法出队！\n");
        return false;
    }
    Node *temp = q->front;
    *value = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return true;
}

// 获取队列头部元素
bool peek(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("队列为空，无法获取头部元素！\n");
        return false;
    }
    *value = q->front->data;
    return true;
}

// 打印队列
void printQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("队列为空！\n");
        return;
    }
    printf("队列元素：");
    Node *current = q->front;
    while (current) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

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

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

    printQueue(&q);

    int value;
    dequeue(&q, &value);
    printf("出队元素：%d\n", value);

    printQueue(&q);

    return 0;
}

总结

1. 基于数组的实现适合队列大小固定的场景，逻辑简单，但需要考虑数组的容量问题。
2. 基于链表的实现灵活性更高，适合队列大小动态变化的场景，但实现复杂度略高。

根据实际应用场景选择合适的队列实现方式，可以让程序更加高效和可靠。希望本文能帮助大家更好地理解和实现队列！