从栈到队列：数据结构基础全解析

一、先解答 Day6 思考题问为什么栈可以实现数字 / 字符串逆序输出答因为栈是后进先出LIFO。把内容依次压入栈再依次弹出顺序自然就反过来了。二、今天学习目标理解队列先进先出 FIFO普通队列与循环队列数组实现循环队列完整代码入队、出队、判空、判满三、什么是队列大白话队列就是排队先来先服务后来排后面。特点先进先出FIFOFirst In First Out一端进队尾 rear一端出队头 front不能插队不能从中间删生活例子食堂打饭排队打印机任务队列消息队列、网络数据包四、为什么要用循环队列普通数组队列会出现 “假溢出”队尾到数组末尾了但前面空位置很多。循环队列把数组看成一个环队尾到末尾后回到开头继续用。用(rear1) % maxSize判断是否满。五、循环队列完整代码可直接运行#include stdio.h #define MAX 5 // 循环队列结构 typedef struct { int data[MAX]; int front; // 队头 int rear; // 队尾 } Queue; // 初始化 void initQueue(Queue *q) { q-front 0; q-rear 0; } // 判断空 int isEmpty(Queue *q) { return q-front q-rear; } // 判断满牺牲一个位置区分空与满 int isFull(Queue *q) { return (q-rear 1) % MAX q-front; } // 入队 int enQueue(Queue *q, int val) { if (isFull(q)) { printf(队列满了\n); return 0; } q-data[q-rear] val; q-rear (q-rear 1) % MAX; return 1; } // 出队 int deQueue(Queue *q) { if (isEmpty(q)) { printf(队列空\n); return -1; } int val q-data[q-front]; q-front (q-front 1) % MAX; return val; } // 打印队列 void printQueue(Queue *q) { if (isEmpty(q)) { printf(队列为空\n); return; } int i q-front; while (i ! q-rear) { printf(%d , q-data[i]); i (i 1) % MAX; } printf(\n); } // 主函数测试 int main() { Queue q; initQueue(q); enQueue(q, 10); enQueue(q, 20); enQueue(q, 30); enQueue(q, 40); printf(队列内容); printQueue(q); printf(出队%d\n, deQueue(q)); printf(出队%d\n, deQueue(q)); printf(队列内容); printQueue(q); enQueue(q, 50); enQueue(q, 60); printf(入队后); printQueue(q); return 0; }运行结果队列内容10 20 30 40 出队10 出队20 队列内容30 40 入队后30 40 50 60六、栈 vs 队列 对比表格结构特点口诀典型应用栈 Stack后进先出LIFO括号匹配、递归、函数调用、逆序队列 Queue先进先出FIFO排队、打印任务、消息队列、BFS七、今日小练习代码思路用队列模拟 3 个任务排队执行任务 A、任务 B、任务 C依次入队再依次出队模拟 “先来先执行”思路把任务编号入队逐个deQueue就是执行顺序。八、明日预告Day8字符串与朴素模式匹配暴力匹配为后续 KMP 打基础新手最容易上手的字符串算法。