跳到主要内容

C 语言队列实现

介绍

队列(Queue)是一种常见的数据结构,遵循先进先出(FIFO, First In First Out)的原则。队列的操作主要包括入队(Enqueue)出队(Dequeue)。入队是将元素添加到队列的末尾,而出队则是从队列的头部移除元素。

队列在计算机科学中有广泛的应用,例如任务调度、缓冲区管理、广度优先搜索(BFS)等。理解队列的实现原理对于掌握更复杂的数据结构和算法至关重要。

队列的基本操作

队列通常支持以下操作:

  1. Enqueue: 将元素添加到队列的末尾。
  2. Dequeue: 移除队列头部的元素。
  3. Front: 获取队列头部的元素,但不移除它。
  4. IsEmpty: 检查队列是否为空。
  5. IsFull: 检查队列是否已满(仅适用于固定大小的队列)。

队列的实现

在C语言中,队列可以通过数组或链表来实现。下面我们将分别介绍这两种实现方式。

1. 使用数组实现队列

使用数组实现队列时,我们需要维护两个指针:frontrearfront 指向队列的头部,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
提示

链表实现的队列可以动态扩展,适合处理不确定数量的数据。

实际应用场景

队列在计算机科学中有许多实际应用,以下是一些常见的例子:

  1. 任务调度:操作系统使用队列来管理进程的执行顺序。
  2. 缓冲区管理:网络数据包的处理通常使用队列来缓冲数据。
  3. 广度优先搜索(BFS):在图算法中,BFS使用队列来存储待访问的节点。

总结

队列是一种重要的数据结构,遵循先进先出的原则。通过数组或链表实现队列,可以有效地管理数据的顺序。理解队列的实现和应用场景,对于学习更复杂的数据结构和算法非常有帮助。

附加资源与练习

  1. 练习:尝试实现一个循环队列,避免数组实现中的空间浪费问题。
  2. 资源:阅读更多关于队列的应用,例如在操作系统中的任务调度。
  3. 挑战:使用队列实现一个简单的打印任务调度系统。
警告

在实现队列时,务必注意边界条件,例如队列为空或满的情况。