一、链队列
使用链表实现的队列，动态分配内存。
1. 结构定义
#include <stdio.h> #include <stdlib.h> // 链队列节点 typedef struct QueueNode { int data; struct QueueNode* next; } QueueNode; // 链队列 typedef struct { QueueNode* front; // 队头指针 QueueNode* rear; // 队尾指针 } LinkedQueue;2. 基本操作实现
// 初始化队列 void initLinkedQueue(LinkedQueue* q) { q->front = q->rear = NULL; } // 判断队列是否为空 int isEmptyLinkedQueue(LinkedQueue* q) { return q->front == NULL; } // 入队操作 int enqueueLinked(LinkedQueue* q, int value) { QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); if (!newNode) { printf("内存分配失败！\n"); return 0; } newNode->data = value; newNode->next = NULL; if (isEmptyLinkedQueue(q)) { // 队列为空，新节点既是队头也是队尾 q->front = q->rear = newNode; } else { // 队列不为空，插入到队尾 q->rear->next = newNode; q->rear = newNode; } return 1; } // 出队操作 int dequeueLinked(LinkedQueue* q, int* value) { if (isEmptyLinkedQueue(q)) { printf("队列为空，无法出队！\n"); return 0; } QueueNode* temp = q->front; *value = temp->data; q->front = q->front->next; // 如果出队后队列为空，需要重置rear if (q->front == NULL) { q->rear = NULL; } free(temp); return 1; } // 获取队头元素 int getFrontLinked(LinkedQueue* q, int* value) { if (isEmptyLinkedQueue(q)) { printf("队列为空！\n"); return 0; } *value = q->front->data; return 1; } // 获取队列长度 int getLengthLinked(LinkedQueue* q) { int length = 0; QueueNode* current = q->front; while (current != NULL) { length++; current = current->next; } return length; } // 打印队列 void printLinkedQueue(LinkedQueue* q) { if (isEmptyLinkedQueue(q)) { printf("队列为空！\n"); return; } printf("队列内容（队头->队尾）："); QueueNode* current = q->front; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n"); } // 销毁队列 void destroyLinkedQueue(LinkedQueue* q) { int value; while (!isEmptyLinkedQueue(q)) { dequeueLinked(q, &value); } }3. 链队列特点
优点：动态增长，不会溢出（除非内存不足）
缺点：每个节点需要额外指针空间，内存开销较大
二、循环队列
使用数组实现的队列，通过循环利用空间解决假溢出问题。
1. 结构定义
#define MAX_SIZE 5 // 队列最大容量 typedef struct { int data[MAX_SIZE]; int front; // 队头指针 int rear; // 队尾指针 } CircularQueue;2. 基本操作实现
// 初始化队列 void initCircularQueue(CircularQueue* q) { q->front = 0; q->rear = 0; } // 判断队列是否为空 int isEmptyCircularQueue(CircularQueue* q) { return q->front == q->rear; } // 判断队列是否已满 int isFullCircularQueue(CircularQueue* q) { return (q->rear + 1) % MAX_SIZE == q->front; } // 入队操作 int enqueueCircular(CircularQueue* q, int value) { if (isFullCircularQueue(q)) { printf("队列已满，无法入队！\n"); return 0; } q->data[q->rear] = value; q->rear = (q->rear + 1) % MAX_SIZE; return 1; } // 出队操作 int dequeueCircular(CircularQueue* q, int* value) { if (isEmptyCircularQueue(q)) { printf("队列为空，无法出队！\n"); return 0; } *value = q->data[q->front]; q->front = (q->front + 1) % MAX_SIZE; return 1; } // 获取队头元素 int getFrontCircular(CircularQueue* q, int* value) { if (isEmptyCircularQueue(q)) { printf("队列为空！\n"); return 0; } *value = q->data[q->front]; return 1; } // 获取队列长度 int getLengthCircular(CircularQueue* q) { return (q->rear - q->front + MAX_SIZE) % MAX_SIZE; } // 打印队列 void printCircularQueue(CircularQueue* q) { if (isEmptyCircularQueue(q)) { printf("队列为空！\n"); return; } printf("队列内容（队头->队尾）："); int i = q->front; while (i != q->rear) { printf("%d ", q->data[i]); i = (i + 1) % MAX_SIZE; } printf("\n"); }3. 循环队列特点
优点：内存连续，访问速度快，内存开销小
缺点：固定大小，需要预分配空间
三、两种队列的比较
| 特性 | 链队列 | 循环队列 |
|---|---|---|
| 存储结构 | 链表 | 数组 |
| 内存分配 | 动态 | 静态/固定 |
| 空间利用率 | 较低（有指针开销） | 较高 |
| 最大容量 | 理论上无限制 | 固定大小 |
| 操作时间复杂度 | O(1) | O(1) |
| 适用场景 | 大小不确定的队列 | 大小确定的队列 |
四、使用示例
int main() { printf("=== 链队列测试 ===\n"); LinkedQueue lq; initLinkedQueue(&lq); // 入队测试 enqueueLinked(&lq, 10); enqueueLinked(&lq, 20); enqueueLinked(&lq, 30); printLinkedQueue(&lq); // 出队测试 int value; dequeueLinked(&lq, &value); printf("出队元素：%d\n", value); printLinkedQueue(&lq); printf("\n=== 循环队列测试 ===\n"); CircularQueue cq; initCircularQueue(&cq); // 入队测试 enqueueCircular(&cq, 1); enqueueCircular(&cq, 2); enqueueCircular(&cq, 3); enqueueCircular(&cq, 4); printCircularQueue(&cq); // 队列满测试 if (!enqueueCircular(&cq, 5)) { printf("队列已满，5无法入队\n"); } // 出队测试 dequeueCircular(&cq, &value); printf("出队元素：%d\n", value); printCircularQueue(&cq); // 再次入队 enqueueCircular(&cq, 5); printCircularQueue(&cq); // 销毁链队列 destroyLinkedQueue(&lq); return 0; }区别使用
选择链队列：
队列大小不确定或变化较大
内存充足，更注重灵活性
不需要随机访问队列元素
选择循环队列：
队列大小固定或可预估
对性能要求高
需要连续内存存储
