7.5 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;
}

在主函数中使用也很容易，首先定义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;
}