一. 队列的基本介绍
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;
}以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言
