基于链表实现队列的初始化、入队、出队及销毁操作

二、核心功能实现：从零搭建完整队列

下面也是实现一些插入、删除操作，先进行初始化。

2.1 准备工作：搭建稳固的基础

2.1.1 队列初始化：一切从这里开始

初始，头、尾指针均指向 NULL。

//初始化 
void QueueInit(Queue* pq) {
    assert(pq); //防止空指针
    pq->phead = pq->ptail = NULL;
}

2.1.2 判空检测：守护队列的'安全门'

此操作，在出队列时，判断是否有节点。

bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->phead == NULL;
}

2.2 入队操作：在队尾优雅地添加数据

//入队（尾插） 
void QueuePush(Queue* pq, QDataType x) {
    assert(pq);
    //创建新节点
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    //刚开始，链表为空，没有节点
    if (pq->phead == NULL) {
        pq->phead = pq->ptail = newnode;
    } else {
        pq->ptail->next = newnode; //尾指针链接新节点
        pq->ptail = pq->ptail->next; //尾指针移动到新节点
    }
}

--插入节点就要先申请一份节点大小的空间，其中节点结构：Data 存要求插入的数据，next 指 NULL。

--刚开始，队列中没有节点，新插入的节点为第一节点，导致头指针、尾指针都指向新节点。

--以后直接是尾指针 next 指向新节点，然后尾指针移动到新节点。

2.3 出队操作：从队头安全地移除数据

//出队列 
void QueuePop(Queue* pq) {
    assert(!QueueEmpty(pq)); //队列是否有节点
    //队列中只有一个节点
    if (pq->phead == pq->ptail) {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    } else {
        //创建指针将下个节点保存
        QueueNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
}

--操作前，先判断队列是否有节点，有节点才能出队列。

--没有节点，头指针、尾指针都指向空。

--否则，创建新 next 指针将第二节点的地址先保存（也就是头指针指向的结构体中的 next 指针保存着地址），释放后，头指针指向新指针。

2.4 销毁队列：善始善终的内存管理

销毁队列，需要遍历队列依次释放空间（注意提前保存下一节点的地址），最后将头指针、尾指针置空。

//销毁 
void QueueDestroy(Queue* pq) {
    assert(pq);
    QueueNode* pcur = pq->phead;
    while (pcur) {
        //保存下一节点的地址
        QueueNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    pq->phead = pq->ptail = NULL;
}

三、功能扩展：让队列更加强大

3.1 窥探队首：获取但不破坏

因为事先已经定义了指向头节点的指针，且指向的结构体中存在存储当前节点数据的 data 变量，直接返回 data 即可。

//取队头数据 
QDataType QueueFront(Queue* pq) {
    assert(!QueueEmpty(pq));
    return pq->phead->data;
}

随着 phead 指向的改变，其指向的结构体中访问到的 data、next 也随之改变。

3.2 窥探队尾：快速访问末端元素

与上面的取队首数据算法思路一样，也是事先定义了指向尾节点的指针，且指向的结构体中存在存储当前节点数据的 data 变量，直接返回 data 即可。

//取队尾数据 
QDataType QueueBack(Queue* pq) {
    assert(!QueueEmpty(pq));
    return pq->ptail->data;
}

3.3 清点元素：高效统计队列大小

这就需要循环内遍历到尾节点，统计个数。

//队列有效元素个数 
int QueueSize(Queue* pq) {
    assert(pq);
    QueueNode* pcur = pq->phead;
    int size = 0;
    while (pcur) {
        ++size;
        pcur = pcur->next;
    }
    return size;
}

四、完整代码展示：理论与实践的完美结合

4.1 Queue.h：队列的'蓝图'与接口

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

typedef int QDataType;
//链表节点结构 
typedef struct QueueNode {
    QDataType data;
    struct QueueNode* next;
}QueueNode;
//队列结构 
typedef struct Queue {
    QueueNode* phead; //指向队头
    QueueNode* ptail; //指向队尾
}Queue;

//初始化 
void QueueInit(Queue* pq);
//判队列是否为空 
bool QueueEmpty(Queue* pq);
//入队（尾插） 
void QueuePush(Queue* pq, QDataType x);
//出队列 (队头) 
void QueuePop(Queue* pq);
//取队头数据 
QDataType QueueFront(Queue* pq);
//取队尾数据 
QDataType QueueBack(Queue* pq);
//队列有效元素个数 
int QueueSize(Queue* pq);
//销毁 
void QueueDestroy(Queue* pq);

4.2 Queue.c：核心逻辑的完整实现

#include "Queue.h"

//初始化 
void QueueInit(Queue* pq) {
    assert(pq); //不能传空指针
    pq->phead = pq->ptail = NULL;
}

//入队（尾插） 
void QueuePush(Queue* pq, QDataType x) {
    assert(pq);
    //创建新节点
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    //刚开始，链表为空，没有节点
    if (pq->phead == NULL) {
        pq->phead = pq->ptail = newnode;
    } else {
        pq->ptail->next = newnode; //尾指针链接新节点
        pq->ptail = pq->ptail->next; //尾指针移动到新节点
    }
}

//判队列是否为空 
bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->phead == NULL;
}

//出队列 
void QueuePop(Queue* pq) {
    assert(!QueueEmpty(pq));
    //队列中只有一个节点
    if (pq->phead == pq->ptail) {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    } else {
        //创建指针将下个节点保存
        QueueNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
}

//取队头数据 
QDataType QueueFront(Queue* pq) {
    assert(!QueueEmpty(pq));
    return pq->phead->data;
}

//取队尾数据 
QDataType QueueBack(Queue* pq) {
    assert(!QueueEmpty(pq));
    return pq->ptail->data;
}

//队列有效元素个数 
int QueueSize(Queue* pq) {
    assert(pq);
    QueueNode* pcur = pq->phead;
    int size = 0;
    while (pcur) {
        ++size;
        pcur = pcur->next;
    }
    return size;
}

//销毁 
void QueueDestroy(Queue* pq) {
    assert(pq);
    QueueNode* pcur = pq->phead;
    while (pcur) {
        //保存下一节点的地址
        QueueNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    pq->phead = pq->ptail = NULL;
}

4.3 test.c：功能验证与测试用例

#include "Queue.h"

void test01() {
    //初始化
    Queue q;
    QueueInit(&q);
    //入队
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    //出队
    /*QueuePop(&q); QueuePop(&q); QueuePop(&q); QueuePop(&q);*/
    //取队首
    /*printf("%d->", QueueFront(&q)); QueuePop(&q); printf("%d->", QueueFront(&q)); QueuePop(&q); printf("%d->", QueueFront(&q)); QueuePop(&q); printf("%d->", QueueFront(&q));*/
    //取队尾
    //printf("%d->", QueueBack(&q));
    //有效数据
    printf("size：%d\n", QueueSize(&q));
}

int main() {
    test01();
    return 0;
}

**结语：**队列的实现标志着你在线性数据结构领域已登堂入室。接下来，二叉树与堆的学习将带你进入非线性数据结构的新世界。有趣的是，队列正是基于堆实现的——现在打下的队列基础，将在下一章绽放新的光彩。