C语言中队列的示例分析

这篇文章将为大家详细讲解有关C语言中队列的示例分析，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

一、队列（Queue）

0x00 队列的概念

???? 概念：

① 队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

② 入队列，进行插入操作的一端称为 队尾。出队列，进行删除操作的一端称为 队头。

③ 队列中的元素遵循先进先出的原则，即 FIFO 原则（First In First Out）

0x01 队列的结构

???? 结构：

二、队列的定义

0x00 链式队列

typedef int QueueDataType;   //队列类型 typedef struct QueueNode {    struct QueueNode* next;  //指向下一个节点    QueueDataType data;      //数据} QueueNode; typedef struct Queue {    QueueNode* pHead;        //头指针    QueueNode* pTail;        //尾指针} Queue;

❓ 为什么不使用单链表？

???? 单链表我们只定义了一个指针指向头，没有定义尾指针。因为定义尾指针解决不了问题，比如尾插尾删。所以我们没有必要定义一个结构体把他们封到一起。这里我们再定义一个头指针 head 一个尾指针 tail ，这两个指针才有意义。因为根据队列的性质，我们只会在队尾插，不会再队尾删。所以这个尾指针的价值就得到了完美的体现，实际中定义几个指针是看你的需求确定的。

0x02 接口函数

???? 这是需要实现几个接口函数：

void QueueInit(Queue* pQ);                  //队列初始化void QueueDestroy(Queue* pQ);               //销毁队列bool QueueIsEmpty(Queue* pQ);               //判断队列是否为空void QueuePush(Queue* pQ, QueueDataType x); //入队void QueuePop(Queue* pQ);                   //出队QueueDataType QueueFront(Queue* pQ);        //返回队头数据QueueDataType QueueBack(Queue* pQ);         //返回队尾数据int QueueSize(Queue* pQ);                   //求队列大小

三、队列的实现

0x00 队列初始化（QueueInit）

???? Queue.h

#pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <stdbool.h> typedef int QueueDataType;   //队列类型 typedef struct QueueNode {    struct QueueNode* next;  //指向下一个节点    QueueDataType data;      //数据} QueueNode; typedef struct Queue {    QueueNode* pHead;        //头指针    QueueNode* pTail;        //尾指针} Queue; void QueueInit(Queue* pQ);   //队列初始化

???? Queue.c

