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

发布于:2025-02-10 ⋅ 阅读:(98) ⋅ 点赞:(0)

原理

队列是一种 先进先出(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)。


网站公告

今日签到

点亮在社区的每一天
去签到