Linux环境下的C语言编程（四十）-育师

一、链队列

使用链表实现的队列，动态分配内存。

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; }