解读环形队列-C语言实现

环形队列（Circular Queue）是一种特殊的队列数据结构。与普通的线性队列不同，环形队列在物理存储上表现为一个首尾相连的环状结构，在逻辑上则仍然遵循先进先出（FIFO）的原则。

特点

  1. 循环利用空间：当队列中的元素被删除后，原来的空间可以被重新使用
  2. 队头队尾指针：使用head和end两个指针标识队列的头部和尾部
  3. 队满与队空判断：需要特殊处理，通常预留一个位置不使用
  4. 动态调整：可以动态调整数组大小来适应数据量变化

应用场景

  • 缓冲区管理：在网络编程或硬件驱动程序中管理固定大小的缓冲区
  • 生产者消费者模型：在多线程环境中用作数据共享的数据结构
  • 滑动窗口算法：实现高效的数据处理策略
  • 串口接收：STM32中常用于串口接收，实现数据异步使用

图解

非循环队列

非循环队列由一个头指针head和一个尾指针end构成。

入队操作：

入队

end = end + 1，然后将数据存入end指向的空间：

入队2

出队操作：

出队

出队就是将head指向空间的数据抛出，然后head加一：

出队2

判断队空：

  • end = -1 表示队空
  • end + 1 = head 表示队空

队空 队空2 队空3

判断队满：end + 1 = MAX_SIZE

队满 队满2

循环队列

循环队列的head指针并不指向数据头，而是指向上一次被删除的数据地址。

下标范围控制：

end = (end+1) % MAX_SIZE
head = (head+1) % MAX_SIZE

入队操作：

循环队列入队

出队操作：

循环队列出队

判断队满：head = (end+1) % MAX_SIZE

循环队队满 循环队队满2

判断队空：head == end

队空条件同样适用于循环后的情况：

循环队队空 循环队队空2 循环队队空3 循环队队空4

C语言实现

定义环形FIFO数据结构

#define Max_Size (10)

typedef struct {
    uint32_t head;    // 头指针
    uint32_t end;     // 尾指针
    uint8_t data[Max_Size];
} Fifo_t;

初始化函数

void FifoInit(Fifo_t *f) {
    f->end = 0;
    f->head = 0;
}

判断队列空函数

uint8_t isEmpty(Fifo_t *f) {
    return (f->end == f->head);
}

判断队列满函数

uint8_t isFull(Fifo_t *f) {
    return ((f->end + 1) % Max_Size == f->head);
}

入队函数

uint32_t FifoIn(Fifo_t *f, uint8_t *in, uint32_t len) {
    uint32_t i;
    for (i = 0; i < len; i++) {
        if (isFull(f)) {
            return 0;
        }
        f->end = (f->end + 1) % Max_Size;
        f->data[f->end] = in[i];
    }
    return i;
}

出队函数

uint8_t FifoOut(Fifo_t *f, uint8_t *out, uint32_t len) {
    uint32_t i;
    for (i = 0; i < len; i++) {
        if (isEmpty(f)) {
            return 0;
        }
        f->head = (f->head + 1) % Max_Size;
        out[i] = f->data[f->head];
    }
    return i;
}

完整源码

#include "stdio.h"
#include "stdint.h"

#define Max_Size (10)

typedef struct {
    uint32_t head;
    uint32_t end;
    uint8_t data[Max_Size];
} Fifo_t;

void FifoInit(Fifo_t *f) {
    f->end = 0;
    f->head = 0;
}

uint8_t isEmpty(Fifo_t *f) {
    return (f->end == f->head);
}

uint8_t isFull(Fifo_t *f) {
    return ((f->end + 1) % Max_Size == f->head);
}

uint32_t FifoIn(Fifo_t *f, uint8_t *in, uint32_t len) {
    uint32_t i;
    for (i = 0; i < len; i++) {
        if (isFull(f)) {
            return 0;
        }
        f->end = (f->end + 1) % Max_Size;
        f->data[f->end] = in[i];
    }
    return i;
}

uint8_t FifoOut(Fifo_t *f, uint8_t *out, uint32_t len) {
    uint32_t i;
    for (i = 0; i < len; i++) {
        if (isEmpty(f)) {
            return 0;
        }
        f->head = (f->head + 1) % Max_Size;
        out[i] = f->data[f->head];
    }
    return i;
}

总结

环形队列有效地解决了普通队列空间浪费的问题，特别适合嵌入式系统中需要固定大小缓冲区的场景，如串口数据接收、网络通信等。