一. 队列的基本介绍
1. 基本概念
队列是基本数据结构的一种 它符合先进先出的原则
我们来看图
大概就是这样子的一种情况
我们想想看 应该用数组还是链表来实现这个结构方便一点呢
我想同学们心里现在肯定已经有了答案了
肯定不是数组
为什么呢？
因为我们如果用数组头作为队头的话 每次删数据就要往前移动很多组其他的数据
这里有同学肯定会有这样子的疑问？
不移动可不可行呢？
当然不可以 ！
队列这种数据结构已经规定死了就是头出 尾进
所以说我们使用链表来实现这个数据结构
2. 代码表示
typedef int QDateType; typedef struct QueueNode { struct QueueNode* next; QDateType date; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue;
仔细看
我们这里使用QueueNode来表示储存数据的一个个节点
使用Queue来表示两个指针 头和尾
可以看图理解快一点
二. 接口函数的实现
1. 队列初始化
//初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; }
队列初始化实际上就是将队列的两个指针置空
我们来看看效果
这里没有传二级指针进去到底能不能将一级指针置空
成功将两个指针置空了
这是为什么呢？
因为我们的头和尾指针实际上是储存在一个结构体里面的
当我们将结构体的地址传进去的时候 结构体指针能够访问到结构体内部的内容（这两个指针）并且可以修改它们
2. 插入数据
这里插入数据我们要考虑两种情况
1.如果head和tail指针指向NULL，就需要将newnode赋给head和tail指针
2.head和tail不指向NULL，就将newnode的地址赋给tail->next，再将tail移到newnode即可
代码如下：
//队进 void QueuePush(Queue* pq, QDateType x) { assert(pq); //开辟新节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } //赋值 newnode->next = NULL; newnode->date = x; //判断是否为空 if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } //个数要++ pq->size++; }
看看效果怎么样
可以运行
3. 删除数据
这里我们要注意的是
由于队列结构的特殊性
我们在打印数据的时候必须要删除数据
所以我们先写删除数据的接口函数
代码表示如下
void QueuePop(Queue* pq) { assert(pq); assert(pq->head!=NULL); //只有一个节点 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { //保存下一位 QNode* next = pq->head->next; free(pq->head); pq->head = next;//迭代 } //个数要-- pq->size--; }
看看效果：
可以运行
4. 摧毁队列
直接看代码：
void QueueDestroy(Queue* pq) { assert(pq); //两个结构体依次销毁 先销毁QNode QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } //再置空Queue pq->head = pq->tail = NULL; pq->size = 0; }
注意：两个结构体要依次销毁，类似（套娃）
我们来看看效果
5. 判断为空
这个也很简单和栈差不多
这里就直接给代码了
//判断为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; }
6.返回大小
这个也很简单，因为我们在Queue结构体中已经定义过size了，我们直接返回就可以
直接看代码：
//大小 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
7. 返回头数据
这个很简单 返回head的值就可以了
注意断言的使用
//对头 QDateType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->date; }
8.返回尾数据
一样的简单
也要注意断言的使用
//队尾 QDateType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->date; }
以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言
