嵌入式算法14---数据流与环形队列

摘要：对生产-消费模型的数据处理，使用环形队列管理，提高内存利用率。

1、应用场景

所谓生产-消费模型，即数据的产生和利用是异步处理，先”生产“了，然后才有”消费“。对嵌入式系统一般是数据接收与解析，数据缓存与发送。因为时序或者空间要求，两者需要异步处理；对于这种数据流，采用环形队列，先进先出的方式保存。

2、环形队列

队列是一种常用的数据结构，按照“先进先出”的原则进行操作的，环形队列是数据元素存储一轮后，再从头部开始入队，首尾相接，是一个装载固定数量元素的闭环。

typedef struct
{
    uint8_t data[RING_FIFO_SIZE];
    uint8_t head;
    uint8_t tail;
} ring_fifo_struct;

其最简形势如上，data为数据缓冲区，head和tail分别表示出队索引和入队索引。即数据入队在tail后追加，出队从head取。

初始状态下队列为空，head和tail相等，存满的情况下两者也相等，为了区分，只能少存一个，即再存一个为队满时提前认为已满。

具体动画效果如下：

3、源码

#include "stdio.h"
#include "string.h"

typedef signed char     int8_t;
typedef unsigned char   uint8_t;
typedef unsigned short  uint16_t;

#define RING_FIFO_SIZE  5

#define RING_FIFO_OK    0
#define RING_FIFO_FULL  -1
#define RING_FIFO_EMPTY  -2

typedef struct
{
    uint8_t data[RING_FIFO_SIZE];
    uint8_t head;
    uint8_t tail;
} ring_fifo_struct;

static ring_fifo_struct ring_fifo = {0};

//入队
int8_t ring_fifo_push(uint8_t value)
{
    uint8_t fake_tail;
    if(ring_fifo.tail == (RING_FIFO_SIZE - 1))
    {
        fake_tail = 0;
    }
    else
    {
        fake_tail = ring_fifo.tail + 1;
    }

    if(fake_tail == ring_fifo.head)
    {
        return RING_FIFO_FULL;//队列满禁止继续入队
    }

    ring_fifo.data[ring_fifo.tail] = value;

    ring_fifo.tail++;

    if(ring_fifo.tail == RING_FIFO_SIZE)
    {
        ring_fifo.tail = 0;
    }
    return RING_FIFO_OK;
}

//出队
int8_t ring_fifo_pop(uint8_t *value)
{
    if(ring_fifo.head == ring_fifo.tail)
    {
        return RING_FIFO_EMPTY;
    }

    *value = ring_fifo.data[ring_fifo.head];

    ring_fifo.head++;
    if(ring_fifo.head == RING_FIFO_SIZE)
    {
        ring_fifo.head = 0;
    }
    return RING_FIFO_OK;
}


int main(void)
{
    uint8_t i, value;
    int8_t ret;

    for(i = 0; i < 6; i++)
    {
        ret = ring_fifo_push(i);
        printf("[%d] ret=%d,push=%d\r\n", i,ret,i);
    }

    for(i = 0; i < 6; i++)
    {
        ret = ring_fifo_pop(&value);
        printf("[%d] ret=%d,pop=%d\r\n", i,ret,value);
        if(ret == RING_FIFO_EMPTY)
        {
            break;
        }
    }

    return 0;
}

运行结果如下：

[0] ret=0,push=0
[1] ret=0,push=1
[2] ret=0,push=2
[3] ret=0,push=3
[4] ret=-1,push=4   
[5] ret=-1,push=5  //存储空间为5，实际存4个即为队满，是为了和队空进行区分

[0] ret=0,pop=0   //0最先入队，也会最先出队
[1] ret=0,pop=1
[2] ret=0,pop=2
[3] ret=0,pop=3
[4] ret=-2,pop=3

4、总结

掌握基础的思路，万变不离其宗，范例只是提供思路，而且只是针对低端单片机。对于硬件资源丰富、功能复杂的应用，可对接口进行一定的扩展。

对存储的数据体可以进行封装，对于缓存区的大小，视具体需求，尽量保证队列不要存满，以免数据丢失；对存储下标的计算可以参考动画中的表示方法。

若设备支持分时操作系统，对环形队列进行操作前，先进入临界区或者使用互斥量进行管控。