数据结构的队列（c语言版）

2024-05-03 07:15:14

一.队列的概念

1.队列的定义

队列是一种常见的数据结构，它遵循先进先出的原则。类似于现实生活中排队的场景，最先进入队列的元素首先被处理，而最后进入队列的元素则要等到前面的元素都被处理完后才能被处理。

在队列中，元素只能从一端插入，称为队尾，而只能从另一端删除，称为队头。新的元素被插入到队尾，而最早插入的元素位于队头。这样，当一个元素被处理或删除时，它前面的元素就会成为新的队头。

2.队列的应用

队列的应用：

1.任务调度：多个任务按照顺序排队等待执行。

2.广度优先搜索（BFS）：在图或树的遍历中，按层次遍历节点。

3.缓存管理：缓存中的数据按照访问顺序排列，最先进入的数据最先被替换。

4.算法设计：某些算法的设计与队列密切相关，如哈夫曼编码、循环队列等。

3.队列的优缺点

优点：

先进先出（FIFO）：队列保持元素的插入顺序，最先插入的元素最先被处理，符合很多实际问题的需求。
简单高效：队列的基本操作入队和出队的时间复杂度为O(1)，无论队列的大小如何，操作的时间复杂度都是固定的。
应用广泛：队列在很多算法和应用中有广泛的应用，如任务调度、广度优先搜索、缓存管理等。

缺点：

随机访问困难：队列只允许在队头删除元素，而在队尾插入元素，不支持随机访问。如果需要在其他位置插入或删除元素，操作效率较低。
队列大小限制：使用数组实现的队列在创建时需要指定最大容量，因此队列的大小有限。如果队列已满，则无法再插入新的元素。
存储空间浪费：如果队列的实际元素数量远小于最大容量，那么可能会造成存储空间的浪费，因为队列的容量是固定的。

二.队列的功能

队列常见的功能：

入队：将一个元素插入到队列的尾部，成为新的队尾。
出队：从队列的头部删除并返回一个元素，将队列的头部指针向后移动一位。
获取队头元素：返回队列的头部元素，但不删除它。
检查队列是否为空：检查队列中是否没有元素，即队列是否为空。
检查队列是否已满：检查队列是否已达到其最大容量，无法再插入新的元素。
清空队列：将队列中的所有元素删除，使其变为空队列。
获取队列中元素的数量：返回队列中元素的当前数量。
遍历队列：从队列的头部开始遍历到尾部，依次访问每个元素。

三.队列的实现

1.定义队列结构

Queue 是一个结构体类型，包含以下成员：

elements：类型为 int* 的指针，用于存储队列中的元素。通常情况下，可以通过动态内存分配来为该指针分配足够的内存空间，以存储队列的元素。
front：整型变量，表示队列头部的索引。它指向队列中的第一个元素。
rear：整型变量，表示队列尾部的索引。它指向队列中最后一个元素。
maxSize：整型变量，表示队列的最大容量。它用于限制队列中元素的数量，防止队列溢出。

typedef struct {
    int* elements;  // 存储元素的数组
    int front;      // 队列头部索引
    int rear;       // 队列尾部索引
    int maxSize;    // 队列的最大容量
} Queue;

2.初始化队列

initQueue(Queue* queue, int maxSize)：初始化队列。该函数接受一个指向 Queue 结构的指针以及队列的最大容量 maxSize。在函数内部，它为队列的元素数组分配内存空间，并将队列的头部索引 front 设置为 0，尾部索引 rear 设置为 -1，表示队列为空。

// 初始化队列
void initQueue(Queue* queue, int maxSize) {
    queue->elements = (int*)malloc(sizeof(int) * maxSize);
    queue->front = 0;
    queue->rear = -1;
    queue->maxSize = maxSize;
}

3.判断队列是否为空

isEmpty(Queue* queue)：检查队列是否为空。该函数接受一个指向 Queue 结构的指针，并根据队列的头部索引和尾部索引的关系来判断队列是否为空。如果队列为空，返回 1；否则，返回 0。

