• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

焯【数据结构】队列的基本概念 | 从零开始实现队列 | 思路草图

互联网 diligentman 2小时前 3次浏览

焯【数据结构】队列的基本概念 | 从零开始实现队列 | 思路草图

前言:

本章我们将学习 "队列" ,首先介绍队列的概念和结构,然后我们将着重讲解栈的实现。我们从零开始写队列的接口,并从零开始步步解读。本章将继续巩固画思路草图的能力,只要思路草图画好了,就可以很轻松地将其转换成代码。


一、队列(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 QueueIfEmpty(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;                 //创建遍历指针cur
    while(cur != NULL) {                 //cur不为空就进入循环
        QueueNode* curNext = cur->next;  //信标指针curNext
        free(cur);                       //释放cur当前指向的节点
        cur = curNext;                   //移动指针cur
    }
    pQ->pHead = pQ->pTail = NULL;        //置空干掉野指针
}

🔑 解读:

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

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

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

0x02 判断队列是否为空

💬 Queue.h

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

🔑 解读:布尔值,返回 true false

💬 Queue.c

/* 判断队列是否为空 */
bool QueueIfEmpty(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(EXIT_FAILURE);
    }
    /* 放置 */
    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 交给 datanext 默认置空,和之前学链表一样,这里就不过多赘述了。

③ 新节点创建好后,我们可以开始写入队的操作了。首先要理解队列的性质:队尾入数据,队头出数据。这里既然是入队,就要在对尾后面进行插入。这里我们还要考虑到如果队列为空的情况,这时我们要把头指针和尾指针都交付给 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(!QueueIfEmpty(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 为空,这里还要放置队列为空,如果队列为空还要求出队的话会出问题的,所以这里要断言一下 QueueIfEmpty 为假。

② 思路草图如下:

焯【数据结构】队列的基本概念 | 从零开始实现队列 | 思路草图

出数据需要释放,和销毁一样,这里使用一个类似于信标性质的指针来记录 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(!QueueIfEmpty(pQ));             //防止队列为空

    return pQ->pHead->data;
}  

🔑 解读:

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

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

0x06 返回队尾数据(QueueBack)

💬 Queue.h

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

💬 Queue.c

/* 返回队尾数据 */
QueueDataType QueueBack(Queue* pQ) {
    assert(pQ);                            //防止传入的pQ为空
    assert(!QueueIfEmpty(pQ));             //防止队列为空

    return pQ->pTail->data;
}

🔑 解读:

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

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

0x07 求队列大小(QueueSize)

💬 Queue.h

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

💬 Queue.c

/* 求队列大小:计数器法 */
int QueueSize(Queue* pQ) {
    assert(pQ);             //防止传入的pQ为空

    int count = 0;          //计数器           
    QueueNode* cur = pQ;    //创建遍历指针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 QueueIfEmpty(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;                 //创建遍历指针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(EXIT_FAILURE);
    }
    /* 放置 */
    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(!QueueIfEmpty(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(!QueueIfEmpty(pQ));             //防止队列为空

    return pQ->pHead->data;
}   

/* 返回队尾数据 */
QueueDataType QueueBack(Queue* pQ) {
    assert(pQ);                            //防止传入的pQ为空
    assert(!QueueIfEmpty(pQ));             //防止队列为空

    return pQ->pTail->data;
}

/* 求队列大小:计数器法 */
int QueueSize(Queue* pQ) {
    assert(pQ);             //防止传入的pQ为空

    int count = 0;          //计数器           
    QueueNode* cur = pQ;    //创建遍历指针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(!QueueIfEmpty(&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

❌ 勘误: 无

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

本篇完。


喜欢 (0)