C 语言队列实现
介绍
队列(Queue)是一种常见的数据结构,遵循先进先出(FIFO, First In First Out)的原则。队列的操作主要包括入队(Enqueue)和出队(Dequeue)。入队是将元素添加到队列的末尾,而出队则是从队列的头部移除元素。
队列在计算机科学中有广泛的应用,例如任务调度、缓冲区管理、广度优先搜索(BFS)等。理解队列的实现原理对于掌握更复杂的数据结构和算法至关重要。
队列的基本操作
队列通常支持以下操作:
- Enqueue: 将元素添加到队列的末尾。
- Dequeue: 移除队列头部的元素。
- Front: 获取队列头部的元素,但不移除它。
- IsEmpty: 检查队列是否为空。
- IsFull: 检查队列是否已满(仅适用于固定大小的队列)。
队列的实现
在C语言中,队列可以通过数组或链表来实现。下面我们将分别介绍这两种实现方式。
1. 使用数组实现队列
使用数组实现队列时,我们需要维护两个指针:front
和 rear
。front
指向队列的头部,rear
指向队列的尾部。
c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 5
typedef struct {
int items[MAX_SIZE];
int front;
int rear;
} Queue;
void initializeQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
bool isFull(Queue *q) {
return q->rear == MAX_SIZE - 1;
}
bool isEmpty(Queue *q) {
return q->front == -1;
}
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full!\n");
} else {
if (isEmpty(q)) {
q->front = 0;
}
q->rear++;
q->items[q->rear] = value;
printf("Enqueued: %d\n", value);
}
}
int dequeue(Queue *q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1;
}
printf("Dequeued: %d\n", item);
return item;
}
}
int front(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
} else {
return q->items[q->front];
}
}
int main() {
Queue q;
initializeQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
dequeue(&q);
dequeue(&q);
printf("Front element is: %d\n", front(&q));
return 0;
}
输入和输出示例:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Dequeued: 10
Dequeued: 20
Front element is: 30
备注
使用数组实现队列时,需要注意队列的容量限制。如果队列已满,则无法继续入队操作。
2. 使用链表实现队列
链表实现的队列可以动态调整大小,避免了数组实现中的容量限制问题。
c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *front;
Node *rear;
} Queue;
void initializeQueue(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;
}
printf("Enqueued: %d\n", value);
}
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
} else {
Node *temp = q->front;
int item = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
printf("Dequeued: %d\n", item);
return item;
}
}
int front(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
} else {
return q->front->data;
}
}
int main() {
Queue q;
initializeQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
dequeue(&q);
dequeue(&q);
printf("Front element is: %d\n", front(&q));
return 0;
}
输入和输出示例:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Dequeued: 10
Dequeued: 20
Front element is: 30
提示
链表实现的队列可以动态扩展,适合处理不确定数量的数据。
实际应用场景
队列在计算机科学中有许多实际应用,以下是一些常见的例子:
- 任务调度:操作系统使用队列来管理进程的执行顺序。
- 缓冲区管理:网络数据包的处理通常使用队列来缓冲数据。
- 广度优先搜索(BFS):在图算法中,BFS使用队列来存储待访问的节点。
总结
队列是一种重要的数据结构,遵循先进先出的原则。通过数组或链表实现队列,可以有效地管理数据的顺序。理解队列的实现和应用场景,对于学习更复杂的数据结构和算法非常有帮助。
附加资源与练习
- 练习:尝试实现一个循环队列,避免数组实现中的空间浪费问题。
- 资源:阅读更多关于队列的应用,例如在操作系统中的任务调度。
- 挑战:使用队列实现一个简单的打印任务调度系统。
警告
在实现队列时,务必注意边界条件,例如队列为空或满的情况。