您现在的位置是:首页 >技术交流 >【数据结构】队列详解网站首页技术交流
【数据结构】队列详解
☃️个人主页:fighting小泽
?作者简介:目前正在学习C语言和数据结构
?博客专栏:数据结构
?️欢迎关注:评论??点赞??留言??
文章目录
1.队列
1.1队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)的特性。
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
比如说我们要将1、2、3、4这几个数进行入队列和出队列的操作
- 我们发现入队列的顺序是1、2、3、4,出队列的顺序也是1、2、3、4。
- 要是我们先入1、2两个数据,并让它们出队列,然后再入3、4两个数据,再让它们出队列,我们发现出队列的顺序还是1、2、3、4。
- 所以队列的特性就是先入先出,并且顺序不会因为出数据而改变。
那么队列在我们生活中有什么用处呢?
举个例子:我们平时去餐厅买饭的时候会先排队,点完餐之后老板会给你一个号,等叫到你的号时便可以去领自己的饭菜了。所以通过队列我们就可以实现一个抽号机,先来的人会先领到号,而且凭号领饭,不会被别人插队。这是不是队列的先入先出性质在我们生活中的应用。
1.2队列的实现
队列也可以通过数组或者链表来实现,但是哪种方式更好呢?
- 我们想一想,队列每次都是在队尾入数据,在队头出数据。是不是会经常用到尾插和头删操作。
- 我们知道数组进行头插操作需要移动整个数组的元素,效率很低。虽然数组尾插很方便,但总体还是弊大于利的。所以我们用链表实现会比较好一点。
我们知道链表进行头插操作很容易,但是进行尾插操作却需要遍历一遍链表,那有没有好的解决办法呢?
- 有的!我们可以专门用一个指针记录下尾节点的位置,然后在尾节点后面进行尾插操作,再改变尾节点的位置即可。
1.2队列的结构
由于队列是由链表构成的,所以链表的每个节点存储了一个数据和指向下一个链表的指针。
注意:这里传的都是结构体的地址,是形参,最好用assert断言一下。不可以改变结构体,但是可以改变结构体的元素。
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
由于队列要进行尾插头删操作,所以我们可以再定义一个结构体来保存队列的头指针和尾指针。队列的大小最好也保存一下。因为我们想要进行入队列出队列操作时,只需要通过队列的头指针和尾指针就可以进行尾插头删操作。
头插不用二级指针的方式:
- 1.用返回值
- 2.将指针放在结构体中
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
很多人可能疑惑为什么要定义两个结构体。注意结构体的定义是根据我们的需求来定的,不要被固定的思维限制住了。
Queue.h
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
void QueueInit(Queue* pq);//初始化队列
void QueueDestroy(Queue* pq);//销毁队列
void QueuePush(Queue* pq, QDataType x);//入队列
void QueuePop(Queue* pq);//出队列
QDataType QueueFront(Queue* pq);//获得队列的第一个元素
QDataType QueueBack(Queue* pq);//获得队列的最后一个元素
int QSize(Queue* pq);//获得队列的元素个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
Queue.c
1.初始化和销毁队列
队列初始化的时候我们可以先给它开辟一些空间,也可以等使用时再开辟,这里我就不开辟啦。初始化就把它的指针置空,把大小置为0就行。
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
队列的销毁跟链表相同,每次记录下头节点下一个节点的位置,再把头节点释放掉,直到释放完为止。
void QueueDestroy(Queue* pq)
{
assert(pq);
while (pq->phead)
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
2.入队列操作
入队列要分为两种情况
- 若队列为空,我们要把尾指针和头指针都指向要插入的新节点
- 若队列不为空,我们直接通过尾指针进行尾插就行了。
- 注意入队列时size要+1
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
newnode->data = x;
newnode->next = NULL;
if (newnode == NULL)
{
perror("malloc fail
");
return;
}
else
{
if (pq->phead == NULL)
{
assert(pq->ptail == NULL);//都为空
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
}
3.出队列操作
同样,出队列也要分为多种情况:
- 若队列为空,我们就不能进行出队列操作了,我们可以写一个QueueEmpty函数来判断队列是否为空
- 若队列有多个元素,我们只需要将头指针指向下一个节点,然后释放掉原来的头节点即可。
- 若队列只有一个元素,我们要是还按第二种方式的话,头节点就指向了NULL,队列就没有元素了,而尾节点却还指向原来的节点。这时尾节点是不是就成为了一个尾指针了,所以要把它给置空,
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
else
{
QNode* tmp = pq->phead->next;
free(pq->phead);
pq->phead = tmp;
pq->size--;
}
}
4.判断队列是否为空和获得队列元素个数
判断队列为空,只需要看它的大小是不是为0就行,或者判断队列的头指针和尾指针是不是都是空指针。
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
获得队列的元素个数,很简单,只需要返回队列的size就行
int QSize(Queue* pq)
{
assert(pq);
return pq->size;
}
5.获得队列头、尾元素
注意元素队列空我们就不能获得元素了,所以要assert判断一下。
然后直接返回头尾指针指向节点存储的data数据即可。
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
5.结尾
这些就是我给大家分享的关于队列的知识啦,是不是很简单啊。希望我们都能有所收获!
先赞后看,养成习惯!!^ _ ^
码字不易,大家的支持就是我坚持下去的动力,点赞后不要忘了关注我哦!
如有错误,还请您批评改正(。ì _ í。)