C语言队列实现及应用详解132

队列是一种先进先出（FIFO）的数据结构，广泛应用于计算机科学的各个领域，例如操作系统中的进程调度、缓冲区管理，以及网络编程中的数据包处理等。本文将深入探讨C语言中队列的实现方法，并结合实际案例进行讲解。

C语言本身并没有内置队列数据结构，我们需要自行定义和实现。常用的实现方式有两种：使用数组和使用链表。

1. 基于数组的循环队列

使用数组实现队列，需要考虑队列的边界问题。为了避免频繁的元素移动，通常采用循环队列的方式。循环队列利用数组的循环特性，当队列尾指针到达数组末尾时，下一个元素插入到数组的起始位置。下面是一个基于数组的循环队列的C语言实现：```c
#include
#include
#include
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
int size;
} Queue;
// 初始化队列
bool initQueue(Queue *q) {
q->front = 0;
q->rear = 0;
q->size = 0;
return true;
}
// 判断队列是否为空
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)) {
return false; // 队列已满
}
q->data[q->rear] = value;
q->rear = (q->rear + 1) % MAX_SIZE;
q->size++;
return true;
}
// 出队
bool dequeue(Queue *q, int *value) {
if (isEmpty(q)) {
return false; // 队列为空
}
*value = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
q->size--;
return true;
}
// 获取队列大小
int queueSize(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: Dequeued value: 10
printf("Queue size: %d", queueSize(&q)); // Output: Queue size: 2
return 0;
}
```

这段代码包含了队列的初始化、判断空/满、入队、出队以及获取队列大小等基本操作。需要注意的是，`% MAX_SIZE` 操作实现了循环队列的循环特性。

2. 基于链表的队列

使用链表实现队列可以避免数组大小的限制，动态调整队列大小。链表实现的队列更加灵活，但需要额外的内存开销来管理链表节点。```c
#include
#include
#include
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *front;
Node *rear;
} Queue;
// 初始化队列
bool initQueue(Queue *q) {
q->front = NULL;
q->rear = NULL;
return true;
}
// 判断队列是否为空
bool isEmpty(Queue *q) {
return q->front == NULL;
}
// 入队
bool enqueue(Queue *q, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
return false; // 内存分配失败
}
newNode->data = value;
newNode->next = NULL;
if (isEmpty(q)) {
q->front = newNode;
} else {
q->rear->next = newNode;
}
q->rear = newNode;
return true;
}
// 出队
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: Dequeued value: 10
return 0;
}
```