栈和队列（2）

队列（2）"/>

栈和队列（2）

目录

🍁一、链表的概念

🍁二、针对本文章给出的几点注意事项：

🍁三、队列的实现

🌕（一）、代码定义

注意：

🌕（二）、初始化

🌕（三）、入队

🌕（四）、出队

🌕（五）、取队头元素

🌕（六）、取队尾元素

🌕（七）、判空

🌕（八）、获取队列元素个数

🌕（九）、销毁

🌕（十）、遍历

🍁、队列实现源代码

🌕（一）、main.c

🌕（二）、Queue.c

🌕（三）、Queue.h

🍁一、链表的概念

①：队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。 ②：队列具有 先进先出（简称FIFO (First In First Out)）的特点 ③：入队列：进行插入操作的一端称为 队尾        出队列：进行删除操作的一端称为 队头 ④：常见使用场景：

🍁二、针对本文章给出的几点注意事项：

（一）、队列使用单向队列即可，因为双向体现不了它的优势，而且双向还会多一个指针域，内存能省一点是一点

（二）、哨兵位（带头）可要可不要，因为哨兵一般解决结构体二级指针，而本次小编会以另外一种方法解决二级指针的问题

（三）、队列可以用数组实现，也可以用链表来实现，但优先选择链表，对于队列，链表的优势远大于数组，因为数组入队很简单，但出队就涉及数据的覆盖，比较麻烦；

（四）、在链表的头部进行出队，尾部进行入队。

（五）、队列实现的具体步骤我会放在代码注释里面，大家请注意一下！因为小编找不到合适的方式，有推荐的小伙伴可以评论区给小编一些建议。

🍁三、队列的实现

🌕（一）、代码定义

之前实现链表的时候我们知道，在不带头且插入第一个数据时会修改结构体指针，此时就需要使用二级指针的参与，从而分类讨论，是情况变得复杂；既然我们不带头，并且这里即需要头指针还需要尾指针，那么我们可以有如下实现：

typedef int QDatatype;
typedef struct QueueNode
{struct QueueNode* next;QDatatype data;
}QNode;typedef struct Queue
{QNode* head;//头指针，指向首结点QNode* tail;//尾指针，指向为结点int size;//记录队列长度
}Que;

我们将头指针head和尾指针tail重新封装成一个结构体，这样即使是在插入第一个数据，那么我们修改head指针，相当于修改结构体Queue的成员,所以我们全部情况只需要结构体Queue的一级指针即可；

注意：

截至目前：我们已经接触了三种改变结构体指针head不需要传参数二级指针的方法：

（一）、就是使用带哨兵的head，这样改变的是head的next域，即改变结构体成员；

（二）、使用不带哨兵的head，但最后会返回新head，在函数外面用适当的指针来接收返回值；

（三）、就是上述所示，在不带哨兵的情况，将头指针、尾指针封装成一个结构体，这样改变head或tail时，改变的是该结构体的成员，只需使用该结构体的一级指针即可；

🌕（二）、初始化

//初始化
void Queueinit(Que* ps)
{assert(ps);ps->head = ps->tail = NULL;ps->size = 0;
}

🌕（三）、入队

①：因为我们使用的是链表结构，所以不用考虑增容；

②：但入队的时候要注意第一次入队时的区别，从而分类讨论；

③：入队后元素数量加1；

//入队
void QueuePush(Que* ps, QDatatype x)
{assert(ps);//创建一个新结点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");return;}//因为是在尾结点入队，所以入队之后结点next域要置空newnode->data = x;newnode->next = NULL;//第一次插入是结构体指针之间的赋值,之后才是结构体成员的赋值，所以要分情况//记住tail指针始终指向尾结点，所以入队之后要对tail指针重定位if (ps->tail == NULL){ps->head = ps->tail = newnode;}else{ps->tail->next = newnode;ps->tail = newnode;}//入队后元素数量+1ps->size++;
}

🌕（四）、出队

出队的时候也要注意几点事项：

①：出队前，一定要检查队列是否为空；

②：因为队列涉及头指针head和尾指针tail，所以当出队列的最后一个元素后，head和tail指针都要指向NULL,所以我们可以分类讨论以防万一；

③：出队后元素数量size减1

//出队
void QueuePop(Que* ps)
{assert(ps);//检查队列是否为空，若为空则assert函数报错提示assert(!QueueEmpty(ps));//队列不为空，进行尾删//当对列只剩下一个元素时,要注意head和tail指针都要指向NULL，所以为了安全起见，进行分类讨论if (ps->head->next == NULL){free(ps->head);//注意free释放的是该指针指向的空间，而不是释掉该指针ps->head = ps->tail = NULL;}else{QNode* next = ps->head->next;free(ps->head);ps->head = next;}//出队列，元素数量-1ps->size--;
}

🌕（五）、取队头元素

操作很简单，只需返回head结点的data域；

但要注意，首先要检查队列是否为空：

//取队头
QDatatype QueueFront(Que* ps)
{assert(ps);//检查队列为不为空assert(!QueueEmpty(ps));//返回首结点的data域return ps->head->data;
}

🌕（六）、取队尾元素

操作和（五）类似：

//取队尾
QDatatype QueueBack(Que* ps)
{assert(ps);//检查队列为不为空assert(!QueueEmpty(ps));//返回尾结点的data域return ps->tail->data;
}

