[教程]C语言队列编程：入门经典与实战技巧解析

1. 队列简介队列是一种先进先出（FIFO）的数据结构，它是计算机科学中一种常用的数据组织方式。在队列中，最先进入的元素将最先被移除。这种数据结构广泛应用于各种场景，如操作系统、网络协议、数据库等。2...

1. 队列简介

队列是一种先进先出（FIFO）的数据结构，它是计算机科学中一种常用的数据组织方式。在队列中，最先进入的元素将最先被移除。这种数据结构广泛应用于各种场景，如操作系统、网络协议、数据库等。

2. 队列的基本操作

队列的基本操作包括：

• 入队（Enqueue）：在队列尾部添加一个元素。
• 出队（Dequeue）：从队列头部移除一个元素。
• 队列长度：获取队列中元素的数量。
• 查看队列头部元素：获取队列头部元素但不移除它。

3. 队列的存储结构

队列的存储结构主要有以下几种：

• 顺序队列：使用数组实现，空间利用率较高，但存在扩容问题。
• 链式队列：使用链表实现，不存在扩容问题，但空间利用率较低。

3.1 顺序队列实现

#include 
#include 
#define MAX_SIZE 100
typedef struct { int data[MAX_SIZE]; int front; int rear;
} SeqQueue;
void InitQueue(SeqQueue *q) { q->front = q->rear = 0;
}
int IsEmpty(SeqQueue *q) { return q->front == q->rear;
}
int IsFull(SeqQueue *q) { return (q->rear + 1) % MAX_SIZE == q->front;
}
void EnQueue(SeqQueue *q, int x) { if (IsFull(q)) { printf("Queue is full!\n"); return; } q->data[q->rear] = x; q->rear = (q->rear + 1) % MAX_SIZE;
}
int DeQueue(SeqQueue *q, int *x) { if (IsEmpty(q)) { printf("Queue is empty!\n"); return 0; } *x = q->data[q->front]; q->front = (q->front + 1) % MAX_SIZE; return 1;
}
int GetHead(SeqQueue *q, int *x) { if (IsEmpty(q)) { printf("Queue is empty!\n"); return 0; } *x = q->data[q->front]; return 1;
}
int GetLength(SeqQueue *q) { return (q->rear - q->front + MAX_SIZE) % MAX_SIZE;
}

3.2 链式队列实现

#include 
#include 
typedef struct QueueNode { int data; struct QueueNode *next;
} QueueNode;
typedef struct { QueueNode *front; QueueNode *rear;
} LinkQueue;
void InitQueue(LinkQueue *q) { q->front = q->rear = (QueueNode *)malloc(sizeof(QueueNode)); if (!q->front) { exit(1); } q->front->next = NULL;
}
int IsEmpty(LinkQueue *q) { return q->front == q->rear;
}
void EnQueue(LinkQueue *q, int x) { QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode)); if (!node) { exit(1); } node->data = x; node->next = NULL; q->rear->next = node; q->rear = node;
}
int DeQueue(LinkQueue *q, int *x) { if (IsEmpty(q)) { return 0; } QueueNode *node = q->front->next; *x = node->data; q->front->next = node->next; if (q->front->next == NULL) { q->rear = q->front; } free(node); return 1;
}
int GetHead(LinkQueue *q, int *x) { if (IsEmpty(q)) { return 0; } *x = q->front->next->data; return 1;
}
int GetLength(LinkQueue *q) { int length = 0; QueueNode *node = q->front->next; while (node) { length++; node = node->next; } return length;
}

4. 实战技巧

4.1 队列的动态扩容

在顺序队列中，当队列满时需要扩容。以下是一个动态扩容的实现：

void EnQueue(SeqQueue *q, int x) { if (IsFull(q)) { int *new_data = (int *)realloc(q->data, MAX_SIZE * 2); if (!new_data) { exit(1); } q->data = new_data; MAX_SIZE *= 2; } q->data[q->rear] = x; q->rear = (q->rear + 1) % MAX_SIZE;
}

4.2 队列的遍历

队列的遍历可以通过循环实现：

void Traverse(SeqQueue *q) { if (IsEmpty(q)) { printf("Queue is empty!\n"); return; } int i = q->front; while (i != q->rear) { printf("%d ", q->data[i]); i = (i + 1) % MAX_SIZE; } printf("\n");
}

4.3 队列的应用

队列在许多场景都有应用，以下是一些例子：

• 操作系统：进程调度、打印管理、设备管理。
• 网络协议：缓存管理、消息队列。
• 数据库：事务管理、锁管理。

5. 总结

本文介绍了C语言队列编程的基础知识，包括队列的基本操作、存储结构、实战技巧和应用。通过学习本文，读者可以掌握队列编程的基本方法，并将其应用于实际项目中。