7.5 C/C++ 实现链表队列_c 结构体加入 链表队列

链表队列是一种基于链表实现的队列，相比于顺序队列而言，链表队列不需要预先申请固定大小的内存空间，可以根据需要动态申请和释放内存。在链表队列中，每个节点包含一个数据元素和一个指向下一个节点的指针，头节点表示队头，尾节点表示队尾，入队操作在队尾插入元素，出队操作在队头删除元素，队列的长度由节点数量决定。由于链表队列没有容量限制，因此可以处理任意数量的元素，但是相比于顺序队列，链表队列的访问速度较慢，因为需要通过指针来访问下一个节点。

读者需自行创建头文件linkqueue.h并拷贝如下链表队列代码实现；

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

struct BiNode
{
    int data;
    struct BiNode *lchild;
    struct BiNode *rchild;
};

// 链表结点的数据类型
struct QueueNode
{
    struct QueueNode *next;
};

struct LQueue
{
    struct QueueNode header; // 头结点
    struct QueueNode *rear;  // 尾指针
    int size;
};

typedef void* LinkQueue;

// 初始化
LinkQueue InitLinkQueue()
{
    struct LQueue *queue = malloc(sizeof(struct LQueue));
    if (NULL == queue)
    {
        return NULL;
    }

    queue->header.next = NULL;
    queue->size = 0;
    queue->rear = &(queue->header);
    return queue;
}

// 入队
void PushLinkQueue(LinkQueue queue, void *data)
{
    if (NULL == queue || NULL == data)
    {
        return;
    }

    struct LQueue *q = (struct LQueue *)queue;
    struct QueueNode *n = (struct QueueNode *)data;

    q->rear->next = n;
    n->next = NULL;

    // 更新尾指针
    q->rear = n;
    q->size++;
}

// 出队
void PopLinkQueue(LinkQueue queue)
{
    if (NULL == queue)
    {
        return;
    }

    struct LQueue *q = (struct LQueue *)queue;
    if (q->size == 0)
    {
        return;
    }

    if (q->size == 1)
    {
        q->header.next = NULL;
        q->rear = &(q->header);
        q->size--;
        return;
    }

    struct QueueNode *pFirstNode = q->header.next;
    q->header.next = pFirstNode->next;
    q->size--;
}

// 获得队头元素
void* FrontLinkQueue(LinkQueue queue)
{
    if (NULL == queue)
    {
        return NULL;
    }

    struct LQueue *q = (struct LQueue *)queue;
    return q->header.next;
}

// 获得队尾元素
void* BackLinkQueue(LinkQueue queue)
{
    if (NULL == queue)
    {
        return NULL;
    }

    struct LQueue *q = (struct LQueue *)queue;
    return q->rear;
}

// 获得队列长度
int SizeLinkQueue(LinkQueue queue)
{
    if (NULL == queue)
    {
        return -1;
    }

    struct LQueue *q = (struct LQueue *)queue;
    return q->size;
}

// 销毁队列
void DestroyLinkQueue(LinkQueue queue)
{
    if (NULL == queue)
    {
        return;
    }

    struct LQueue *q = (struct LQueue *)queue;
    q->header.next = NULL;
    q->rear = NULL;
    q->size = 0;

    free(queue);
    queue = NULL;
}
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

在主函数中使用也很容易，首先定义Studnet结构体，通过调用InitLinkQueue初始化队列，并使用PushLinkQueue向队列中插入元素，函数BackLinkQueue可用于获取到队列队尾元素，函数PopLinkQueue用于弹出元素，函数DestroyLinkQueue则用于销毁队列。

#include"linkqueue.h"

struct Student
{
    struct QueueNode node;
    char name[64];
    int age;
};

int main(int argc, char *argv[])
{
    // 初始化队列
    LinkQueue queue = InitLinkQueue();

    // 创建数据
    struct Student p1 = { NULL, "aaa", 10 };
    struct Student p2 = { NULL, "bbb", 20 };
    struct Student p3 = { NULL, "ccc", 30 };
    struct Student p4 = { NULL, "ddd", 40 };
    struct Student p5 = { NULL, "eee", 50 };
    struct Student p6 = { NULL, "fff", 60 };

    // 插入队列
    PushLinkQueue(queue, &p1);
    PushLinkQueue(queue, &p2);
    PushLinkQueue(queue, &p3);
    PushLinkQueue(queue, &p4);
    PushLinkQueue(queue, &p5);
    PushLinkQueue(queue, &p6);

    struct Student *pBack = (struct Student *)BackLinkQueue(queue);
    printf("队尾元素: %s %d\n", pBack->name, pBack->age);

    while (SizeLinkQueue(queue) > 0)
    {
        // 获得队头元素
        struct Student *person = (struct Student *)FrontLinkQueue(queue);
        
        // 打印队头元素
        printf("姓名: %s 年龄: %d \n", person->name, person->age);
        
        // 弹出队头元素
        PopLinkQueue(queue);
    }
    
    // 销毁队列
    DestroyLinkQueue(queue);

    system("pause");
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51