C 语言队列实现

介绍

队列（Queue）是一种常见的数据结构，遵循先进先出（FIFO, First In First Out）的原则。队列的操作主要包括入队（Enqueue）和出队（Dequeue）。入队是将元素添加到队列的末尾，而出队则是从队列的头部移除元素。

队列在计算机科学中有广泛的应用，例如任务调度、缓冲区管理、广度优先搜索（BFS）等。理解队列的实现原理对于掌握更复杂的数据结构和算法至关重要。

队列的基本操作

队列通常支持以下操作：

Enqueue: 将元素添加到队列的末尾。
Dequeue: 移除队列头部的元素。
Front: 获取队列头部的元素，但不移除它。
IsEmpty: 检查队列是否为空。
IsFull: 检查队列是否已满（仅适用于固定大小的队列）。

队列的实现

在C语言中，队列可以通过数组或链表来实现。下面我们将分别介绍这两种实现方式。

1. 使用数组实现队列

使用数组实现队列时，我们需要维护两个指针：front 和 rear。front 指向队列的头部，rear 指向队列的尾部。

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

#define MAX_SIZE 5

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

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isFull(Queue *q) {
    return q->rear == MAX_SIZE - 1;
}

bool isEmpty(Queue *q) {
    return q->front == -1;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
    } else {
        if (isEmpty(q)) {
            q->front = 0;
        }
        q->rear++;
        q->items[q->rear] = value;
        printf("Enqueued: %d\n", value);
    }
}

int dequeue(Queue *q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
        printf("Dequeued: %d\n", item);
        return item;
    }
}

int front(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    } else {
        return q->items[q->front];
    }
}

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

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

    dequeue(&q);
    dequeue(&q);

    printf("Front element is: %d\n", front(&q));

    return 0;
}

输入和输出示例：

Enqueued: 10
Enqueued: 20
Enqueued: 30
Dequeued: 10
Dequeued: 20
Front element is: 30

备注

使用数组实现队列时，需要注意队列的容量限制。如果队列已满，则无法继续入队操作。

2. 使用链表实现队列

链表实现的队列可以动态调整大小，避免了数组实现中的容量限制问题。

c
#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 initializeQueue(Queue *q) {
    q->front = q->rear = NULL;
}

bool 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 = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("Enqueued: %d\n", value);
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    } else {
        Node *temp = q->front;
        int item = temp->data;
        q->front = q->front->next;

        if (q->front == NULL) {
            q->rear = NULL;
        }

        free(temp);
        printf("Dequeued: %d\n", item);
        return item;
    }
}

int front(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    } else {
        return q->front->data;
    }
}

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

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

    dequeue(&q);
    dequeue(&q);

    printf("Front element is: %d\n", front(&q));

    return 0;
}

输入和输出示例：

Enqueued: 10
Enqueued: 20
Enqueued: 30
Dequeued: 10
Dequeued: 20
Front element is: 30

提示

链表实现的队列可以动态扩展，适合处理不确定数量的数据。

实际应用场景

队列在计算机科学中有许多实际应用，以下是一些常见的例子：

任务调度：操作系统使用队列来管理进程的执行顺序。
缓冲区管理：网络数据包的处理通常使用队列来缓冲数据。
广度优先搜索（BFS）：在图算法中，BFS使用队列来存储待访问的节点。

总结

队列是一种重要的数据结构，遵循先进先出的原则。通过数组或链表实现队列，可以有效地管理数据的顺序。理解队列的实现和应用场景，对于学习更复杂的数据结构和算法非常有帮助。

附加资源与练习

练习：尝试实现一个循环队列，避免数组实现中的空间浪费问题。
资源：阅读更多关于队列的应用，例如在操作系统中的任务调度。
挑战：使用队列实现一个简单的打印任务调度系统。

警告

在实现队列时，务必注意边界条件，例如队列为空或满的情况。

介绍​

队列的基本操作​

队列的实现​

1. 使用数组实现队列​

2. 使用链表实现队列​

实际应用场景​

总结​

附加资源与练习​

介绍