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

在程序设计中，队列是一种常用的数据结构，它遵循先进先出 (FIFO, First-In-First-Out) 的原则。这意味着最先进入队列的元素将最先被移除。队列广泛应用于各种场景，例如缓冲区管理、任务调度、广度优先搜索等。本文将详细介绍如何在C语言中实现队列，并探讨其在不同应用中的使用方法。

一、队列的两种实现方式：

在C语言中，我们可以使用两种主要方式来实现队列：数组和链表。

1. 数组实现：

使用数组实现队列相对简单，但需要预先分配固定大小的内存空间。如果队列元素数量超过预分配大小，就会发生溢出。为了避免这种情况，我们需要设置队列的容量，并进行相应的判断。

以下是一个基于数组实现的循环队列的示例代码：```c
#include
#include
#include
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int head;
int tail;
int size;
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->head = 0;
q->tail = 0;
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)) {
return false; // 队列已满
}
q->data[q->tail] = value;
q->tail = (q->tail + 1) % MAX_SIZE; // 循环队列处理
q->size++;
return true;
}
// 出队
bool deQueue(Queue *q, int *value) {
if (isEmpty(q)) {
return false; // 队列为空
}
*value = q->data[q->head];
q->head = (q->head + 1) % MAX_SIZE; // 循环队列处理
q->size--;
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); // 输出 10
return 0;
}
```

这段代码实现了循环队列，避免了数组索引越界的问题。`head` 指向队列头，`tail` 指向队列尾，`size` 记录队列中元素个数。入队操作将元素添加到 `tail` 位置，出队操作从 `head` 位置移除元素。

2. 链表实现：

使用链表实现队列可以动态调整队列大小，避免了数组实现中固定的容量限制。但是，链表实现的队列需要更多的内存开销来存储节点指针。

以下是一个基于链表实现的队列的示例代码：```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 = NULL;
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 = newNode;
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;
free(temp);
if (q->front == NULL) {
q->rear = NULL;
}
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); // 输出 10
return 0;
}
```