数据结构-队列（顺序存储、链式存储、双端队列）

队列是算法和开发中最常用的线性结构之一无论是操作系统任务调度、网络请求缓冲、算法滑动窗口还是消息队列中间件底层核心都是队列。一、队列1.1 什么是队列队列是一种受限的线性表严格遵循FIFO先进先出就像我们日常排队先排队的人先办理业务后排队的人后办理。1.2 两大核心端点队头 front负责出队删除元素队尾 rear负责入队插入元素规则只允许尾进、头出不允许中间插入、删除、修改1.3 队列的分类顺序存储队列数组实现普通顺序队列、循环顺序队列链式存储队列链表实现双端队列两端可进可出二、顺序存储队列数组实现顺序队列本质是连续数组存储数据通过 front、rear 下标指针控制出入队所有操作固定围绕两个指针移动实现。2.1 普通顺序队列底层原理front指向当前队头元素下标rear指向下一个可以入队的空位置入队rear 向后移动出队front 向后移动致命缺陷假溢出当数组前面元素出队后前端空间空置但 rear 走到数组末尾系统判定队列已满无法继续入队。有空位却无法存数据就是假溢出因此工程中几乎不用。结构体定义#includestdio.h#defineMaxSize5// 顺序队列结构体数组存储数据双指针typedefstruct{intdata[MaxSize];// 固定大小数组存储队列元素intfront;// 队头指针出队用intrear;// 队尾指针入队用}SqQueue;操作队列初始化核心逻辑队列创建后头尾指针全部归零代表空队列。voidInitQueue(SqQueue*q){q-front0;q-rear0;}判空操作核心逻辑头尾指针重合说明没有任何元素。intisEmpty(SqQueue*q){returnq-frontq-rear;}判满操作核心逻辑队尾指针走到数组最大长度代表数组无剩余空间。intisFull(SqQueue*q){returnq-rearMaxSize;}入队操作尾插核心逻辑先判断队列是否满未满则存入数据再向后移动队尾指针。intEnQueue(SqQueue*q,intx){if(isFull(q))return0;// 队列满入队失败q-data[q-rear]x;// 存入元素rear后移return1;// 入队成功}出队操作头删核心逻辑先判断队列是否空非空则取出队头元素再向后移动队头指针。intDeQueue(SqQueue*q,int*x){if(isEmpty(q))return0;// 队列空出队失败*xq-data[q-front];// 取出队头元素front后移return1;// 出队成功}优缺点总结优点结构简单、内存连续、访问速度快缺点存在假溢出、空间利用率极低、容量固定2.2 循环顺序队列通过逻辑环形数组取模运算解决假溢出问题是工程最常用的顺序队列。主动牺牲一个空间区分队空、队满状态。核心判定公式队空front rear队满(rear 1) % MaxSize front元素个数(rear - front MaxSize) % MaxSize结构体定义#includestdio.h#defineMaxSize5typedefstruct{intdata[MaxSize];intfront;intrear;}SqQueue;操作初始化队列逻辑头尾指针归0初始为空队列。voidInitQueue(SqQueue*q){q-frontq-rear0;}判空intisEmpty(SqQueue*q){returnq-frontq-rear;}判满逻辑利用取模实现环形判定避免首尾指针混淆。intisFull(SqQueue*q){return(q-rear1)%MaxSizeq-front;}循环入队逻辑先存值再通过取模移动 rear 指针到达数组末尾自动跳转头部。intEnQueue(SqQueue*q,intx){if(isFull(q))return0;// 队满直接失败q-data[q-rear]x;// 存入当前队尾位置q-rear(q-rear1)%MaxSize;// 循环后移return1;}循环出队逻辑先取出队头值再取模移动 front 指针实现环形出队。intDeQueue(SqQueue*q,int*x){if(isEmpty(q))return0;// 队空直接失败*xq-data[q-front];// 取出队头元素q-front(q-front1)%MaxSize;// 循环后移return1;}获取队列有效长度逻辑加 MaxSize 避免负数取模保证环形计算准确。intgetLength(SqQueue*q){return(q-rear-q-frontMaxSize)%MaxSize;}优缺点总结优点彻底解决假溢出、内存利用率高、读写速度快缺点容量固定无法动态扩容适合数据量稳定的场景三、链式存储队列链表实现链式队列基于单链表实现无固定容量动态扩容。采用带头结点设计规避空队列边界问题核心尾插入队、头删出队。结构体定义#includestdio.h#includestdlib.h// 链表节点结构typedefstructLNode{intdata;// 节点数据structLNode*next;// 后继指针}LNode;// 链式队列结构头尾双指针typedefstruct{LNode*front;LNode*rear;}LinkQueue;操作初始化队列逻辑创建头结点头尾指针同时指向头结点初始队列为空。voidInitQueue(LinkQueue*q){// 动态开辟头结点空间q-frontq-rear(LNode*)malloc(sizeof(LNode));q-front-nextNULL;// 头结点后继置空}判空逻辑头尾指针重合代表无有效元素。intisEmpty(LinkQueue*q){returnq-frontq-rear;}入队尾插法逻辑新建节点→挂载到队尾→更新尾指针全程不改动头指针。intEnQueue(LinkQueue*q,intx){// 1. 新建节点LNode*s(LNode*)malloc(sizeof(LNode));s-datax;s-nextNULL;// 2. 挂载到队尾q-rear-nexts;// 3. 尾指针后移q-rears;return1;}出队头删法逻辑取出首元素→断链释放节点→判断是否为最后一个节点重置尾指针避免野指针。intDeQueue(LinkQueue*q,int*x){if(isEmpty(q))return0;// 1. 指向第一个有效节点LNode*pq-front-next;*xp-data;// 2. 头结点指向新后继删除原队头q-front-nextp-next;// 3. 关键删除最后一个节点重置尾指针if(q-rearp){q-rearq-front;}free(p);// 释放内存防止内存泄漏return1;}优缺点与适用场景优点动态扩容、无溢出、不浪费内存无需提前开辟空间缺点每个节点存储指针有额外内存开销不支持随机访问读写速度略慢于顺序队列适用场景数据量不确定、频繁增减元素的场景四、双端队列Deque双端队列支持头尾双向入队、双向出队兼容普通队列和栈的所有功能基于循环数组实现沿用环形取模逻辑。结构体定义#includestdio.h#defineMaxSize5typedefstruct{intdata[MaxSize];intfront;intrear;}Deque;操作初始化voidInitDeque(Deque*d){d-frontd-rear0;}判空、判满intisEmpty(Deque*d){returnd-frontd-rear;}intisFull(Deque*d){return(d-rear1)%MaxSized-front;}队头入队反向入队逻辑front 指针先向前循环移动再存入数据实现头部插入。intEnFront(Deque*d,intx){if(isFull(d))return0;// 向前移动MaxSize 防止下标为负d-front(d-front-1MaxSize)%MaxSize;d-data[d-front]x;return1;}队尾入队常规入队intEnRear(Deque*d,intx){if(isFull(d))return0;d-data[d-rear]x;d-rear(d-rear1)%MaxSize;return1;}队头出队常规出队intDeFront(Deque*d,int*x){if(isEmpty(d))return0;*xd-data[d-front];d-front(d-front1)%MaxSize;return1;}队尾出队反向出队逻辑rear 指针先向前循环回撤再取出尾部数据。intDeRear(Deque*d,int*x){if(isEmpty(d))return0;// 尾部指针回撤d-rear(d-rear-1MaxSize)%MaxSize;*xd-data[d-rear];return1;}核心应用场景算法滑动窗口最大值、单调队列问题工程浏览器前进后退、历史记录管理缓存机制、任务双向调度五、四种队列全方位对比队列类型存储结构容量特性溢出问题核心特点适用场景普通顺序队列数组固定假溢出严重结构简单缺陷明显仅教学演示循环顺序队列数组固定无溢出速度最快、利用率高固定大小缓冲区链式队列链表动态无溢出动态扩容、无空间浪费数据量不确定场景双端队列数组/链表可选无溢出两端进出、功能最全算法刷题、双向调度