文章目录队列非循环队列队列的顺序实现循环队列的“判空”与“判满”代码实现(基于“牺牲一个单元”)结构定义与初始化入队出队查找获取队头元素清空与销毁队列队列是只允许在一端插入、另一端删除的操作受限的线性表遵循FIFO先进先出(先进入队列的元素先出队。队尾rear入队插入元素允许插入的一端队尾元素队头front出队删除元素允许删除的一段队头元素非循环队列假溢出数组前面有空位置但rear走到数组末尾后无法继续入队就会存在空间浪费。对策使用循环队列。将数组逻辑上视为首尾相接的环。当rear或front到达MaxSize-1时再前进一步就回到0。这通过取模运算%实现。队列的顺序实现顺序队列是利用连续的内存空间静态数组和两个整型指针队头front队尾rear来实现先进先出 FIFO逻辑的存储结构。front指向队头元素所在位置或前一个位置标准严蔚敏版指向队头。rear指向队尾元素的下一个位置即待插入位置。循环队列的“判空”与“判满”在循环队列中rear front既可能是“空”也可能是“满”因为循环。为了区分严蔚敏/王道教材采用最经典的“牺牲一个存储单元”的约定。核心记忆在“牺牲一个单元”的约定下数组永远有一个空位不用。所以MaxSize10的队列最多只能存9个元素。方法方法一牺牲一个单元标准方法二增设 size 变量方法三增设 tag 变量核心思想数组中永远空出一个位置不用让队满时front在rear的前一个位置。用一个变量size实时记录当前队列中的元素个数。用一个变量tag记录上一次操作是“入队”还是“出队”。结构体定义int data[MaxSize];int front, rear;int data[MaxSize];int front, rear;int size;int data[MaxSize];int front, rear;int tag;初始化front rear 0;front rear 0;size 0;front rear 0;tag 0;队空条件front rearsize 0front rear tag 0队满条件(rear 1) % MaxSize frontsize MaxSizefront rear tag 1入队操作data[rear] e;rear (rear1)%MaxSize;data[rear] e;rear (rear1)%MaxSize;size;data[rear] e;rear (rear1)%MaxSize;tag 1;// 标记刚插入了出队操作e data[front];front (front1)%MaxSize;e data[front];front (front1)%MaxSize;size--;e data[front];front (front1)%MaxSize;tag 0;// 标记刚删除了获取长度(rear - front MaxSize) % MaxSizesize直接读取O(1)(rear - front MaxSize) % MaxSize最多存多少元素MaxSize - 1牺牲了一个位置MaxSize全用满MaxSize全用满优缺点无需额外变量省内存。缺点浪费一个空间判断满的公式易记错。逻辑清晰不易出错。缺点多用了 4 个字节的内存。不浪费空间也不浪费内存。缺点判空/判满必须结合 frontrear推荐推荐严蔚敏标准了解即可选择秒杀了解代码实现(基于“牺牲一个单元”)结构定义与初始化#includestdio.h#includestdbool.h#defineMaxSize10typedefstruct{intdata[MaxSize];// 使用 静态数组 存放队列元素intfront;// 队头指针指向队头元素intrear;// 队尾指针指向队尾元素的下一个位置待插入位置}SqQueue;// 初始化 创建空队列voidInitQueue(SqQueueQ){Q.front0;Q.rear0;// front rear 代表空// 或者写成一行代码 Q.front Q.rear 0;}// 判空boolQueueEmpty(SqQueue Q){returnQ.frontQ.rear;// 当 队头指针和队尾指针相等时为 空队列相当于初始化时}// 判满 核心公式必背boolQueueFull(SqQueue Q){return(Q.rear1)%MaxSizeQ.front;// 因为 rear 指向队尾元素的下一个位置 所以这里 rear 最多指向 9// 但为了判空与判满不都是 Q.front Q.rear 所以选择牺牲最后一个元素// 则这里 rear1 为 10在取模 最大 10 则为 0 // 这时 rear 与 front 相等就说明队列已满// 运用 模运算 将存储空间在逻辑上变成了“环状 ”}// 获取队列长度 选择题秒杀公式intQueueLength(SqQueue Q){return(Q.rear-Q.frontMaxSize)%MaxSize;}入队// 入队 在队尾插入元素 e (想象排队只能从队尾来人排队不能从头或者从中间开始插队没礼貌)boolEnQueue(SqQueueQ,inte){// 1. 先判断是否已满if((Q.rear1)%MaxSizeQ.front)returnfalse;// 2. 将元素放入当前 rear 指向的空位Q.data[Q.rear]e;// 3. rear 指针循环后移一位必须取模Q.rear(Q.rear1)%MaxSize;returntrue;}出队// 出队 删除队头元素并通过 e 带回其值// 想想排队:假设来排队的人都必须要在这里买东西不买到绝不离开// 那么在最前面的人买完东西之后就离开即在队头离开删除boolDeQueue(SqQueueQ,inte){// 1. 先判空if(Q.frontQ.rear)returnfalse;// 2. 取出队头元素eQ.data[Q.front];// 3. front 指针循环后移一位必须取模Q.front(Q.front1)%MaxSize;returntrue;}查找获取队头元素// 查队头 只读操作不删除元素boolGetHead(SqQueue Q,inte){// 先判空if(Q.frontQ.rear)returnfalse;// 取出队头元素eQ.data[Q.front];// front 不动returntrue;}对比出队操作清空与销毁清空逻辑清空只需将front和rear置为相等即可即Q.front Q.rear 0;。物理数据不用清逻辑上被指针屏蔽。销毁释放内存由于顺序队列是静态数组栈区或全局区不需要free。如果队列结构体是通过malloc动态创建的则free(Q)即可。顺序队列利用一组地址连续的存储单元数组存放队列元素并附设front和rear两个整型指针分别指示队头和队尾。为了解决‘假溢出’问题通常采用循环队列通过取模运算将数组视为环形结构。在标准约定牺牲一个存储单元下队空条件为rear front队满条件为(rear 1) % MaxSize front入队和出队的时间复杂度均为O(1)。