队列是一种**先进先出（FIFO）**的线性数据结构，只允许在一端（队尾）插入、另一端（队头）删除。链队列用带头结点的单链表实现，相比顺序队列（循环数组）不会存在假溢出问题，空间按需分配。
数据结构定义
#include <stdio.h>#include <stdbool.h>#include <stdlib.h>
typedef char DataType;
typedef struct LQNode { DataType data; struct LQNode *next;} LQNode, *LinkedQNode; // 链队列结点的类型
typedef struct { struct LQNode *front, *rear; // 头指针和尾指针} LQueue, *LinkedQueue; // 将头、尾指针封装在一起的链队列
// [算法 3.21] 创建一个带头结点的空队列void QueueInit(LinkedQueue *Q) { //构造一个空队列 Q *Q = (LinkedQueue)malloc(sizeof(LQueue)); // 分配队列结构体空间 if (!(*Q)) return; // 分配失败 (*Q)->front = (LQNode*)malloc(sizeof(LQNode)); // 分配头结点 if (!((*Q)->front)) { free(*Q); *Q = NULL; return; } (*Q)->front->next = NULL; // 头结点next置空 (*Q)->rear = (*Q)->front; // front和rear都指向头结点，表示队列为空}
// [算法 3.22] 入队列bool QueueIn(LinkedQueue Q, DataType x) { //插入元素 x 为 Q 的队尾元素 if (!Q) return false; LQNode *node = (LQNode*)malloc(sizeof(LQNode)); // 新建结点 if (!node) return false; node->data = x; node->next = NULL; Q->rear->next = node; // 原队尾结点next指向新结点 Q->rear = node; // rear指向新结点 return true;}
// [算法 3.23] 出队列bool QueueOut (LinkedQueue Q, DataType *x){ //若队列不空 ,则删除 Q 的队头元素 if (!Q || Q->front == Q->rear) return false; // 队空 LQNode *p = Q->front->next; // 队头元素 *x = p->data; // 取数据 Q->front->next = p->next; // 头结点next指向下一个结点 if (Q->rear == p) Q->rear = Q->front; // 若出队后队空，rear回到头结点 free(p); return true;}
// [算法 3.24] 判断队列是否为空bool QueueEmpty(LinkedQueue Q) { //判断队列 Q 是否为空 if (!Q) return true; // 队列指针为空 return Q->front == Q->rear; // 头尾指针相遇即为空}
//清空队列void Empty(LinkedQueue Q){ while (Q->front != Q->rear) { LQNode * p = Q->front->next; //取得队列第一个元素指针 Q->front->next = p->next; //修改队头指针指向 free(p); if(Q->front->next == NULL) //只有一个元素时 ,出队后队空 ,此时还要修改队尾指针 Q->rear = Q->front; }}
// 释放队列void FreeQueue(LinkedQueue *Q) { if (*Q == NULL) return; // 如果队列为空，直接返回
LQNode * current = (*Q)->front; // 从头节点开始 LQNode * temp;
while (current != NULL) { temp = current; // 保存当前节点 current = current->next; // 移动到下一个节点 free(temp); // 释放当前节点 }
free(*Q); // 最后释放队列结构体本身 *Q = NULL; // 将队列指针设为NULL，防止悬挂指针}
//获取队首元素void GetQueue(LinkedQueue Q){ if (Q->front == NULL) { printf("None\n"); return; } else printf("%c\n", Q->front->next->data);
}
int main(){ DataType c,x; LinkedQueue Q = NULL; QueueInit(&Q); while (1) { scanf(" %c", &c); if (c == 'E') { scanf(" %c", &x); QueueIn(Q, x); } else if (c == 'C') { Empty(Q); } else if (c == 'G') { GetQueue(Q); } else if (c == 'D') { //dequeue(m); if(QueueOut(Q, &x)) printf("%c\n", x); else printf("None\n"); } else if (c == 'Q') { break; } } FreeQueue(&Q); return 0;}这里详细讲一下 (*Q)-> 的含义和作用：
二级指针解引用 (*Q)->
-
参数类型
QueueInit(LinkedQueue *Q)里的Q是“指向队列指针的指针”。
也就是：LinkedQueue是LQueue *，LinkedQueue *Q就是LQueue **Q。 -
解引用
*Q表示“取出 Q 指向的内容”，也就是实际的队列指针（LQueue *）。
例如：*Q = malloc(...)，就是让外部的队列指针指向新分配的队列结构体。 -
访问结构体成员
(*Q)->front表示“队列的头指针”。
因为*Q是LQueue *，所以用->访问结构体成员。 -
为什么不用 Q->front
如果直接用Q->front，那 Q 必须是LQueue *，而不是LQueue **。
但这里 Q 是指向指针的指针，所以要先解引用，再访问成员。
举例说明：
void QueueInit(LinkedQueue *Q) { *Q = (LinkedQueue)malloc(sizeof(LQueue)); // 分配队列结构体 (*Q)->front = (*Q)->rear = (LQNode *)malloc(sizeof(LQNode)); // 分配头结点 (*Q)->front->next = NULL; // 头结点next置空}*Q：拿到实际的队列指针(*Q)->front：访问队列的头指针(*Q)->rear：访问队列的尾指针
总结：(*Q)-> 是先解引用拿到队列指针，再用 -> 访问结构体成员。这样才能正确初始化和操作队列。
用指针返回出队值 *x = p->data
出队函数签名是 QueueOut(LinkedQueue Q, DataType *x)，其中 *x = p->data; 这一行不带 * 不行。
原因是：要把出队的元素值“带出来”给主程序用，必须用指针参数（DataType *x），在函数里通过 *x = p->data; 赋值。如果只用值参数（如 DataType x），函数内部的赋值不会影响主程序变量，主程序拿不到出队的值。这就是 C 语言“用指针返回结果”的常规做法——和 scanf("%d", &n) 传 &n 一个道理。