数据结构 —— 队列（超详细图解 & 接口函数实现）

系列文章目录

数据结构 —— 顺序表
数据结构 —— 单链表
数据结构 —— 双向链表
数据结构 —— 栈
数据结构 —— 队列

文章目录

前言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一种十分优秀的解决实际问题的模板，是先进思想的结晶。博主将会用代码结合大量图解，对数据结构进行深度剖析，以便大家更好的学习数据结构的思想。

一、示例问题：排队叫号

1.排队叫号流程

例如当我们到银行办理业务时，我们首先需要取号，银行按照号码顺序叫号，被叫到号的人去办理业务。

2.逻辑示意图

先取号的，先被叫号

3.队列的引入

队列的引入：先进先出，后进后出的数据结构

二、队列的概念

1.定义

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

• 入队列：进行插入操作的一端称为队尾
• 出队列：进行删除操作的一端称为队头

2.结构

队列的结构类型：由于只需要考虑头删和尾插，所以单链表的结构更适合队列

//类型typedefint QDataType;// 链式结构：表示队列typedefstructQueueNode{
    QDataType data;structQueueNode*next;} QueueNode;// 队列的结构typedefstructQueue{
    QueueNode *head;
    QueueNode *tail;} Queue;

3.存储

存储：用动态开辟的单链表来存储

三、队列的接口函数

1.初始化队列

对队列的内容进行初始设置

// 初始化队列voidQueueInit(Queue *que){assert(que);
    que->head = que->tail =NULL;}

2.空队列

判断是否为空队列

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue *que){assert(que);return que->head ==NULL&& que->tail ==NULL;}

3.入队（尾插）

队列的插入操作

// 队尾入队voidQueuePush(Queue *que, QDataType data){assert(que);
    QueueNode *newNode =(QueueNode *)malloc(sizeof(QueueNode));if(newNode ==NULL){perror("malloc fail:");}else{
        newNode->next =NULL;
        newNode->data = data;}if(que->head ==NULL){
        que->head = que->tail = newNode;}else{
        que->tail->next = newNode;
        que->tail = que->tail->next;}}

4.出队（头删）

队列的删除操作

// 队头出队voidQueuePop(Queue *que){assert(que);assert(!QueueEmpty(que));if(que->head->next ==NULL){free(que->head);
        que->head = que->tail =NULL;}else{
        QueueNode *next = que->head->next;free(que->head);
        que->head = next;}}

5.头部元素

获取队列头部元素

// 获取队列头部元素
QDataType QueueFront(Queue *que){assert(que);assert(!QueueEmpty(que));return que->head->data;}

6.尾部元素

获取队列尾部元素

// 获取队列队尾元素
QDataType QueueBack(Queue *que){assert(que);assert(!QueueEmpty(que));return que->tail->data;}

7.队列的元素个数

获取队列中有效元素个数

// 获取队列中有效元素个数intQueueSize(Queue *que){assert(que);
    QueueNode *curr = que->head;int size =0;while(curr){
        curr = curr->next;
        size++;}return size;}

8.销毁队列

释放栈申请的空间

// 销毁队列voidQueueDestroy(Queue *que){assert(que);
    QueueNode *curr = que->head;while(curr){
        QueueNode *del = curr;
        curr = curr->next;free(del);}
    que->head = que->tail =NULL;}

四、总结

队列是解决实际问题时极其常用的一种数据结构，是非常重要的解决问题的方式。队列的各种接口的复现，有利于更好的学习数据结构的思想，有利于开阔视野，学习前辈的智慧结晶。对我们后续解决实际问题也会有很大帮助。