队列的链式实现

队列的链式实现

链队列是队列的链式存储结构，本质上是操作受限的单链表。其解决了顺序队列（循环队列）“容量固定、可能溢出”的缺陷。
链队列需要两个指针：

• front（队头指针）：指向头结点（注意：不是第一个数据结点）。头结点的data闲置，next指向真正的首元结点。
• rear（队尾指针）：指向最后一个数据结点（尾结点）。

带头结点后，空队时front == rear（均指向头结点），所有操作逻辑完全统一。

图示：

空队： front(rear) -> [头结点 | next=NULL] 入队10： front -> [头结点 | next] -> [10 | NULL] rear-^ 入队20： front -> [头结点 | next] -> [10 | next] -> [20 | NULL] rear -^

代码实现

结构定义与初始化

与顺序队列不同，链队列通常将front和rear封装在一个结构体中，便于函数传参。

带头结点

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>// ① 结点定义（与单链表完全一样）typedefstructLNode{intdata;structLNode*next;}LNode;// ② 链队列定义（封装了队头和队尾指针）typedefstruct{LNode*front;// 队头指针（指向头结点）LNode*rear;// 队尾指针（指向最后一个结点）}LinkQueue;// 带头结点// 初始化 ：创建空队列（创建头结点）boolInitQueue(LinkQueue&Q){// 1. 申请头结点空间 队尾指针也指向头结点（表示空队）Q.front=Q.rear=(LNode*)malloc(sizeof(LNode));if(Q.front==NULL)returnfalse;// 内存分配失败// 2. 头结点的 next 置空Q.front->next=NULL;returntrue;}// 判空boolQueueEmpty(LinkQueue Q){returnQ.front==Q.rear;// 或者 Q.front->next == NULL 若 front = rear 则为空}// 判满 链队列不存在 “满 ”的概念！// 唯一的限制是堆内存耗尽。通常不写判满函数，而是在入队时检测 malloc 返回值。boolQueueFull(LinkQueue Q){returnfalse;// 理论永远不满（只要内存够）}

不带头结点

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>typedefstructLNode{intdata;structLNode*next;}LNode;typedefstruct{LNode*front;// 队头指针：指向第一个数据结点（不是头结点！！！！！）LNode*rear;// 队尾指针：指向最后一个数据结点}LinkQueue;// 不带头结点// 初始化 创建空队列（不分配头结点）voidInitQueue(LinkQueue&Q){Q.front=NULL;// 直接置空Q.rear=NULL;// 直接置空}// 判空boolQueueEmpty(LinkQueue Q){returnQ.front==NULL;// 只要队头为空，队列就为空// 也可以这样判断：Q.rear == NULL;}

入队（尾插法）

带头结点

步骤：新建结点 → 接到rear后面 → 更新rear为新结点

// 带头结点// 入队 在队尾（rear 后面）插入元素 eboolEnQueue(LinkQueue&Q,inte){// 1. 申请新结点空间LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL)returnfalse;// 内存耗尽，相当于 “队满 ”// 2. 初始化新结点s->data=e;s->next=NULL;// 3. 将新结点挂到当前尾结点后面Q.rear->next=s;// 4. 尾指针后移（指向新的尾结点）Q.rear=s;returntrue;}

不带头结点

// 不带头结点// 入队 在队尾插入元素 eboolEnQueue(LinkQueue&Q,inte){LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL)returnfalse;s->data=e;s->next=NULL;// 必须特别判断是不是第一个结点// 不带头结点的队列，第一个元素入队时需要特别处理if(Q.front==NULL){// 情况1：空队，front 和 rear 都指向新结点Q.front=s;// 修改队头队尾指针Q.rear=s;}else{// 情况2：非空队，挂在尾结点后面Q.rear->next=s;// 新结点插入到 rear 结点之后Q.rear=s;// 修改 rear 指针}returntrue;}

出队

删除队头第一个有效结点
特殊边界：如果删除后队列为空，需要将rear重置回头结点，防止rear悬空。

带头结点

删除头结点的后继。

// 带头结点// 出队 删除队头元素，并通过 e 带回其值boolDeQueue(LinkQueue&Q,int&e){// 1. 判空if(Q.front==Q.rear)returnfalse;// 2. p 指向首元结点（第一个数据结点）LNode*p=Q.front->next;e=p->data;// 保存数据// 3. 头结点跨过 p，指向 p 的下一个结点Q.front->next=p->next;// 注意：如果 p 恰好是最后一个结点（即出队后队列变空）// 必须把 rear 重新指向头结点，否则 rear 将指向已释放的内存！if(p==Q.rear){Q.rear=Q.front;}// 4. 释放 p 结点内存free(p);returntrue;}

不带头结点

// 不带头结点// 出队 删除队头元素，并通过 e 带回其值boolDeQueue(LinkQueue&Q,int&e){// 1. 判空if(Q.front==NULL)returnfalse;// 2. p 指向队头结点（直接就是 front）LNode*p=Q.front;e=p->data;// 3. 队头指针后移（指向下一个数据结点）Q.front=p->next;// 如果删除的是唯一结点（出队后队列变空）if(Q.front==NULL){// 必须把 rear 也置为 NULL，否则 rear 指向已释放的内存！Q.rear=NULL;}// 或这样写// if(Q.rear == p ){// Q.rear = NULL;// Q.front = NULL;// }free(p);returntrue;}

查队头

// 带头结点// 查队头 只读操作，不删除元素boolGetHead(LinkQueue Q,int&e){if(Q.front==Q.rear)// 空队returnfalse;e=Q.front->next->data;// 头结点的后继才是第一个数据returntrue;}// 不带头结点// 查队头 只读操作boolGetHead(LinkQueue Q,int&e){if(Q.front==NULL)returnfalse;e=Q.front->data;// front 直接指向数据结点，无需绕 ->nextreturntrue;}

销毁

// 带头结点// 销毁 释放所有结点（包括头结点）voidDestroyQueue(LinkQueue&Q){LNode*p=Q.front;// p 从头结点开始while(p!=NULL){LNode*q=p;p=p->next;free(q);}// 防止野指针（虽然 Q 是引用，但置空是好习惯）Q.front=NULL;Q.rear=NULL;}// 不带头结点// 销毁 释放所有数据结点voidDestroyQueue(LinkQueue&Q){LNode*p=Q.front;while(p!=NULL){LNode*q=p;p=p->next;free(q);}Q.front=NULL;Q.rear=NULL;}

链队列是采用链式存储结构的队列，通常使用带头结点的单链表实现，并附设front和rear两个指针分别指向头结点和尾结点。入队操作对应单链表的尾插法（rear->next = s; rear = s;），出队操作对应删除头结点的后继结点。在出队时，若被删结点是尾结点，必须将rear重置为front。链队列克服了顺序队列容量固定的缺陷，入队、出队、判空操作的时间复杂度均为O(1)。