队列Queue原理及其C语言实现

原理

队列是一种 先进先出（FIFO, First In First Out） 的线性数据结构，操作限制在两端：

• 队尾（Rear）：仅允许插入元素（入队，enqueue）。

• 队头（Front）：仅允许删除元素（出队，dequeue）。

队列的底层可通过 数组 或 链表 实现。数组实现需处理固定大小和循环利用（避免空间浪费），链表实现则动态扩展。

对列操作示意

1. 初始状态
   Front = -1, Rear = -1
   +---+---+---+---+---+
   |   |   |   |   |   |
   +---+---+---+---+---+

2. 入队元素 A
   Front = 0, Rear = 0
   +---+---+---+---+---+
   | A |   |   |   |   |
   +---+---+---+---+---+

3. 入队元素 B、C
   Front = 0, Rear = 2
   +---+---+---+---+---+
   | A | B | C |   |   |
   +---+---+---+---+---+

4. 出队元素 A
   Front = 1, Rear = 2
   +---+---+---+---+---+
   |   | B | C |   |   |
   +---+---+---+---+---+

5. 循环队列（数组满后复用空间）
   Front = 1, Rear = 0
   +---+---+---+---+---+
   | D | B | C | E | F | → Rear 回到索引 0（循环）
   +---+---+---+---+---+

应用场景

1. 任务调度：操作系统按顺序处理进程请求。

2. 消息队列：异步通信系统中缓冲消息（如 RabbitMQ）。

3. 打印机任务：按提交顺序打印文件。

4. 广度优先搜索（BFS）：遍历树或图的节点层级。

5. 实时系统：事件按发生顺序处理（如键盘输入缓冲）。

C语言代码实现

//1. 定义队列结构
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 5

typedef struct Queue {
    int data[MAX_SIZE];
    int front;  // 队头索引
    int rear;   // 队尾索引
} Queue;

//2. 初始化队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    if (!queue) {
        printf("内存分配失败！\n");
        exit(1);
    }
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

//3. 基本操作实现
// 判空
int isEmpty(Queue* queue) {
    return queue->front == -1;
}

// 判满
int isFull(Queue* queue) {
    return (queue->rear + 1) % MAX_SIZE == queue->front;
}

// 入队
void enqueue(Queue* queue, int value) {
    if (isFull(queue)) {
        printf("队列已满，无法入队！\n");
        return;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->rear = (queue->rear + 1) % MAX_SIZE;
    queue->data[queue->rear] = value;
}

// 出队
int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队！\n");
        return -1;
    }
    int value = queue->data[queue->front];
    if (queue->front == queue->rear) {
        // 队列只剩一个元素，重置指针
        queue->front = queue->rear = -1;
    } else {
        queue->front = (queue->front + 1) % MAX_SIZE;
    }
    return value;
}

// 查看队头
int peek(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空！\n");
        return -1;
    }
    return queue->data[queue->front];
}

// 打印队列
void printQueue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空！\n");
        return;
    }
    int i = queue->front;
    printf("队列元素: ");
    do {
        printf("%d ", queue->data[i]);
        i = (i + 1) % MAX_SIZE;
    } while (i != (queue->rear + 1) % MAX_SIZE);
    printf("\n");
}

/* ---------- 应用示例：模拟银行叫号系统 ---------- */
int main() {
    Queue* queue = createQueue();  // 创建容量为5的队列

    // 客户取号
    enqueue(queue, 101);
    enqueue(queue, 102);
    enqueue(queue, 103);
    printQueue(queue);  // 输出: 101 102 103

    // 柜员处理客户
    printf("正在处理: %d\n", dequeue(queue));  // 输出 101
    printf("下一个客户: %d\n", peek(queue));    // 输出 102

    // 新客户继续取号
    enqueue(queue, 104);
    enqueue(queue, 105);
    enqueue(queue, 106);  // 触发队列已满提示
    printQueue(queue);    // 输出: 102 103 104 105

    return 0;
}

 实现方式对比

 总结

• 核心特性：先进先出，操作受限（仅队头出队、队尾入队）。

• 时间复杂度：入队、出队、查看队头均为 O(1)。

• 适用场景：需按顺序处理任务的场景（如调度、缓冲、BFS）。