write in front
个人主页:认真写博客的夏目浅石.
欢迎各位→点赞 + 收藏⭐️ + 留言
系列专栏:

二、队列的结构

队列可以使用 数组链表实现,但是二者之间有不同的地方,哪一个更加适合队列呢?

我想:使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数
组头上出数据,效率会比较低

三、队列的实现

3.1结构体的定义

typedef char QDatatype;typedef struct QueueNode{    struct QueueNode* next;    QDatatype data;}QNode;

由于链表的尾插比较麻烦,而队列的入数据为尾插。所以定义队列的结构体时,可以定义两个指针 head tail 分别对应 队头 和 队尾 ,tail 的引入就是方便尾插再在给定一个 size 实时记录队列的大小。

typedef struct Queue{    QNode* head;    QNode* tail;    int size;}Queue;

3.2函数接口

void QueueInit(Queue* pq);//初始化void QueueDestroy(Queue* pq);//销毁void QueuePush(Queue* pq,QDatatype x);//入队列void QueuePop(Queue* pq);//出队列int QueueSize(Queue* pq);//计算队列大小bool QueueEmpty(Queue* pq);//判断队列是否为空QDatatype QueueFront(Queue* pq);//取对头元素QDatatype QueueBack(Queue* pq);//取队尾元素

3.3初始化

要领: 队列对头队尾相等都为NULL,且size=0;

void QueueInit(Queue* pq){    //暴力检查    assert(pq);    pq->head=pq->tail=NULL;    pq->size=0;}

3.4销毁

要领:cur不断遍历,然后free节点,最后处理headtail即可;

void QueueDestroy(Queue* pq){    assert(pq);    QNode* cur=pq->head;    while(cur)    {        QNode* tmp=cur->next;        free(cur);        cur=tmp;    }    pq->head=pq->tail=NULL;    pq->size=0;}

3.5入队列

要领: 尾节点(tail)进行插入;

void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{newnode->data = x;newnode->next = NULL;}// 尾插if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->size++; }

3.6出队列

要领: 找到原本头节点的下一个节点 更换一下新的头节点就好了,注意free就行

void QueuePop(Queue* pq){    assert(pq);    assert(pq->head!=NULL);    QNode* tmp=pq->head->next;    free(pq->head);    pq->head=tmp;    if(pq->head==NULL)    {        pq->tail=NULL;    }    pq->size--;}

3.7计算队列大小

要领: 返回size的大小即可;

int QueueSize(Queue* pq){    assert(pq);    return pq->size;}

3.8判断队列是否为空

要领: 其实本质就是看size是否为0;

bool QueueEmpty(Queue* pq){    assert(pq);    return pq->size==0;}

3.9取对头元素

要领: 队列非空,取 head 出数据

QDatatype QueueFront(Queue* pq){    assert(pq);    assert(!QueueEmpty(pq));    return pq->head->data;}

3.10取队尾元素

要领: 队列非空,取 tail 处数据。

QDatatype QueueBack(Queue* pq){    assert(pq);    assert(!QueueEmpty(pq));    return pq->tail->data;}

四、队列的总代码

#include#include#include#includetypedef char QDatatype;typedef struct QueueNode{    struct QueueNode* next;    QDatatype data;}QNode;typedef struct Queue{    QNode* head;    QNode* tail;    int size;}Queue;void QueueInit(Queue* pq);void QueueDestroy(Queue* pq);void QueuePush(Queue* pq,QDatatype x);void QueuePop(Queue* pq);int QueueSize(Queue* pq);bool QueueEmpty(Queue* pq);QDatatype QueueFront(Queue* pq);QDatatype QueueBack(Queue* pq);//--------------------------手动分割线---------------------------//初始化void QueueInit(Queue* pq){    //暴力检查    assert(pq);    pq->head=pq->tail=NULL;    pq->size=0;}//--------------------------手动分割线---------------------------//销毁void QueueDestroy(Queue* pq){    assert(pq);    QNode* cur=pq->head;    while(cur)    {        QNode* tmp=cur->next;        free(cur);        cur=tmp;    }    pq->head=pq->tail=NULL;    pq->size=0;}//--------------------------手动分割线---------------------------void QueuePush(Queue* pq,QDatatype x){    assert(pq);    QNode* newnode=(QNode*)malloc(sizeof(QNode));    if(newnode==NULL)    {        perror("malloc fail");        return;    }    newnode->data=x;    newnode->next=NULL;        if(pq->head==NULL)    {        assert(pq->tail==NULL);        pq->head=pq->tail=newnode;    }    else    {        pq->tail->next=newnode;        pq->tail=newnode;    }    pq->size++;}//--------------------------手动分割线---------------------------void QueuePop(Queue* pq){    assert(pq);    assert(pq->head!=NULL);    QNode* tmp=pq->head->next;    free(pq->head);    pq->head=tmp;    if(pq->head==NULL)    {        pq->tail=NULL;    }    pq->size--;}//--------------------------手动分割线---------------------------int QueueSize(Queue* pq){    assert(pq);    return pq->size;}//--------------------------手动分割线---------------------------bool QueueEmpty(Queue* pq){    assert(pq);    return pq->size==0;}//--------------------------手动分割线---------------------------QDatatype QueueFront(Queue* pq){    assert(pq);    assert(!QueueEmpty(pq));    return pq->head->data;}//--------------------------手动分割线---------------------------QDatatype QueueBack(Queue* pq){    assert(pq);    assert(!QueueEmpty(pq));    return pq->tail->data;}


总结

  今天学习了单链表的知识,初次写数据结构的知识,给我的感觉就是,学三遍不如手敲代码一遍来的实在,所以数据结构的学习我将多画图,多敲代码来学习,希望大家吸取经验和我一起学习数据结构,为后面打比赛刷题打下坚实基础。

  我是夏目浅石,希望和你一起学习进步,刷题无数!!!希望各位大佬能一键三连支持一下博主,hhhh~我们下期见喽

如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn

原创不易,还希望各位大佬支持一下 \textcolor{blue}{原创不易,还希望各位大佬支持一下} 原创不易,还希望各位大佬支持一下

点赞,你的认可是我创作的动力! \textcolor{9c81c1}{点赞,你的认可是我创作的动力!} 点赞,你的认可是我创作的动力!

⭐️ 收藏,你的青睐是我努力的方向! \textcolor{ed7976}{收藏,你的青睐是我努力的方向!} 收藏,你的青睐是我努力的方向!

✏️ 评论,你的意见是我进步的财富! \textcolor{98c091}{评论,你的意见是我进步的财富!} 评论,你的意见是我进步的财富!