void QueueInit(Queue* pQ) {    assert(pQ);                          //防止传入的pQ为空     pQ->pHead = pQ->pTail = NULL;        //将头尾指针置空}

???? 解析：首先使用断言防止传入的pQ为空。初始化只需要把头指针和尾指针都置成空即可。

0x01 销毁队列（QueueDestroy）

void QueueDestroy(Queue* pQ) {    assert(pQ);                          //防止传入的pQ为空     QueueNode* cur = pQ->pHead;          //创建遍历指针cur    while(cur != NULL) {                 //cur不为空就进入循环        QueueNode* curNext = cur->next;  //信标指针curNext，防止释放cur后找不到其下一个节点        free(cur);                       //释放cur当前指向的节点        cur = curNext;                   //移动指针cur    }    pQ->pHead = pQ->pTail = NULL;        //置空干掉野指针}

???? 解读：

① 首先断言防止传入的pQ为空。

② 销毁要把所有节点都释放掉，我们创建遍历指针 cur 遍历整个队列。既然要释放 cur 指向的节点，为了防止释放 cur 之后找不到其下一个节点导致无法移动，我们这里创建一个类似于信标性质的指针 curNext 来记录一下 cur 的下一个节点，之后再 free 掉 cur，这样就可以移动 cur 了。

③ 最后为了防止野指针，还需要把头指针和尾指针都置为空。

0x02 判断队列是否为空（HeapIsEmpty）

???? Queue.h

bool QueueIsEmpty(Queue* pQ);               //判断队列是否为空

???? 解读：布尔值，返回 true 或 false

???? Queue.c

bool QueueIsEmpty(Queue* pQ) {    assert(pQ);                          //防止传入的pQ为空     return pQ->pHead == NULL;            //如果成立则为True，不成立则为False}

???? 解读：

① 首先断言防止传入的pQ为空。

② 判断队列是否为空，可以直接返回，巧妙地利用布尔类型的特性。如果 pQ->pHead == NULL 成立则为真，会返回 true；不成立则为假，会返回 false。

0x03 入队（QueuePush）

???? Queue.h

void QueuePush(Queue* pQ, QueueDataType x); //入队

???? Queue.c

void QueuePush(Queue* pQ, QueueDataType x) {    assert(pQ);             //防止传入的pQ为空         QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));        if(new_node == NULL) {        printf("malloc failed!\n");        exit(-1);    }        new_node->data = x;     //待插入的数据    new_node->next = NULL;  //默认为空            if(pQ->pHead == NULL) {                //情况1: 队列为空        pQ->pHead = pQ->pTail = new_node;  //       既当头又当尾    } else {                               //情况2: 队列不为空        pQ->pTail->next = new_node;        //       在现有尾的后一个节点放置new_node        pQ->pTail = new_node;              //       更新pTail，使它指向新的尾    }}

???? 解读：

① 首先断言防止传入的pQ为空。

② 我们首先要创建新节点。通过 malloc 动态内存开辟一块 QueueNode 大小的空间，都学到这里了大家想必都养成了检查 malloc 的好习惯了吧？。最后放置数据吗，将待插入的数据 x 交给 data，next 默认置空，和之前学链表一样，这里就不过多赘述了。

③ 新节点创建好后，我们可以开始写入队的操作了。首先要理解队列的性质：队尾入数据，队头出数据。这里既然是入队，就要在对尾后面进行插入。这里我们还要考虑到如果队列为空的情况，这时我们要把头指针和尾指针都交付给 new_node 。为了理清思路，我们可以画一个思路草图来帮助我们更好地理解：

有了这个图，我们就可以清楚地实现了：

if(pQ->pHead == NULL) {                //情况1: 队列为空    pQ->pHead = pQ->pTail = new_node;  //       既当头又当尾}else {                                 //情况2: 队列不为空    pQ->pTail->next = new_node;        //       在现有尾的后一个节点放置new_node    pQ->pTail = new_node;              //       更新pTail，使它指向新的尾}

当队列为空时，令头指针和尾指针都指向 new_node ，当队列不为空时，再尾部地下一个节点放置 new_node ，随后再更新尾指针让其指向新的尾（new_node 的位置）。

0x04 出队（QueuePop）

???? Queue.h

void QueuePop(Queue* pQ);                   //出队

???? Queue.c

 void QueuePop(Queue* pQ) {    assert(pQ);                            //防止传入的pQ为空    assert(!QueueIsEmpty(pQ));             //防止队列为空         QueueNode* headNext = pQ->pHead->next; //信标指针HeadNext    free(pQ->pHead);    pQ->pHead = headNext;                  //更新头         if(pQ->pHead == NULL)                  //如果pHead为空        pQ->pTail = NULL;                  //处理一下尾指针，将尾指针置空}

???? 解读：

① 首先断言防止传入的 pQ 为空，这里还要放置队列为空，如果队列为空还要求出队的话会出问题的，所以这里要断言一下 QueueIsEmpty 为假。

② 思路草图如下：

出数据需要释放，和销毁一样，这里使用一个类似于信标性质的指针来记录 pHead 的下一个节点，之后我们就可以大胆地释放 pHead 而不用担心找不到了。free 掉之后更新头即可，令头指针指向 headNext 即可。 

???? 注意：这里还要考虑一个问题，如果队内都被删完了，pHead 往后走指向空，但是 pTail 仍然指向那块已经被 free 掉的空间。pTail 就是一个典型的野指针。

我们可以不用担心 pHead，因为后面没有数据他会自然指向 NULL，但是我们这里得关注 pTail ！我们需要手动处理一下它：

如果 pHead 为空，我们就把 pTail 也置为空即可。

 if(pQ->pHead == NULL)                  //如果pHead为空        pQ->pTail = NULL;               //处理一下尾指针，将尾指针置空

0x05 返回队头数据（QueueFront）

???? Queue.h

QueueDataType QueueFront(Queue* pQ);        //返回队头数据

???? Queue.c

QueueDataType QueueFront(Queue* pQ) {    assert(pQ);                            //防止传入的pQ为空    assert(!QueueIsEmpty(pQ));             //防止队列为空     return pQ->pHead->data;}

???? 解读：

① 首先断言防止传入的 pQ 为空，这里我们还是要断言一下 QueueIsEmpty 为假，因为如果队内没有数据，还返回个锤子数据呢。

② 这里直接返回头的数据即可，特别简单没有什么好讲的。

0x06 返回队尾数据（QueueBack）

???? Queue.h

QueueDataType QueueBack(Queue* pQ);         //返回队尾数据

???? Queue.c

QueueDataType QueueBack(Queue* pQ) {    assert(pQ);                            //防止传入的pQ为空    assert(!QueueIsEmpty(pQ));             //防止队列为空     return pQ->pTail->data;}

???? 解读：

① 首先断言防止传入的 pQ 为空，断言一下 QueueIsEmpty 为假。

② 这里直接返回队尾的数据即可。

0x07 求队列大小（QueueSize）

???? Queue.h

int QueueSize(Queue* pQ);                   //求队列大小

???? Queue.c

int QueueSize(Queue* pQ) {    assert(pQ);             //防止传入的pQ为空     int count = 0;          //计数器               QueueNode* cur = pQ->pHead;    //创建遍历指针cur    while(cur != NULL) {        ++count;            //计数+1        cur = cur->next;    //移动指针cur    }    return count;}

???? 解读：这里我们采用计数器法来求大小即可，调用一次就是 O(N) ，也没什么不好的。

① 首先断言防止传入的 pQ 为空。

② 创建计数器变量和遍历指针 cur，遍历整个队列并计数，最后返回计数的结果即可。

0x08 完整代码

???? Queue.h

#pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <stdbool.h> typedef int QueueDataType;   //队列类型 typedef struct QueueNode {    struct QueueNode* next;  //指向下一个节点    QueueDataType data;      //数据} QueueNode; typedef struct Queue {    QueueNode* pHead;        //头指针    QueueNode* pTail;        //尾指针} Queue; void QueueInit(Queue* pQ);                  //队列初始化void QueueDestroy(Queue* pQ);               //销毁队列bool QueueIsEmpty(Queue* pQ);               //判断队列是否为空void QueuePush(Queue* pQ, QueueDataType x); //入队void QueuePop(Queue* pQ);                   //出队QueueDataType QueueFront(Queue* pQ);        //返回队头数据QueueDataType QueueBack(Queue* pQ);         //返回队尾数据int QueueSize(Queue* pQ);                   //求队列大小

???? Queue.c

#include <Queue.h> void QueueInit(Queue* pQ) {    assert(pQ);                          //防止传入的pQ为空     pQ->pHead = pQ->pTail = NULL;        //将头尾指针置空} void QueueDestroy(Queue* pQ) {    assert(pQ);                          //防止传入的pQ为空     QueueNode* cur = pQ->pHead;          //创建遍历指针cur    while(cur != NULL) {                 //cur不为空就进入循环        QueueNode* curNext = cur->next;  //信标指针curNext，防止释放cur后找不到其下一个节点        free(cur);                       //释放cur当前指向的节点        cur = curNext;                   //移动指针cur    }    pQ->pHead = pQ->pTail = NULL;        //置空干掉野指针} bool QueueIfEmpty(Queue* pQ) {    assert(pQ);                          //防止传入的pQ为空     return pQ->pHead == NULL;            //如果成立则为True，不成立则为False} void QueuePush(Queue* pQ, QueueDataType x) {    assert(pQ);             //防止传入的pQ为空         QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));        if(new_node == NULL) {        printf("malloc failed!\n");        exit(-1);    }        new_node->data = x;     //待插入的数据    new_node->next = NULL;  //默认为空            if(pQ->pHead == NULL) {                //情况1: 队列为空        pQ->pHead = pQ->pTail = new_node;  //       既当头又当尾    } else {                               //情况2: 队列不为空        pQ->pTail->next = new_node;        //       在现有尾的后一个节点放置new_node        pQ->pTail = new_node;              //       更新pTail，使它指向新的尾    }}  void QueuePop(Queue* pQ) {    assert(pQ);                            //防止传入的pQ为空    assert(!QueueIsEmpty(pQ));             //防止队列为空         QueueNode* headNext = pQ->pHead->next; //信标指针HeadNext，防止释放pHead后找不到其下一个节点    free(pQ->pHead);    pQ->pHead = headNext;                  //更新头         if(pQ->pHead == NULL)                  //如果pHead为空        pQ->pTail = NULL;                  //处理一下尾指针，将尾指针置空} QueueDataType QueueFront(Queue* pQ) {    assert(pQ);                            //防止传入的pQ为空    assert(!QueueIsEmpty(pQ));             //防止队列为空     return pQ->pHead->data;}    QueueDataType QueueBack(Queue* pQ) {    assert(pQ);                            //防止传入的pQ为空    assert(!QueueIsEmpty(pQ));             //防止队列为空     return pQ->pTail->data;} int QueueSize(Queue* pQ) {    assert(pQ);             //防止传入的pQ为空     int count = 0;          //计数器               QueueNode* cur = pQ->pHead;    //创建遍历指针cur    while(cur != NULL) {        ++count;            //计数+1        cur = cur->next;    //移动指针cur    }    return count;}

???? Test.c

#include "Queue.h" void TestQueue1() {    Queue q;    QueueInit(&q);     QueuePush(&q, 1);    QueuePush(&q, 2);    QueuePush(&q, 3);    QueuePush(&q, 4);     QueuePop(&q);    QueuePop(&q);    QueuePop(&q);    QueuePop(&q);    //QueuePop(&q);     QueueDestroy(&q);} void TestQueue2() {    Queue q;    QueueInit(&q);     QueuePush(&q, 1);    QueuePush(&q, 2);    QueuePush(&q, 3);    QueuePush(&q, 4);     //假设先入了1 2，让1出来，再继续入，它的顺序还是不会变。    // 永远保持先进先出的，无论是入了两个出两个，再入再出，还是全部入完了再出，都是不会变的。这就是队列的性质    while(!QueueIsEmpty(&q)) {        QueueDataType front = QueueFront(&q);        printf("%d ", front);        QueuePop(&q);  //pop掉去下一个    }    printf("\n");     QueueDestroy(&q);} int main(void) {    TestQueue2();     return 0;}

关于“C语言中队列的示例分析”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。