🚀write in front🚀
📝个人主页：认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏：C语言实现数据结构
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊
✉️如果无聊的话，就来逛逛我的博客栈吧stack-frame.cn

前言

今天打算给大家讲解队列这一个知识点，会把函数接口一一列举出来 并且 依次实现，这样才会更加牢固的掌握队列这一基本数据结构，话不多说，让我们一起来学习吧。

一、队列的概念

队列 与 栈 链表都是一种线性表结构。

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

数据结构图如下：

二、队列的结构

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

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

三、队列的实现

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节点，最后处理head与tail即可；

void QueueDestroy(Queue* pq)
{
    assert(pq);

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

3.5入队列

要领： 尾节点（tail）进行插入；

void QueuePush(Queue* pq,QDatatype x)
{
    Queue* newnode=(Queue*)malloc(sizeof(Queue));
    if(newnode==NULL)
    {
        perror("malloc fail");
        return;
    }
    newnode->data=x;
    newnode->nxet=NULL;
    
    if(pq->head=NULL)
    {
        assert(pq->tail==NULL)
        pq->head=pq->tail=newnode;
    }
    else
    {
        pq->tail->next=newnode;
        pq->tail=newnode;
    }
    pq->size++;
}

3.6出队列

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

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head!=NULL);

    Queue* 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<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef 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);

    Queue* cur=pq->head;
    while(cur)
    {
        Queue* tmp=cur->next;
        free(cur);
        cur=tmp;
    }
    pq->head=pq->tail=NULL;
    pq->size=0;
}
//--------------------------手动分割线---------------------------

void QueuePush(Queue* pq,QDatatype x)
{
    Queue* newnode=(Queue*)malloc(sizeof(Queue));
    if(newnode==NULL)
    {
        perror("malloc fail");
        return;
    }
    newnode->data=x;
    newnode->nxet=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);

    Queue* 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

✨$原创不易，还希望各位大佬支持一下$

👍 $点赞，你的认可是我创作的动力！$

⭐️ $收藏，你的青睐是我努力的方向！$

✏️ $评论，你的意见是我进步的财富！$