C语言队列

队列（Queue）是一种先进先出（FIFO，First-In-First-Out）的线性数据结构。它类似于现实生活中的排队，新元素被添加到队尾，而从队首移除元素。

1. 队列的基本操作:

• Enqueue (入队): 将一个元素添加到队列的尾部。
• Dequeue (出队): 从队列的头部移除一个元素，并返回该元素的值。
• Front (队首): 返回队首元素的值，但不移除它。
• Rear (队尾): 返回队尾元素的值，但不移除它。
• IsEmpty (判空): 检查队列是否为空。
• IsFull (判满): 检查队列是否已满（对于固定大小的队列）。
• Size (大小): 返回队列中元素的数量。

2. 队列的实现方式:

C语言中，队列通常可以通过两种方式实现：

• 数组实现 (顺序队列): 使用数组来存储队列元素，需要维护队首和队尾指针。
• 链表实现 (链式队列): 使用链表来存储队列元素，每个节点包含数据和指向下一个节点的指针。

3. 数组实现 (顺序队列):

3.1 结构体定义:

1. #define MAX_SIZE 100 // 定义队列的最大容量
3. typedef struct {
4. int data[MAX_SIZE]; // 存储队列元素的数组
5. int front; // 队首指针，指向队首元素
6. int rear; // 队尾指针，指向队尾元素的下一个位置
7. } Queue;

复制代码

3.2 初始化队列:

1. void initQueue(Queue *q) {
2. q->front = 0;
3. q->rear = 0;
4. }

复制代码

3.3 判空:

1. int isEmpty(Queue *q) {
2. return q->front == q->rear;
3. }

复制代码

3.4 判满:

1. int isFull(Queue *q) {
2. return (q->rear + 1) % MAX_SIZE == q->front; // 循环队列的判满条件
3. }

复制代码

3.5 入队:

1. int enqueue(Queue *q, int value) {
2. if (isFull(q)) {
3. printf("Queue is full!\n");
4. return 0; // 入队失败
5. }
6. q->data[q->rear] = value;
7. q->rear = (q->rear + 1) % MAX_SIZE; // 循环队列的队尾指针更新
8. return 1; // 入队成功
9. }

复制代码

3.6 出队:

1. int dequeue(Queue *q, int *value) {
2. if (isEmpty(q)) {
3. printf("Queue is empty!\n");
4. return 0; // 出队失败
5. }
6. *value = q->data[q->front];
7. q->front = (q->front + 1) % MAX_SIZE; // 循环队列的队首指针更新
8. return 1; // 出队成功
9. }

复制代码

3.7 获取队首元素:

1. int front(Queue *q, int *value) {
2. if (isEmpty(q)) {
3. printf("Queue is empty!\n");
4. return 0;
5. }
6. *value = q->data[q->front];
7. return 1;
8. }

复制代码

3.8 获取队尾元素:

1. int rear(Queue *q, int *value) {
2. if (isEmpty(q)) {
3. printf("Queue is empty!\n");
4. return 0;
5. }
6. *value = q->data[(q->rear - 1 + MAX_SIZE) % MAX_SIZE]; // 注意循环队列的队尾元素位置
7. return 1;
8. }

复制代码

3.9 循环队列:

为了避免“假溢出”现象（即队列还有空间，但 rear 指针已经到达数组末尾），通常使用循环队列。循环队列通过取模运算 (%) 来实现队首和队尾指针的循环移动。

4. 链表实现 (链式队列):

4.1 结构体定义:

1. typedef struct Node {
2. int data;
3. struct Node *next;
4. } Node;
6. typedef struct {
7. Node *front;
8. Node *rear;
9. } Queue;

复制代码

4.2 初始化队列:

1. void initQueue(Queue *q) {
2. q->front = NULL;
3. q->rear = NULL;
4. }

复制代码

4.3 判空:

1. int isEmpty(Queue *q) {
2. return q->front == NULL;
3. }

复制代码

4.4 入队:

1. int enqueue(Queue *q, int value) {
2. Node *newNode = (Node *)malloc(sizeof(Node));
3. if (newNode == NULL) {
4. printf("Memory allocation failed!\n");
5. return 0; // 入队失败
6. }
7. newNode->data = value;
8. newNode->next = NULL;
10. if (isEmpty(q)) {
11. q->front = newNode;
12. q->rear = newNode;
13. } else {
14. q->rear->next = newNode;
15. q->rear = newNode;
16. }
17. return 1; // 入队成功
18. }

复制代码

4.5 出队:

1. int dequeue(Queue *q, int *value) {
2. if (isEmpty(q)) {
3. printf("Queue is empty!\n");
4. return 0; // 出队失败
5. }
6. Node *temp = q->front;
7. *value = temp->data;
8. q->front = q->front->next;
10. if (q->front == NULL) {
11. q->rear = NULL; // 如果队列为空，则 rear 也需要置为 NULL
12. }
14. free(temp);
15. return 1; // 出队成功
16. }

复制代码

4.6 获取队首元素:

1. int front(Queue *q, int *value) {
2. if (isEmpty(q)) {
3. printf("Queue is empty!\n");
4. return 0;
5. }
6. *value = q->front->data;
7. return 1;
8. }

复制代码

4.7 获取队尾元素:

1. int rear(Queue *q, int *value) {
2. if (isEmpty(q)) {
3. printf("Queue is empty!\n");
4. return 0;
5. }
6. *value = q->rear->data;
7. return 1;
8. }

复制代码

5. 完整示例 (链表实现):

1. #include <stdio.h>
2. #include <stdlib.h>
4. // ... (链表实现的结构体定义和函数) ...
6. int main() {
7. Queue q;
8. initQueue(&q);
10. enqueue(&q, 10);
11. enqueue(&q, 20);
12. enqueue(&q, 30);
14. int value;
15. if (front(&q, &value)) {
16. printf("Front element: %d\n", value);
17. }
18. if (rear(&q, &value)) {
19. printf("Rear element: %d\n", value);
20. }
22. while (!isEmpty(&q)) {
23. if (dequeue(&q, &value)) {
24. printf("Dequeued element: %d\n", value);
25. }
26. }
28. return 0;
29. }

复制代码

6. 数组实现 vs 链表实现:

特性	数组实现 (顺序队列)	链表实现 (链式队列)
内存分配	静态分配	动态分配
空间利用率	可能浪费空间	更有效利用空间
插入/删除	可能需要移动元素	效率更高
大小限制	固定大小	大小可变
实现复杂度	相对简单	相对复杂

总结:

• 数组实现: 简单，但受限于预定义的大小，可能导致空间浪费或溢出。
• 链表实现: 灵活，可以动态调整大小，空间利用率高，插入和删除操作效率更高，但实现相对复杂，需要处理指针。

选择哪种实现方式取决于具体应用场景的需求。如果队列大小已知且固定，