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

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

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

0x01 销毁队列（QueueDestroy）

/* 销毁队列：free掉所有队列元素并将头尾置空 */
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的空间 */
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    /* 检查malloc */
    if(new_node == NULL) {
        printf("malloc failed!\n");
        exit(-1);
    }
    /* 放置 */
    new_node->data = x;     //待插入的数据
    new_node->next = NULL;  //默认为空
    
    /* 入队：
     *【思路草图】
     *   情况1：队列为空：既当头又当尾
     *         [new_node]
     *           ↑    ↑
     *         pHead pTail
     * 
     *   情况2：队列不为空：队尾入数据
     *          [] -> [] -> [] -> []   ->  [new_node]
     *         pHead             pTail     pTail->next
     *                            ↓             ↑
     *                            ----------→ pTail（更新尾指针）
     */
    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));             //防止队列为空
 
    /* 出队:
     *【思路草图】
     *        [free] ->  []     -> [] -> []
     *        pHead    headNext  
     *           ↓         ↑
     *           -------→ pHead（更新头指针）
     */
    QueueNode* headNext = pQ->pHead->next; //信标指针HeadNext
    free(pQ->pHead);
    pQ->pHead = headNext;                  //更新头
 
    /* 如果队内都被删完了，不处理pTail就会带来野指针的隐患 
     * 【思路草图】
     *          NULL               已经被free掉的内存！
     *           ↑                         ↑   （野指针警告）
     *         pHead(因为HeadNext是NULL)  pTail
    */
    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>
 
/* 队列初始化：将头尾指针置为NULL */
void QueueInit(Queue* pQ) {
    assert(pQ);                          //防止传入的pQ为空
 
    pQ->pHead = pQ->pTail = NULL;        //将头尾指针置空
}
 
/* 销毁队列：free掉所有队列元素并将头尾置空 */
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的空间 */
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    /* 检查malloc */
    if(new_node == NULL) {
        printf("malloc failed!\n");
        exit(-1);
    }
    /* 放置 */
    new_node->data = x;     //待插入的数据
    new_node->next = NULL;  //默认为空
    
    /* 入队：
     *【思路草图】
     *   情况1：队列为空：既当头又当尾
     *         [new_node]
     *           ↑    ↑
     *         pHead pTail
     * 
     *   情况2：队列不为空：队尾入数据
     *          [] -> [] -> [] -> []   ->  [new_node]
     *         pHead             pTail     pTail->next
     *                            ↓             ↑
     *                            ----------→ pTail（更新尾指针）
     */
    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));             //防止队列为空
 
    /* 出队:
    
     *【思路草图】
     *        [free] ->  []     -> [] -> []
     *        pHead    headNext  
     *           ↓         ↑
     *           -------→ pHead（更新头指针）
     */
    QueueNode* headNext = pQ->pHead->next; //信标指针HeadNext，防止释放pHead后找不到其下一个节点
    free(pQ->pHead);
    pQ->pHead = headNext;                  //更新头
 
    /* 如果队内都被删完了，不处理pTail就会带来野指针的隐患 
     * 【思路草图】
     *          NULL               已经被free掉的空间！
     *           ↑                         ↑   （野指针）
     *         pHead(因为HeadNext是NULL)  pTail
    */
    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;
}

参考资料：

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

? 笔者：王亦优

? 更新： 2021.11.17

? 勘误：无

? 声明：由于作者水平有限，本文有错误和不准确之处在所难免，本人也很想知道这些错误，恳望读者批评指正！

本篇完。

频道导航

C语言数据结构系列队列篇

目录

一、队列（Queue）

0x00 队列的概念

0x01 队列的结构

二、队列的定义

0x00 链式队列

0x02 接口函数

三、队列的实现

0x00 队列初始化（QueueInit）

0x01 销毁队列（QueueDestroy）

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

0x03 入队（QueuePush）

0x04 出队（QueuePop）

0x05 返回队头数据（QueueFront）

0x06 返回队尾数据（QueueBack）

0x07 求队列大小（QueueSize）

0x08 完整代码

您可能感兴趣的文章: