今天学习数据结构中另一种特殊的线性表——队列。 我们平时在医院、银行等地方办理业务时,先排队在抽号机进行抽号,服务窗口会根据号码的顺序叫号,再为我们进行业务办理。 其中抽号机的工作原理就类似于是队列,先进入的数据先出(先抽号的人先服务),遵循了先来后到,确保了公平性。
只允许在一端进行插入数据的操作,在另一端进行删除数据的操作的特殊线性表。 队列中的元素遵循先进先出(FIFO)的原则。
对队列的操作: 1.入队列:在插入数据的一端插入数据(队尾); 2.出队列:在删除队列的一端删除数据(队头)。
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些。因为如果使用数组的结构,出队列在数组上进行头删数据,效率会比较低。
实际中我们有时还会使用一种队列叫循环队列。如操作系统中的生产者消费者模型就会使用循环队列。环形队列可以使用数组实现,也可以使用循环链表实现。
typedef int QueueNodeType;
typedef struct QueueNode//队列节点
{
QueueNodeType node;//存储数据的节点
struct QueueNode* next;//指向下一个节点
}QueueNode;
typedef struct Queue//队列
{
QueueNode* head;//指向头结点
QueueNode* tail;//指向尾节点
int size;//队列中的元素个数
}Queue;
//队列的初始化
void QueueInit(Queue* ps);
//出队
void QueuePop(Queue* ps);
//入队
void QueuePush(Queue* ps, QueueNodeType x);
//销毁队列
void QueueDistory(Queue* ps);
//队头元素
QueueNodeType QueueFront(Queue* ps);
//判断队列为空(空就返回1,非空就返回0)
bool QueueEmpty(Queue* ps);
void QueueInit(Queue* ps)
{
assert(ps);
ps->head = ps->tail = NULL;
ps->size = 0;
}
QueueNode* QueueBuyNode(QueueNodeType x)
{
QueueNode* t = (QueueNode*)malloc(sizeof(QueueNode));
if (t == NULL)
{
perror("malloc fail");
}
t->node = x;
t->next = NULL;
return t;
}
(空就返回1,非空就返回0)
bool QueueEmpty(Queue* ps)
{
return ps -> tail == NULL &&ps -> head == NULL;
}
QueueNodeType QueueFront(Queue* ps)
{
assert(ps);
assert(!QueueEmpty(ps));
return ps->head->node;
}
void QueuePush(Queue* ps, QueueNodeType x)
{
QueueNode* newnode = QueueBuyNode(x);
if (ps->tail == NULL)
{
ps->head = ps->tail = newnode;
}
else
{
ps->tail->next = newnode;
ps->tail = newnode;
}
ps->size++;
}
void QueuePop(Queue* ps)
{
assert(ps);
assert(!QueueEmpty(ps));
if (ps->head->next == NULL)
{
free(ps->head);
ps->head = ps->tail = NULL;
}
else
{
QueueNode* temp = ps->head;
ps->head = ps->head->next;
free(temp);
temp = NULL;
}
ps->size--;
}
void QueueDistory(Queue* ps)
{
assert(ps);
QueueNode* cur = ps->head;
while (cur)
{
QueueNode* del = cur;
cur = cur->next;
free(del);
}
ps->head = ps->tail = NULL;
}
使用某些库函数时要记得包含它对应的头文件,我也给大家整理了本次所需要的头文件。
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
测试队列的相应功能,以下是我使用的主函数,大家也可以根据需要进行修改,测试其他的测试用例。
void test()
{
Queue ps;
QueueInit(&ps);//初始化队列
QueuePush(&ps, 1);
QueuePush(&ps, 2);
QueuePush(&ps, 13);
QueuePush(&ps, 14);
//打印队列元素(遍历一边队列的元素,实质上就是出队列)
while (!QueueEmpty(&ps))
{
printf("%d ", QueueFront(&ps));
QueuePop(&ps);
}
QueueDistory(&ps);//销毁队列
}
int main()
{
test();
return 0;
}
到这篇文章,我们已经了解了很多栈和队列的相关知识,所以我在这里同大家分享一些与栈和队列有关的概念性的选择题,以便让大家对这些知识掌握更加熟练。 大家可以先自己尝试着做一下这些选择题,我也会将它们的答案公布在下一篇博客的评论区里。
以上就是今天要讲的内容,本文介绍了数据结构中的队列。对队列的概念以及它的具体实现都进行了讲解。大家感兴趣的也可以根据作者所写思路自行实现。 本文作者目前也是正在学习数据结构的知识,如果文章中的内容有错误或者不严谨的部分,欢迎大家在评论区指出也欢迎大家在评论区提问、交流。 最后,如果本篇文章对你有所启发的话,也希望可以多多支持作者,谢谢大家!