Linux环境下的C语言编程（三十九）

三、队列的基本操作（接三十八）

1. 基本数据结构定义

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 // 队列最大容量 // 队列结构体定义 typedef struct { int data[MAX_SIZE]; // 存储数据的数组 int front; // 队头指针 int rear; // 队尾指针 int size; // 当前队列大小 } Queue;

二、队列基本操作实现

1. 初始化队列

// 初始化队列 void initQueue(Queue* q) { q->front = 0; // 队头指针初始化为0 q->rear = -1; // 队尾指针初始化为-1（表示空队列） q->size = 0; // 队列大小为0 }

2. 判断队列是否为空

// 检查队列是否为空 bool isEmpty(Queue* q) { // 方法1：使用size变量 return q->size == 0; // 方法2：使用front和rear指针（循环队列） // return (q->front == (q->rear + 1) % MAX_SIZE); }

3. 判断队列是否已满

// 检查队列是否已满 bool isFull(Queue* q) { // 方法1：使用size变量 return q->size == MAX_SIZE; // 方法2：使用front和rear指针（循环队列） // return ((q->rear + 2) % MAX_SIZE == q->front); }

4. 入队操作

// 将元素添加到队列尾部 bool enqueue(Queue* q, int value) { if (isFull(q)) { printf("错误：队列已满，无法添加元素 %d\n", value); return false; // 入队失败 } // 移动rear指针（循环队列） q->rear = (q->rear + 1) % MAX_SIZE; // 在rear位置插入元素 q->data[q->rear] = value; // 队列大小增加 q->size++; printf("成功入队: %d (位置: %d)\n", value, q->rear); return true; // 入队成功 }

5. 出队操作

// 从队列头部移除元素 bool dequeue(Queue* q, int* value) { if (isEmpty(q)) { printf("错误：队列为空，无法移除元素\n"); return false; // 出队失败 } // 获取队头元素 *value = q->data[q->front]; // 移动front指针（循环队列） q->front = (q->front + 1) % MAX_SIZE; // 队列大小减少 q->size--; printf("成功出队: %d (新队头位置: %d)\n", *value, q->front); return true; // 出队成功 }

6. 查看队头元素

// 获取队头元素但不移除 bool peekFront(Queue* q, int* value) { if (isEmpty(q)) { printf("错误：队列为空，无队头元素\n"); return false; } *value = q->data[q->front]; printf("队头元素: %d\n", *value); return true; }

7. 查看队尾元素

// 获取队尾元素但不移除 bool peekRear(Queue* q, int* value) { if (isEmpty(q)) { printf("错误：队列为空，无队尾元素\n"); return false; } *value = q->data[q->rear]; printf("队尾元素: %d\n", *value); return true; }

8. 获取队列大小

// 返回队列中元素的数量 int getSize(Queue* q) { return q->size; // 如果不使用size变量，可以用以下公式计算： // return (q->rear - q->front + MAX_SIZE) % MAX_SIZE + 1; }

9. 清空队列

// 清空队列中的所有元素 void clearQueue(Queue* q) { q->front = 0; q->rear = -1; q->size = 0; printf("队列已清空\n"); }

三、完整的队列操作示例

// 打印队列内容 void printQueue(Queue* q) { if (isEmpty(q)) { printf("队列为空\n"); return; } printf("队列内容 (从队头到队尾): "); if (q->front <= q->rear) { // 正常情况：front <= rear for (int i = q->front; i <= q->rear; i++) { printf("%d ", q->data[i]); } } else { // 循环情况：rear < front for (int i = q->front; i < MAX_SIZE; i++) { printf("%d ", q->data[i]); } for (int i = 0; i <= q->rear; i++) { printf("%d ", q->data[i]); } } printf("\n"); } // 显示队列状态 void displayQueueStatus(Queue* q) { printf("\n=== 队列状态 ===\n"); printf("队头位置: %d\n", q->front); printf("队尾位置: %d\n", q->rear); printf("队列大小: %d\n", getSize(q)); printf("队列容量: %d\n", MAX_SIZE); printf("是否为空: %s\n", isEmpty(q) ? "是" : "否"); printf("是否已满: %s\n", isFull(q) ? "是" : "否"); printQueue(q); } // 主函数：测试队列基本操作 int main() { Queue myQueue; int value; printf("=== 队列基本操作演示 ===\n"); // 1. 初始化队列 printf("\n1. 初始化队列\n"); initQueue(&myQueue); displayQueueStatus(&myQueue); // 2. 入队操作 printf("\n2. 入队操作演示\n"); printf("入队元素: 10, 20, 30, 40, 50\n"); enqueue(&myQueue, 10); enqueue(&myQueue, 20); enqueue(&myQueue, 30); enqueue(&myQueue, 40); enqueue(&myQueue, 50); displayQueueStatus(&myQueue); // 3. 查看队头和队尾 printf("\n3. 查看队头和队尾\n"); peekFront(&myQueue, &value); peekRear(&myQueue, &value); // 4. 出队操作 printf("\n4. 出队操作演示\n"); dequeue(&myQueue, &value); printf("出队元素: %d\n", value); dequeue(&myQueue, &value); printf("出队元素: %d\n", value); displayQueueStatus(&myQueue); // 5. 获取队列大小 printf("\n5. 获取队列大小\n"); printf("当前队列大小: %d\n", getSize(&myQueue)); // 6. 继续入队 printf("\n6. 继续入队操作\n"); printf("入队元素: 60, 70, 80\n"); enqueue(&myQueue, 60); enqueue(&myQueue, 70); enqueue(&myQueue, 80); displayQueueStatus(&myQueue); // 7. 批量出队 printf("\n7. 批量出队直到队列为空\n"); while (!isEmpty(&myQueue)) { dequeue(&myQueue, &value); printf("出队: %d, 剩余大小: %d\n", value, getSize(&myQueue)); } displayQueueStatus(&myQueue); // 8. 测试边界情况 printf("\n8. 测试边界情况\n"); printf("从空队列出队: "); dequeue(&myQueue, &value); // 应该失败 printf("查看空队列的队头: "); peekFront(&myQueue, &value); // 应该失败 // 9. 清空队列 printf("\n9. 清空队列\n"); clearQueue(&myQueue); displayQueueStatus(&myQueue); return 0; }

3. 操作的正式定义

四、状态转换图

初始状态 ↓ [空队列] (isEmpty = true) ↓ Enqueue(x) [队列: x] (size = 1) ↓ Enqueue(y) [队列: x ← y] (size = 2) ↓ Dequeue() → 返回x [队列: y] (size = 1) ↓ Dequeue() → 返回y [空队列] (isEmpty = true) ↓ Dequeue() [错误/异常：队列为空]

五、关键特性总结