C语言队列实现与应用详解279

队列是一种先进先出 (FIFO, First-In-First-Out) 的线性数据结构。它类似于排队等候，先进入队列的元素先被处理。在C语言中，我们可以使用数组或链表来实现队列。本文将详细介绍C语言中队列的两种常见实现方式，并结合代码示例，讲解其应用。

一、基于数组的循环队列

使用数组实现队列，需要考虑数组空间的有效利用。如果仅仅使用一个数组模拟队列，则入队和出队操作都会涉及到数组元素的移动，效率较低。因此，我们通常采用循环队列的方式来解决这个问题。循环队列利用数组的循环特性，当队列尾指针到达数组末尾时，下一个位置回到数组的开头。这样可以有效地避免数组元素的移动，提高效率。

以下是基于数组的循环队列的C语言实现：```c
#include
#include
#include
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
int size;
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = 0;
q->rear = -1;
q->size = 0;
}
// 判断队列是否为空
bool isEmpty(Queue *q) {
return q->size == 0;
}
// 判断队列是否已满
bool isFull(Queue *q) {
return q->size == MAX_SIZE;
}
// 入队
bool enQueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full!");
return false;
}
q->rear = (q->rear + 1) % MAX_SIZE;
q->data[q->rear] = value;
q->size++;
return true;
}
// 出队
bool deQueue(Queue *q, int *value) {
if (isEmpty(q)) {
printf("Queue is empty!");
return false;
}
*value = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
q->size--;
return true;
}
// 获取队列大小
int getQueueSize(Queue *q) {
return q->size;
}
int main() {
Queue q;
initQueue(&q);
enQueue(&q, 10);
enQueue(&q, 20);
enQueue(&q, 30);
int value;
deQueue(&q, &value);
printf("Dequeued value: %d", value); // Output: 10
deQueue(&q, &value);
printf("Dequeued value: %d", value); // Output: 20
printf("Queue size: %d", getQueueSize(&q)); // Output: 1
return 0;
}
```

二、基于链表的队列

使用链表实现队列可以避免数组大小的限制，更加灵活。链表的每个节点存储一个队列元素，链表的头指针指向队列的头部，尾指针指向队列的尾部。入队操作在尾部插入节点，出队操作删除头部节点。

以下是基于链表的队列的C语言实现：```c
#include
#include
#include
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *front;
Node *rear;
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = q->rear = NULL;
}
// 判断队列是否为空
bool isEmpty(Queue *q) {
return q->front == NULL;
}
// 入队
void enQueue(Queue *q, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (isEmpty(q)) {
q->front = q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
}
// 出队
bool deQueue(Queue *q, int *value) {
if (isEmpty(q)) {
return false;
}
Node *temp = q->front;
*value = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return true;
}
int main() {
Queue q;
initQueue(&q);
enQueue(&q, 10);
enQueue(&q, 20);
enQueue(&q, 30);
int value;
deQueue(&q, &value);
printf("Dequeued value: %d", value); // Output: 10
return 0;
}
```

三、队列的应用

队列广泛应用于各种程序设计场景，例如：
广度优先搜索 (BFS)：在图论中，BFS 使用队列来存储待访问的节点。
任务调度：操作系统使用队列来管理等待执行的任务。
缓冲区：在数据处理中，队列可以作为缓冲区，用于存储临时数据。
打印队列：打印机使用队列来管理等待打印的任务。
模拟系统：例如模拟银行排队等候。

四、总结

本文详细介绍了C语言中队列的两种实现方式：基于数组的循环队列和基于链表的队列，并给出了相应的代码示例。选择哪种实现方式取决于具体的应用场景。对于需要预先知道队列大小的场景，数组实现更有效率；对于大小不确定的队列，链表实现更灵活。 理解队列的概念和实现方法对于程序员来说至关重要，因为它在许多算法和系统设计中扮演着关键角色。

2025-06-16

上一篇：C语言绘制字符串：深入探讨DrawString函数及其替代方案

下一篇：C语言字符逆向输出详解：多种方法及性能比较