C语言数据结构之队列怎么定义与实现

1. 队列的基本概念

队列（Queue）是一种先进先出（FIFO, First In First Out）的线性数据结构。它只允许在表的一端进行插入操作，而在另一端进行删除操作。队列的这种特性使得它在很多场景中非常有用，比如任务调度、缓冲区管理等。

1.1 队列的特点

• 先进先出：最先进入队列的元素最先被移除。
• 操作受限：只能在队尾插入元素，在队头删除元素。
• 动态性：队列的大小可以动态变化，通常不需要预先定义大小。

1.2 队列的基本操作

• 入队（Enqueue）：在队列的尾部插入一个元素。
• 出队（Dequeue）：从队列的头部删除一个元素。
• 获取队头元素（Front）：获取队列头部的元素，但不删除它。
• 获取队尾元素（Rear）：获取队列尾部的元素，但不删除它。
• 判断队列是否为空（IsEmpty）：判断队列是否为空。
• 获取队列的大小（Size）：获取队列中元素的个数。

2. 队列的实现方式

队列可以通过多种方式实现，常见的有数组实现和链表实现。下面我们将分别介绍这两种实现方式。

2.1 数组实现队列

数组实现队列的方式相对简单，但存在一个潜在的问题：当队列的头部元素被删除后，数组的前部空间将无法被利用，导致空间浪费。为了解决这个问题，通常使用循环队列的方式来实现。

2.1.1 循环队列的定义

循环队列是一种特殊的队列，它通过将数组的首尾相连，形成一个环形结构。这样，当队列的头部元素被删除后，数组的前部空间可以被重新利用。

2.1.2 循环队列的实现

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

#define MAX_SIZE 100

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

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

// 判断队列是否为空
bool isEmpty(CircularQueue *q) {
    return q->front == q->rear;
}

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

// 入队操作
bool enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return false;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}

// 出队操作
bool dequeue(CircularQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return true;
}

// 获取队头元素
bool front(CircularQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->data[q->front];
    return true;
}

// 获取队尾元素
bool rear(CircularQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->data[(q->rear - 1 + MAX_SIZE) % MAX_SIZE];
    return true;
}

// 获取队列的大小
int size(CircularQueue *q) {
    return (q->rear - q->front + MAX_SIZE) % MAX_SIZE;
}

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

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

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

    rear(&q, &value);
    printf("Rear element: %d\n", value);

    printf("Queue size: %d\n", size(&q));

    dequeue(&q, &value);
    printf("Dequeued element: %d\n", value);

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

    printf("Queue size: %d\n", size(&q));

    return 0;
}

2.2 链表实现队列

链表实现队列的方式更加灵活，不需要预先定义队列的大小，且不会出现空间浪费的问题。

2.2.1 链表队列的定义

链表队列通过链表节点来存储数据，每个节点包含数据和指向下一个节点的指针。队列的头部指向链表的第一个节点，尾部指向链表的最后一个节点。

2.2.2 链表队列的实现

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

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

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

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

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

// 入队操作
void enqueue(LinkedQueue *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;
    }
}

// 出队操作
bool dequeue(LinkedQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\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 front(LinkedQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->front->data;
    return true;
}

// 获取队尾元素
bool rear(LinkedQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->rear->data;
    return true;
}

// 获取队列的大小
int size(LinkedQueue *q) {
    int count = 0;
    Node *current = q->front;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

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

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

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

    rear(&q, &value);
    printf("Rear element: %d\n", value);

    printf("Queue size: %d\n", size(&q));

    dequeue(&q, &value);
    printf("Dequeued element: %d\n", value);

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

    printf("Queue size: %d\n", size(&q));

    return 0;
}

3. 队列的应用场景

队列在计算机科学中有广泛的应用，以下是一些常见的应用场景：

3.1 任务调度

在操作系统中，任务调度通常使用队列来实现。任务按照到达的顺序进入队列，调度器从队列的头部取出任务进行执行。

3.2 缓冲区管理

在网络通信中，数据包的传输通常使用队列作为缓冲区。数据包按照到达的顺序进入队列，接收端从队列的头部取出数据包进行处理。

3.3 广度优先搜索（BFS）

在图论中，广度优先搜索算法使用队列来存储待访问的节点。算法从起始节点开始，依次访问其邻接节点，并将这些节点加入队列中，直到队列为空。

3.4 打印队列

在打印机管理中，打印任务通常使用队列来管理。打印任务按照提交的顺序进入队列，打印机从队列的头部取出任务进行打印。

4. 总结

队列是一种非常重要的数据结构，具有先进先出的特性。它可以通过数组或链表来实现，每种实现方式都有其优缺点。数组实现的队列简单高效，但存在空间浪费的问题；链表实现的队列灵活且不会浪费空间，但需要额外的内存来存储指针。

在实际应用中，队列被广泛用于任务调度、缓冲区管理、广度优先搜索等场景。掌握队列的定义与实现，对于理解和应用这些场景至关重要。

通过本文的学习，你应该已经掌握了如何在C语言中定义和实现队列，并了解了队列的基本操作和应用场景。希望这些知识能够帮助你在编程实践中更好地使用队列这一数据结构。