🎬 鸽芷咕:个人主页 🔥 个人专栏:《速学数据结构》 《C语言进阶篇》
⛺️生活的理想,就是为了理想的生活!
🌈hello! 各位宝子们大家好啊,栈区的实现我们前面已经讲了,而栈和队列都是特殊的线性表,今天我们就来看看队列是怎么实现的! ⛳️队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)的特点。 📚本期文章收录在《数据结构&算法》,大家有兴趣可以看看呐! ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝!
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出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
他们指向空就好了。
size
目前也没有数据初始化为零可以了📚 代码演示:
// 初始化队列
void QueueInit(Que* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
入队列就很简单了,每次需要了就去 malloc 一个节点然后尾插到 队列后面就好了。
📚 代码演示:
// 队尾入队列
void QueuePush(Que* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
出队列就简单了,先判断一下队列是否为空。为空就直接返回
free()
掉前一个节点,然后 front
向前走到下一个节点size--
数据不要忘记了📚 代码演示:
void QueuePop(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
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--;
}
由于我们已经定义了一个头指针,所以直接找到 front
里面存放的元素返回就OK了,是不是非常简单。
📚 代码演示:
// 获取队列头部元素
QDataType QueueFront(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
队尾元素可对头是一样的,先判断指针是否为空,和队列是否为空。
📚 代码演示:
// 获取队列队尾元素
QDataType QueueBack(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
大家看到这个是不是觉得就是小卡拉米,一下就搞定了:
📚 代码演示:
// 获取队列中有效元素个数
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;
}
大家想一想什么时候队列尾空呢?是不是只有 front == break 的时候才为空啊!
📚 代码演示:
// 检测队列是否为空,如果为空返回非零false,如果非空返回true
bool QueueEmpty(Que* pq)
{
assert(pq);
return pq->head == NULL;
}
销毁队列就和以前一样了,先把每个节点都用循环销毁了。在把俩个队列指针置空
szie
为0 ,这样就可以销毁队列了📚 代码演示:
void QueueDestroy(Que* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
☁️ 好啦以上就是队列实现的全部过程了,相比较链表来说这些更像是链表的扩展只要链表掌握的好这些都是非常简单的!
看到这里了还不给博主扣个:
⛳️ 点赞
☀️收藏
⭐️ 关注
!
💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要!
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。