队列 先进 先出 很公平 排队打菜一样
有对头 和 对尾 就是对单链表 限制或者只去用部分的函数 就不要其他的功能 来使其 具有独特的 属性和 应用场景
现实 比喻 嘉豪 男娘 等
1 为什么非要包一个结构体？因为队列必须同时记住：头在哪、尾在哪，不然没法快速入队、出队。
<stdlib.h> 精简版作用
1. 动态内存：malloc、free、calloc、realloc
2. 程序退出：exit()
3. 类型转换：atoi 字符串转整数、atof 转小数
4. 随机数：rand、srand
5. 工具函数：abs 求绝对值、qsort 排序
一句话：C语言内存分配、随机数、类型转换、程序退出都靠它。
每一个 Node 就是一个排队的人
val 是这个人带的东西
next 是伸手指着下一个人
将结构体变量 看作大哥 下面有小弟 大哥可以指挥小弟
Queue 是总管，手里拿着两个指针，盯着队伍头和队伍尾。
方便 头删 出队列 对头
尾插 入队列 队尾
2 第一个初始化函数 —— 队列初始化
思路：刚创建一个队列，队伍里一个人都没有所以：
头指针、尾指针 都赋值为 NULL
3 判空函数 思路：
只要 head == NULL，说明队伍没人，就是空队列。
return pq->Head ==NULL; return !pq->Head;z这里是等价的 但推荐第一种只管 表达式的结果就是返回值 很直观4 销毁队列![]()
需要从头开始 来写 一个一个遍历之后 销毁 free
5 入队列
*队列结构体已经把 head 和 tail 包起来了，你传 Queue就能修改 head 和 tail，根本不需要二级指针！**
尾插 时的 直接使用 记录好的Tail![]()
![]()
![]()
6 取数据 对头 队尾![]()
注意 队列判空
7 求 队列中的人数
细节拉满
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
接口函数-
#define _CRT_SECURE_NO_WARNINGS 1 #include "queue.h" //初始化 void QueueInit(Queue* pq) { assert(pq); //pq->val = 0; 对里没人 更不可能有东西呀 pq->Head=pq->Tail = NULL; } // 还有就是销毁 void QueueDestroy(Queue* pq) { assert(pq); Node* cur = pq->Head; while (cur!=NULL) { Node* next = cur->next;//记录下个节点 free(cur);//cur无 cur = next;//狸猫换太子 } pq->Head = pq->Tail = NULL; } // 判空 bool EmptyQueue(Queue* pq) { assert(pq); return pq->Head ==NULL; //return !pq->Head; //return pq->Head !=NULL; //return pq->Head; } // 入队列 尾插 void QueuePush(Queue* pq,QueueDatatype x) { assert(pq); //创建新的节点 Node* newnode = (Node*)malloc(sizeof(Node)); if (newnode == NULL) { perror("malloc error!\n"); return; } newnode->val = x; newnode->next = NULL; //0 节点 if (pq->Head == NULL) { pq->Head = pq->Tail = newnode; } else//至少一节点 尾插 { //Node* Ftail = pq->Head; //while (Ftail->next!=NULL) { // Ftail = Ftail->next; //} //Ftail->next = newnode; //直接使用 pq->Tail->next = newnode; pq->Tail = newnode; } pq->size++;//666 } // 出队 头删除 void QueuePop(Queue* pq) { assert(pq); assert(!EmptyQueue( pq)); Node*del = pq->Head; Node* next = pq->Head->next; free(del); del = NULL; pq->Head = next; if (next == NULL) { pq->Tail = pq->Head = NULL; } pq->size--;///6666 } //取对头 QueueDatatype GotQHead(Queue* pq) { assert(pq); assert(!EmptyQueue(pq)); return pq->Head->val; } // 队尾数 QueueDatatype GotQTail(Queue* pq) { assert(pq); assert(!EmptyQueue(pq)); return pq->Tail->val; } // // 队列中的数据总数 // 每次新增size都加一 o(1) int CountQsize(Queue* pq) { return pq->size; }头文件
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QueueDatatype; //单链表实现 typedef struct Node { QueueDatatype val;//物品 struct Node* next; }Node; //人 typedef struct Queue { Node* Head; int size; Node* Tail; }Queue;
