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

队列是一种常用的数据结构，遵循“先进先出”（FIFO）的原则。在C语言中，我们可以通过多种方式实现队列，本文将详细介绍几种常见的队列实现方法，并结合实际案例，讲解队列的应用。

一、队列的基本概念

队列的特点是只能在队尾添加元素（入队），只能从队头删除元素（出队）。这类似于现实生活中的排队等候，先来的先被服务。队列的常用操作包括：
入队 (enqueue)：在队列尾部添加一个元素。
出队 (dequeue)：从队列头部删除一个元素。
判空 (isEmpty)：判断队列是否为空。
取队头 (front)：返回队列头部的元素，但不删除。
取队尾 (rear)：返回队列尾部的元素，但不删除。

二、队列的C语言实现方法

我们可以使用数组或链表来实现队列。下面分别介绍这两种方法：

2.1 数组实现

使用数组实现队列，需要定义一个数组和两个指针：front 指向队头，rear 指向队尾。入队时，将元素添加到 rear 指向的位置，然后 rear 后移；出队时，从 front 指向的位置删除元素，然后 front 后移。需要注意的是，数组是有限的，需要考虑队列满和队列空的情况。```c
#include
#include
#include
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
// 判断队列是否为空
bool isEmpty(Queue *q) {
return q->front == q->rear;
}
// 判断队列是否已满
bool isFull(Queue *q) {
return q->rear == MAX_SIZE - 1;
}
// 入队
bool enqueue(Queue *q, int value) {
if (isFull(q)) {
return false;
}
q->rear++;
q->data[q->rear] = value;
if (q->front == -1) {
q->front = 0;
}
return true;
}
// 出队
bool dequeue(Queue *q, int *value) {
if (isEmpty(q)) {
return false;
}
*value = q->data[q->front];
if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
} else {
q->front++;
}
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;
}
```

2.2 链表实现

使用链表实现队列可以避免数组大小的限制。链表中的每个节点存储一个队列元素，front 指向队头节点，rear 指向队尾节点。入队时，在队尾添加一个新节点；出队时，删除队头节点。```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); // Output: 10
return 0;
}
```