🌕（七）、判空

规则：

队列为空返回真；

队列不为空返回假；

我们用一个表达式的逻辑值来实现，如下：

//判空
bool QueueEmpty(Que* ps)
{assert(ps);//为空返回真，不为空返回假return (ps->head == NULL);
}

🌕（八）、获取队列元素个数

操作很简单，直接返回size即可：

//获取队列元素个数
int QueueSize(Que* ps)
{assert(ps);return ps->size;
}

🌕（九）、销毁

与单链表的销毁类似，一个结点一个结点的销毁；

先用临时指针cur指向head，再用临时指针next保存cur的下一个结点，再释放当前结点cur，然后cur重定位到下一个结点，直至cur为NULL；

//销毁
void QueueDestroy(Que* ps)
{assert(ps);QNode* cur = ps->head;//先保存下一个结点，在释放当前结点，在重定位while (cur){QNode* Qnext = cur->next;free(cur);cur = Qnext;}ps->head = ps->tail = NULL;ps->size = 0;
}

🌕（十）、遍历

与栈类似的，队列遍历的时候也不用封装成函数，而是用循环，边遍历边出队，遍历完后，队列为空，这与其后面使用场景有着密切联系；

void Queuetest1()
{Que ps;Queueinit(&ps);QueuePush(&ps, 1);QueuePush(&ps, 2);QueuePush(&ps, 3);QueuePush(&ps, 4);QueuePush(&ps, 5);//遍历while (!QueueEmpty(&ps)){//当前数据是整形，所以占位符用%dprintf("%d ", QueueFront(&ps));QueuePop(&ps);}printf("\n");QueueDestroy(&ps);
}

先进先出，符合其特征；

🍁、队列实现源代码

🌕（一）、main.c

#include"Queue.h"void Queuetest1()
{Que ps;Queueinit(&ps);QueuePush(&ps, 1);QueuePush(&ps, 2);QueuePush(&ps, 3);QueuePush(&ps, 4);QueuePush(&ps, 5);//遍历while (!QueueEmpty(&ps)){//当前数据是整形，所以占位符用%dprintf("%d ", QueueFront(&ps));QueuePop(&ps);}printf("\n");QueueDestroy(&ps);
}int main()
{Queuetest1();return 0;
}

🌕（二）、Queue.c

#include"Queue.h"//初始化
void Queueinit(Que* ps)
{assert(ps);ps->head = ps->tail = NULL;ps->size = 0;
}//销毁
void QueueDestroy(Que* ps)
{assert(ps);QNode* cur = ps->head;//先保存下一个结点，在释放当前结点，在重定位while (cur){QNode* Qnext = cur->next;free(cur);cur = Qnext;}ps->head = ps->tail = NULL;ps->size = 0;
}//入队
void QueuePush(Que* ps, QDatatype x)
{assert(ps);//创建一个新结点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");return;}//因为是在尾结点入队，所以入队之后结点next域要置空newnode->data = x;newnode->next = NULL;//第一次插入是结构体指针之间的赋值,之后才是结构体成员的赋值，所以要分情况//记住tail指针始终指向尾结点，所以入队之后要对tail指针重定位if (ps->tail == NULL){ps->head = ps->tail = newnode;}else{ps->tail->next = newnode;ps->tail = newnode;}//入队后元素数量+1ps->size++;
}//出队
void QueuePop(Que* ps)
{assert(ps);//检查队列是否为空，若为空则assert函数报错提示assert(!QueueEmpty(ps));//队列不为空，进行尾删//当对列只剩下一个元素时,要注意head和tail指针都要指向NULL，所以为了安全起见，进行分类讨论if (ps->head->next == NULL){free(ps->head);//注意free释放的是该指针指向的空间，而不是释掉该指针ps->head = ps->tail = NULL;}else{QNode* next = ps->head->next;free(ps->head);ps->head = next;}//出队列，元素数量-1ps->size--;
}//取队头
QDatatype QueueFront(Que* ps)
{assert(ps);//检查队列为不为空assert(!QueueEmpty(ps));//返回首结点的data域return ps->head->data;
}//取队尾
QDatatype QueueBack(Que* ps)
{assert(ps);//检查队列为不为空assert(!QueueEmpty(ps));//返回尾结点的data域return ps->tail->data;
}//判空
bool QueueEmpty(Que* ps)
{assert(ps);//为空返回真，不为空返回假return (ps->head == NULL);
}//获取队列元素个数
int QueueSize(Que* ps)
{assert(ps);return ps->size;
}

🌕（三）、Queue.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>typedef int QDatatype;
typedef struct QueueNode
{struct QueueNode* next;QDatatype data;
}QNode;typedef struct Queue
{QNode* head;//头指针，指向首结点QNode* tail;//尾指针，指向为结点int size;//记录队列长度
}Que;//初始化
void Queueinit(Que* ps);//销毁
void QueueDestroy(Que* ps);//入队
void QueuePush(Que* ps,QDatatype x);//出队
void QueuePop(Que *ps);//取队头
QDatatype QueueFront(Que* ps);//取队尾
QDatatype QueueBack(Que* ps);//判空
bool QueueEmpty(Que* ps);//获取队列元素个数
int QueueSize(Que* ps);

本次知识到此结束，希望对你有所帮助