栈和队列（C语言底层实现环形队列）

链表队列就像是“排队买奶茶”队伍长度不固定人多我就排长一点人少我就排短一点灵活多变适合高级业务逻辑。环形队列就像是“机场的行李转盘”或者旋转门转盘大小是固定的不需要临时扩建。放行李的工人在后面放入队旅客在前面拿出队。只要拿的速度跟得上放的速度这个固定大小的转盘就能无限地处理几万件行李1.定义环形队列的结构体typedef struct CircularQueue { int* data;//待会用malloc获取一块连续的数字空间 int capacity;//记录这个队列的总容量 int front;//队头游标排在最前面的数据 int rear;//队尾游标永远指向下一个空位 }CircularQueue;2.初始化环形队列我们要体现环形队列最核心的“心法”为了区分“空”和“满”必须故意浪费一个座位void queueInit(CircularQueue* q, int maxSize) { //【核心心法】你想装 maxSize 个人我底层必须开辟 maxSize 1 个位置 //那个多出来的位置就是为了防止 front 追上 rear 时分不清是空还是满。 q-capacity maxSize 1; //此时malloc一块空间之后不会再用malloc q-data (int*)malloc(sizeof(int) * q-capacity); if (q-data NULL) { perror(malloc failed); return; } q-front 0; q-rear 0; printf(环形队列初始化成功真实容量为%d可装载人数为%d\n, q-capacity, maxSize); }为什么capacity maxSize 1假设顾客说“我要一个能装 4 个人的队列。”如果我们底层只申请 4 个位置的数组。当 4 个人全站满时rear绕了一圈回到了起点刚好和front重叠rear front。但是当队列空无一人时rear和front也是重叠的rear front。这样一来程序就彻底抓瞎了所以我们极其狡猾地向系统申请5个位置capacity 5我们依然只允许最多站 4 个人。这样当站满 4 个人时rear和front之间永远会隔着一个空位它们永远不会重叠只有当真正的空无一人时它们才会重叠。这就是计算机科学里极其经典的“牺牲空间换取逻辑清晰”的做法。3.判空函数bool queueIsEmpty(CircularQueue* q) { //当front和rear重合即一个人也没有为空 if (q-front q-rear) { return true; } else { return false; } }4.判满函数bool queueIsFull(CircularQueue* q) { //【核心心法】让rear在脑海里往前“试探性”地走一步。 //如果往前走一步刚好撞上了front说明转盘只剩最后那个“必须浪费的空位”了队列已满 int nextRear (q-rear 1) % q-capacity; if (nextRear q-front) { return true; } else { return false; } }为什么要进行取模运算假设我们申请了一个capacity 5的数组下标是 0, 1, 2, 3, 4。 我们的目标是让游标从 0 走到 4 之后下一步瞬间穿越回 0正常情况没走到头假设现在rear 2。往前走一步(2 1) % 53 除以 5商是 0余数是3。所以下一步去了下标 3。非常正常。走到尽头的情况见证奇迹的时刻假设现在rear 4已经站在物理数组的最后一个位置了。往下走一步(4 1) % 55 除以 5商是 1余数是0看它完美地绕回了起点 0物理上是一条直线的数组在逻辑上被这个%号硬生生“掰弯”成了一个圆环所以在rear距离front还有一格距离的时候我们就必须强行拉响警报“满了满了不能再放了rear指向那个是即将放入人的那个位置而非最后一个人5.入列函数把人放进空位然后让游标往前挪一步。void queuePush(CircularQueue* q, int value) { if (queueIsFull(q)) { printf(队列已满入列失败\n); return; } //把value装进下标为q-value的位置 q-data[q-rear] value; //【核心】工人 (rear) 往前走一步寻找下一个空位 //如果走到了数组的尽头% 取模运算会把他瞬间传送回下标 0 q-rear (q-rear 1) % q-capacity; printf(%d入队成功\n, value); }6.出列函数出队的逻辑几乎和入队是对称的只是操作的游标换成了frontint queuePop(CircularQueue* q) { if (queueIsEmpty(q)) { printf(出列失败队列为空\n); return -1; } //拿到即将删除的那个值 int popValue q-data[q-front]; //核心旅客(front) 拿完行李往前走一步准备接下一个。 //同样走到要 % 传送回起点。 q-front (q-front 1) % q-capacity; printf(%d出列成功\n, popValue); return popValue; }7.销毁队列void queueDestroy(CircularQueue* q) { if (q-data ! NULL) { free(q-data); q-data NULL; } q-front 0; q-rear 0; q-capacity 0; printf(队列成功被销毁\n); }我们一开始用malloc申请了那个巨大的底层数组关机的时候当然要还给操作系统。8.不同文件代码的整合CircularQueue.h#pragma once #include stdio.h #include stdbool.h #include stdlib.h typedef struct CircularQueue { int* data;//待会用malloc获取一块连续的数字空间 int capacity;//记录这个队列的总容量 int front;//队头游标排在最前面的数据 int rear;//队尾游标永远指向下一个空位 }CircularQueue; //初始化环形队列 void queueInit(CircularQueue* q, int maxSize); //判空函数 bool queueIsEmpty(CircularQueue* q); //判满函数 bool queueIsFull(CircularQueue* q); //入列函数 void queuePush(CircularQueue* q, int value); //出列函数 int queuePop(CircularQueue* q); //销毁队列 void queueDestroy(CircularQueue* q);CircularQueue.c#define _CRT_SECURE_NO_WARNINGS 1 #include CircularQueue.h void queueInit(CircularQueue* q, int maxSize) { //【核心心法】你想装 maxSize 个人我底层必须开辟 maxSize 1 个位置 //那个多出来的位置就是为了防止 front 追上 rear 时分不清是空还是满。 q-capacity maxSize 1; //此时malloc一块空间之后不会再用malloc q-data (int*)malloc(sizeof(int) * q-capacity); if (q-data NULL) { perror(malloc failed); return; } q-front 0; q-rear 0; printf(环形队列初始化成功真实容量为%d可装载人数为%d\n, q-capacity, maxSize); } bool queueIsEmpty(CircularQueue* q) { //当front和rear重合即一个人也没有为空 if (q-front q-rear) { return true; } else { return false; } } bool queueIsFull(CircularQueue* q) { //【核心心法】让rear在脑海里往前“试探性”地走一步。 //如果往前走一步刚好撞上了front说明转盘只剩最后那个“必须浪费的空位”了队列已满 int nextRear (q-rear 1) % q-capacity; if (nextRear q-front) { return true; } else { return false; } } void queuePush(CircularQueue* q, int value) { if (queueIsFull(q)) { printf(队列已满入列失败\n); return; } //把value装进下标为q-value的位置 q-data[q-rear] value; //【核心】工人 (rear) 往前走一步寻找下一个空位 //如果走到了数组的尽头% 取模运算会把他瞬间传送回下标 0 q-rear (q-rear 1) % q-capacity; printf(%d入队成功\n, value); } int queuePop(CircularQueue* q) { if (queueIsEmpty(q)) { printf(出列失败队列为空\n); return -1; } //拿到即将删除的那个值 int popValue q-data[q-front]; //核心旅客(front) 拿完行李往前走一步准备接下一个。 //同样走到要 % 传送回起点。 q-front (q-front 1) % q-capacity; printf(%d出列成功\n, popValue); return popValue; } void queueDestroy(CircularQueue* q) { if (q-data ! NULL) { free(q-data); q-data NULL; } q-front 0; q-rear 0; q-capacity 0; printf(队列成功被销毁\n); }test.c#define _CRT_SECURE_NO_WARNINGS 1 #include CircularQueue.h int main() { CircularQueue MyQueue; queueInit(MyQueue, 5); queuePush(MyQueue, 1); queuePush(MyQueue, 2); queuePush(MyQueue, 3); queuePush(MyQueue, 4); queuePush(MyQueue, 5); queuePush(MyQueue, 1); /*queuePop(MyQueue); queuePop(MyQueue); queuePop(MyQueue); queuePop(MyQueue); queuePop(MyQueue); queuePop(MyQueue);*/ queueDestroy(MyQueue); return 0; }