c语言数据结构实现-数组队列/环形队列-白红宇

c语言数据结构实现-数组队列/环形队列

阅读量：4138 次

发布时间：2019-05-25

本文共 2342 字，大约阅读时间需要 7 分钟。

一、背景需求

应用场景是一个生产者一个消费者，两者平均处理速度是相当的，但是有生产峰值速度太快，消费者处理速度跟不上的情况；

这种场景若用单线程处理，则会出现消费速度慢导致拖慢生产者的速度；

若使用双线程处理，一个生产线程一个消费线程，这个时候就能用到队列/环形队列了。

二、相关知识

队列的数据结构其实非常简单，实现方式主要为动态的链式结构或者为静态的数组结构，本文介绍一种静态的数组结构；

如上

图所示，入列时插入队列尾，出列时由队列头弹出，用下标值进行位置标识。

约束是用户数据必须是定长的数据，才能用静态数组结构去标识。

三、实现

创建队列，需要确定队列大小以及每个用户数据的长度

int bufqueue_create(bufqueue_t *phead, size_t nmemb, size_t item_size){    int ix = 0;    if ( !phead ) {        return FAILURE;    }#define __ISPOWER(_num_) ((_num_ ^ (_num_ - 1)) == (((_num_ - 1) << 1) + 1))    if ( !__ISPOWER(nmemb) ) {        return FAILURE;    }    /* Refree queue */    FREE_POINTER(phead->queue);    phead->queue = (bufqueue_item *)calloc(nmemb, sizeof(bufqueue_item));    if ( !phead->queue ) {        return FAILURE;    }    for ( ix = 0; ix < nmemb; ix++ ) {        phead->queue[ix].pitem = calloc(1, item_size);        if ( !phead->queue[ix].pitem ) {            return FAILURE;        }    }    phead->item_size = item_size;    phead->size = nmemb;    phead->mask = nmemb - 1;    phead->head = 0;    phead->tail = 0;    phead->used = 0;    printf("Queue alloc success, size: %zd ( Bytes )\n",            sizeof(bufqueue_t) + nmemb * item_size);    return SUCCESS;}

入列操作，分为获取队列尾，返回数据的指针给生成者，生产者生产数据后，更新队列尾操作

void* bufqueue_tail(bufqueue_t *phead){    if ( SUCCESS == bufqueue_isfull(phead) ) {        return NULL;    }    return (phead->queue[phead->tail].pitem);}

int bufqueue_push(bufqueue_t *phead){    phead->used++;    phead->tail = (phead->tail + 1) & phead->mask;    return SUCCESS;}

出列，消费者调用该接口直接获取到数据指针，注意外部并不需要释放空间

void* bufqueue_pop(bufqueue_t *phead){    void *pitem = NULL;    if ( phead->tail == phead->head ) {        return NULL;    }    pitem = phead->queue[phead->head].pitem;    phead->head = (phead->head + 1) & phead->mask;    phead->used--;    return (pitem);}

判定队列是否为空

int bufqueue_isempty(bufqueue_t *phead){    if ( phead->tail == phead->head ) {        return SUCCESS;    }    return FAILURE;}

判断队列是否满

int bufqueue_isfull(bufqueue_t *phead){    if ( !phead ) {        return FAILURE;    }    if ( phead->head == ((phead->tail + 1) & phead->mask) ) {        /* Queue is full */        return SUCCESS;    }    return FAILURE;}

四、小结

使用数组队列类似于牺牲空间换时间的方法，实现简单。但要求用户数据必须定长，并且会出现队列满的情况；

但是在索引方面，由于使用了下标法进行定位，可以快速地查找到下一个元素（head=(head + 1)&mask），这个时候也必须保证队列大小为2^N；

同时在一个生产者一个消费者的场景下，使用该队列可以无需上锁，节省锁的开销；

你可能感兴趣的文章