/ 检查队列是否为空
int isEmpty(Queue* queue) {
    return (queue->rear < queue->front);
}

4.判断队列是否已满

isFull(Queue* queue)：检查队列是否已满。该函数接受一个指向 Queue 结构的指针，并根据队列的头部索引和尾部索引的关系来判断队列是否已满。如果队列已满，返回 1；否则，返回 0。

// 检查队列是否已满
int isFull(Queue* queue) {
    return (queue->rear == queue->maxSize - 1);
}

5.入队

enqueue(Queue* queue, int element)：入队。该函数接受一个指向 Queue 结构的指针和要插入的元素 element。在函数内部，它首先检查队列是否已满，如果已满，则打印出队列已满的提示信息并返回；否则，将尾部索引 rear 增加 1，并将元素 element 存储在队列的尾部。

// 入队
void enqueue(Queue* queue, int element) {
    if (isFull(queue)) {
        printf("队列已满，无法入队。\n");
        return;
    }
    queue->rear++;
    queue->elements[queue->rear] = element;
}

6.出队

dequeue(Queue* queue)：出队。该函数接受一个指向 Queue 结构的指针，并返回队列头部的元素。在函数内部，它首先检查队列是否为空，如果为空，则打印出队列为空的提示信息并返回 -1；否则，将头部索引 front 增加 1，并返回队列头部的元素。

// 出队
int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队。\n");
        return -1;
    }
    int element = queue->elements[queue->front];
    queue->front++;
    return element;
}

7.获取队列头部信息

getFront(Queue* queue)：获取队列头部元素。该函数接受一个指向 Queue 结构的指针，并返回队列头部的元素，但不删除它。在函数内部，它首先检查队列是否为空，如果为空，则打印出队列为空的提示信息并返回 -1；否则，返回队列头部的元素。

// 获取队列头部元素
int getFront(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法获取头部元素。\n");
        return -1;
    }
    return queue->elements[queue->front];
}

8.释放内存

freeQueue(Queue* queue)：释放队列内存空间。该函数接受一个指向 Queue 结构的指针，并释放队列的元素数组所占用的内存空间。

// 释放队列内存空间
void freeQueue(Queue* queue) {
    free(queue->elements);
}

四.队列的源码呈现

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

// 定义队列结构
typedef struct {
    int* elements;  // 存储元素的数组
    int front;      // 队列头部索引
    int rear;       // 队列尾部索引
    int maxSize;    // 队列的最大容量
} Queue;

// 初始化队列
void initQueue(Queue* queue, int maxSize) {
    queue->elements = (int*)malloc(sizeof(int) * maxSize);
    queue->front = 0;
    queue->rear = -1;
    queue->maxSize = maxSize;
}

// 检查队列是否为空
int isEmpty(Queue* queue) {
    return (queue->rear < queue->front);
}

// 检查队列是否已满
int isFull(Queue* queue) {
    return (queue->rear == queue->maxSize - 1);
}

// 入队
void enqueue(Queue* queue, int element) {
    if (isFull(queue)) {
        printf("队列已满，无法入队。\n");
        return;
    }
    queue->rear++;
    queue->elements[queue->rear] = element;
}

// 出队
int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队。\n");
        return -1;
    }
    int element = queue->elements[queue->front];
    queue->front++;
    return element;
}

// 获取队列头部元素
int getFront(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法获取头部元素。\n");
        return -1;
    }
    return queue->elements[queue->front];
}

// 释放队列内存空间
void freeQueue(Queue* queue) {
    free(queue->elements);
}

int main() {
    Queue queue;
    int maxSize = 5;
    
    // 初始化队列
    initQueue(&queue, maxSize);
    
    // 入队
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    
    // 出队
    int element = dequeue(&queue);
    printf("出队元素：%d\n", element);
    
    // 获取队列头部元素
    int frontElement = getFront(&queue);
    printf("队列头部元素：%d\n", frontElement);
    
    // 释放队列内存空间
    freeQueue(&queue);
    
    return 0;
}

码农公寓