3、FIFO数据结构设计：数组实现FIFO、链表实现FIFO、环形缓冲区设计

好，咱们今天聊聊FIFO的数据结构设计。说白了，FIFO就是「先进先出」——你第一个放进去的数据，必须第一个被取出来。这个逻辑在缓存系统里太常见了，比如CPU的指令队列、网络数据包的收发缓冲，甚至你手机里App的消息推送，背后都有它的影子。

我个人习惯把FIFO的实现分成三大类：数组实现、链表实现和环形缓冲区。每种方案都有自己的脾气，选错了后面调试起来会非常痛苦。我当年刚入行时，就因为选错了实现方式，导致一个嵌入式项目里的数据丢包，排查了整整两天……嗯，咱们今天就把这些坑提前填上。

3.1 数组实现FIFO：简单直接，但小心「假溢出」

数组实现FIFO，是最直观的思路。你定义一个固定大小的数组，再用两个指针（或者索引）分别指向「队头」和「队尾」。

• 入队：数据放到队尾指针的位置，队尾指针+1。
• 出队：从队头指针的位置取数据，队头指针+1。

听起来很简单对吧？但这里有个大坑——假溢出。什么意思？你想想看，如果队尾指针已经指到了数组的最后一个位置，但队头指针还在前面，数组前面其实空着很多位置。这时候再入队，程序会告诉你「满了」，但实际上空间是有的。这就是假溢出。

数组实现的优点很明显：内存连续，访问速度快。缺点也突出：大小固定，无法动态扩展。如果你能预估数据量的上限，数组方案是最稳的。

// 数组实现FIFO的简化示例（C语言风格）
#define FIFO_SIZE 64
typedef struct {
    int data[FIFO_SIZE];
    int head;  // 队头索引
    int tail;  // 队尾索引
    int count; // 当前元素个数
} ArrayFIFO;

// 入队
int enqueue(ArrayFIFO *fifo, int value) {
    if (fifo->count >= FIFO_SIZE) return -1; // 满
    fifo->data[fifo->tail] = value;
    fifo->tail = (fifo->tail + 1) % FIFO_SIZE; // 取模防止越界
    fifo->count++;
    return 0;
}

// 出队
int dequeue(ArrayFIFO *fifo, int *value) {
    if (fifo->count <= 0) return -1; // 空
    *value = fifo->data[fifo->head];
    fifo->head = (fifo->head + 1) % FIFO_SIZE;
    fifo->count--;
    return 0;
}

3.2 链表实现FIFO：灵活但开销大

链表实现FIFO，说白了就是每个节点里存数据，再加一个指向下一个节点的指针。入队时在链表尾部插入，出队时从链表头部删除。

这种方案的好处是动态分配内存，理论上可以无限扩展（只要内存够）。我在做一个网络协议栈的缓存层时，就用了链表FIFO——因为网络数据包的大小和数量都不固定，用数组根本没法预估。

但缺点也很要命：每个节点都有额外的指针开销（通常8字节或16字节），而且内存不连续，CPU缓存命中率低。你想想看，如果数据量很大，频繁的malloc和free会导致内存碎片，系统跑久了可能就分配不出内存了。

// 链表实现FIFO的简化示例
typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *head; // 队头
    Node *tail; // 队尾
    int size;   // 当前节点数
} LinkedFIFO;

// 入队
void enqueue(LinkedFIFO *fifo, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if (fifo->tail == NULL) {
        fifo->head = fifo->tail = newNode;
    } else {
        fifo->tail->next = newNode;
        fifo->tail = newNode;
    }
    fifo->size++;
}

// 出队
int dequeue(LinkedFIFO *fifo, int *value) {
    if (fifo->head == NULL) return -1;
    Node *temp = fifo->head;
    *value = temp->data;
    fifo->head = temp->next;
    if (fifo->head == NULL) fifo->tail = NULL;
    free(temp);
    fifo->size--;
    return 0;
}

3.3 环形缓冲区：工程中最常用的方案

环形缓冲区，也叫循环队列。它本质上还是数组，但通过取模运算让队尾指针绕回数组开头，完美解决了假溢出问题。你想想看，数组就像一个圆环，头尾相连，空间利用率100%。

我做过一个高速数据采集系统，ADC每秒产生几百万个采样点。用环形缓冲区，配合DMA直接写入，CPU只需要在缓冲区半满时去读数据——效率极高。这种方案在嵌入式、音视频处理、网络驱动里几乎是标配。

环形缓冲区的核心设计要点有两个：

• 判空判满：常见做法是「空：head == tail；满：(tail + 1) % size == head」。注意，这里会浪费一个元素空间来区分空和满。
• 读写指针的原子性：在多线程或多任务环境下，要保证head和tail的更新不被中断。我一般用关中断或者CAS操作来处理。

// 环形缓冲区实现（单生产者单消费者，无需锁）
#define RING_SIZE 16  // 必须是2的幂，方便取模优化
typedef struct {
    int buffer[RING_SIZE];
    volatile int head;  // 读指针
    volatile int tail;  // 写指针
} RingBuffer;

// 入队
int ring_enqueue(RingBuffer *rb, int value) {
    int next_tail = (rb->tail + 1) & (RING_SIZE - 1); // 位运算代替取模
    if (next_tail == rb->head) return -1; // 满
    rb->buffer[rb->tail] = value;
    rb->tail = next_tail;
    return 0;
}

// 出队
int ring_dequeue(RingBuffer *rb, int *value) {
    if (rb->head == rb->tail) return -1; // 空
    *value = rb->buffer[rb->head];
    rb->head = (rb->head + 1) & (RING_SIZE - 1);
    return 0;
}

三种方案对比

知识体系结构图

下面这张图，帮你理清三种FIFO实现的核心逻辑和选择路径。

好了，三种FIFO实现方案就聊到这儿。我个人最推荐环形缓冲区——它兼顾了数组的速度和链表的灵活性，是工程实践中的「万金油」。当然，具体选哪个，还得看你的项目场景。嗯，记住一点：没有最好的方案，只有最合适的方案。

可可精品资料库