十、数据结构——链式队列

数据结构中的链式队列

目录

一、链式队列的定义
二、链式队列的实现
三、链式队列的基本操作

• ①初始化
  ②判空
  ③入队
  ④出队
  ⑤获取长度
  ⑥打印

四、循环队列的应用
五、总结
六、全部代码
七、结果

在数据结构中，队列（Queue）是一种常见的线性数据结构，遵循先进先出（First In First Out，FIFO）的原则。链式队列是队列的一种实现方式，它使用链表来存储队列中的元素。本篇博客将详细介绍链式队列的定义、实现和基本操作，并附带有带有注释的示例代码。

一、链式队列的定义

链式队列是通过链表实现的一种队列，它将队列的元素通过指针连接起来。链式队列不需要预先分配固定大小的存储空间，因此可以动态增长，更加灵活。

二、链式队列的实现

// 定义节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义链式队列
typedef struct {
    Node* front;
    Node* rear;
} LinkedQueue;
1
2
3
4
5
6
7
8
9
10
11

三、链式队列的基本操作

①初始化链式队列

// 初始化链式队列
void initLinkedQueue(LinkedQueue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}
1
2
3
4
5

②判断队列是否为空

// 判断队列是否为空
int isEmpty(LinkedQueue* queue) {
    return queue->front == NULL;
}
1
2
3
4

③入队操作

// 入队操作
void enqueue(LinkedQueue* queue, TypeData value) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(queue)) {
        // 队列为空，新节点成为队头
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        // 将新节点插入到队尾
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

④ 出队操作

// 出队操作
int dequeue(LinkedQueue* queue) {
    int value = -1;
    if (!isEmpty(queue)) {
        // 保存队头节点的值
        value = queue->front->data;

        // 删除队头节点
        Node* temp = queue->front;
        queue->front = queue->front->next;
        free(temp);

        // 队列为空时，更新rear指针
        if (queue->front == NULL) {
            queue->rear = NULL;
        }
    }
    return value;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

⑤获取队列中元素的个数

// 获取队列的长度
int getQueueLength(LinkedQueue* queue) {
    Node* current = queue->front;
    int length = 0;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}
1
2
3
4
5
6
7
8
9
10

⑥打印队列内元素

// 打印队列内的元素
void printQueue(LinkedQueue* queue) {
    Node* current = queue->front;
    printf("Queue: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10

四、链式队列的应用

链式队列适用于在不确定队列大小的情况下，动态地存储数据。它可以用于解决生产者-消费者问题，以及在需要异步处理数据的情况下。

五、总结

①入队操作：

• 当队列为空时，新节点既是队头也是队尾。
• 当队列不为空时，将新节点插入到队尾，并更新rear指针为新节点。
• 入队操作涉及动态内存分配，要注意释放节点内存以避免内存泄漏。

②出队操作：

• 在出队操作之前，要先检查队列是否为空，避免出现空队列的错误。
• 出队操作要删除队头节点，并更新front指针为下一个节点。
• 如果队列为空，同时要更新rear指针为空。

③判断队列是否为空：

• 需要根据front指针是否为空来判断队列是否为空。

④获取队列长度：

• 需要遍历队列中的节点，并计算节点个数来获取队列长度。

⑤动态内存管理：

• 在链式队列中，需要使用malloc函数为节点分配内存空间。
• 在节点不再需要时，要使用free函数释放节点的内存空间，以避免内存泄漏。

⑥打印队列元素：

• 可以通过遍历队列的节点，并输出节点的数据来打印队列中的元素。

⑦队列的初始化：

• 在使用链式队列之前，要先对其进行初始化，将front和rear指针都设置为空。

⑧注意空队列和满队列：

• 链式队列一般不会出现满队列的情况，但要注意空队列的处理，以避免出现空指针引用错误。

⑨链表的插入和删除：

• 在链式队列中，入队操作涉及链表的插入，而出队操作涉及链表的删除。要确保插入和删除的指针操作正确，避免出现内存泄漏或者空指针错误。

⑩异常处理：

• 在队列操作时，要考虑异常情况，如空队列出队、空指针操作等，要对这些情况进行适当的处理，避免程序崩溃或出现不可预料的错误。

六、全部代码

①listqueue.h

#ifndef _LISTQUEUE_H_
#define _LISTQUEUE_H_
#include <stdio.h>
#include <stdlib.h>
typedef int TypeData;
typedef struct Node {
    TypeData data;
    struct Node* next;
} Node;

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

// 初始化链式队列
void initLinkedQueue(LinkedQueue* queue);

// 判断队列是否为空
int isEmpty(LinkedQueue* queue);

// 入队操作
void enqueue(LinkedQueue* queue, TypeData value) ;

// 出队操作
int dequeue(LinkedQueue* queue);

// 获取队列的长度
int getQueueLength(LinkedQueue* queue)

// 打印队列内的元素
void printQueue(LinkedQueue* queue);

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

②listqueue.c

#include "listqueue.h"
// 初始化链式队列
void initLinkedQueue(LinkedQueue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

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

// 入队操作
void enqueue(LinkedQueue* queue, TypeData value) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(queue)) {
        // 队列为空，新节点成为队头
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        // 将新节点插入到队尾
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队操作
int dequeue(LinkedQueue* queue) {
    int value = -1;
    if (!isEmpty(queue)) {
        // 保存队头节点的值
        value = queue->front->data;

        // 删除队头节点
        Node* temp = queue->front;
        queue->front = queue->front->next;
        free(temp);

        // 队列为空时，更新rear指针
        if (queue->front == NULL) {
            queue->rear = NULL;
        }
    }
    return value;
}

// 获取队列的长度
int getQueueLength(LinkedQueue* queue) {
    Node* current = queue->front;
    int length = 0;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

// 打印队列内的元素
void printQueue(LinkedQueue* queue) {
    Node* current = queue->front;
    printf("Queue: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

③listqueue_main.c

#include "listqueue.h"
#include "listqueue.c"
int main() {
    LinkedQueue queue;
    initLinkedQueue(&queue);

    // 入队操作
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    // 打印队列内的元素
    printQueue(&queue);

    // 获取队列长度
    int length = getQueueLength(&queue);
    printf("Queue length: %d\n", length);

    // 出队操作
    int value = dequeue(&queue);
    printf("Dequeued value: %d\n", value);

    // 打印出队后的队列
    printQueue(&queue);

    // 获取出队后的队列长度
    length = getQueueLength(&queue);
    printf("Queue length: %d\n", length);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

七、结果