[C++知识库]C语言构建环形缓冲区

它逻辑上是一个首尾相连的FIFO结构，具体实现上采用简单的线性数组。通过额外的辅助标志（head、tail）能很快知道队列的使用情况（是满还是为空）。正因为其简单高效的原因，甚至在硬件都实现了环形队列。

环形队列广泛用于网络数据收发、程序间的大量数据交换（比如内核与应用程）、硬件接收大量数据。

1、环形缓冲区原理

• 环列队列逻辑上将数组元素array[0]与array[LEN-1]连接起来，形成一个存放队列的环形空间。实际操作中为了方便读写，采用head和tail分别指向可以读的位置和可以写的位置。
• 环形队列的关键是判断队列为空，还是为满。一般有两种方法：
  • 一是附加一个标志位tag
  • 当head赶上tail，队列空，则令tag=0
  • 当tail赶上head，队列满，则令tag=1
  • 二是在队尾结点与队首结点之间留有1个元素的空间
    • 队列空： head==tail
    • 队列满： (tail+1)% MAXN ==head

2、预留1个空位的环形队列

• 开始时head和tail指向同一个地址，但随着数据的push和poll，head和tail之间永远预留一个单元空间。如下图所示即为一个满队列。但箭头所指的位置不准确。tail应该指向空位，head指向9。即从头出去，从尾巴进来。

• 数据结构：

struct ring_queue{  
    unsigned int head;   
    unsigned int tail;  
    unsigned int size; 	//环形缓冲区容量
    int *array;   		//实际缓冲区（数组）的首地址
}; 

• 规则：
  • head指向可读位置（地址存有数据），tail指向可写位置（地址无数据）。
  • 初始化状态: head = tail = 0;
  • 判定队列为空：head == tail
  • 队列为满：**（ (tail+1) % SIZE ) == head **
  • 入队操作：若队列不满，则写入。
  • 出队操作：若队列不空，则读出。
  • 缓冲区必须是连续的内存空间，可以通过静态数组变量或局部数组变量的方式定义，但绝不能从堆上分配（malloc），因为malloc分配的内存空间是不连续的！！！
• 头文件：

#ifndef __RINGQ_H__
#define __RINGQ_H__

#ifdef __cplusplus
extern "C" {
#endif

    
typedef struct {  
    unsigned int head;   
    unsigned int tail;
    unsigned int size;
    int *array;   
}RINGQ;    

#define ringq_is_empty(q) (q->head == q->tail)
#define ringq_is_full(q) (((q->tail+1)%q->size) == q->head )

int ringq_init(RINGQ * ringqp, int * array_ptr, unsigned size);
int ringq_free(RINGQ * ringqp);
int ringq_push(RINGQ * ringqp,int data);
int ringq_poll(RINGQ * ringqp,int * val);
void ringq_display(RINGQ * ringqp);

#ifdef __cplusplus
}
#endif

#endif

• c文件：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include "ringq.h"
  4 
  5 int ringq_init(RINGQ * ringqp, int * array_ptr, unsigned size)
  6 {
  7     /*
  8        不能从堆里分配空间！！！
  9        因为堆里的空间不是连续的，而是通过链表链接的一个空间串
 10     if(!(ringqp->array = (int *)malloc(size))){
 11         printf("Malloc failed!\n");
 12        return -1;
 13     }
 14     */
 15     ringqp->array = array_ptr;
 16     ringqp->size = size;
 17     ringqp->head = 0;
 18     ringqp->tail = 0;
 19     return 0;
 20 }
 21 
 22 int ringq_free(RINGQ * ringqp)
 23 {
 24     free(ringqp->array);
 25     return 0;
 26 }
 27 
 28 
 29 int ringq_push(RINGQ * ringqp,int data)
 30 {
 31     if(ringq_is_full(ringqp))
 32     {
 33         printf("ringq is full.\n");
 34         return -2;
 35     }
 36     ringqp->array[ringqp->tail] = data;
 37     ringqp->tail = (ringqp->tail + 1) % ringqp->size ;
 38     return 0;
 39 }
 40 
 41 
 42 int ringq_poll(RINGQ * ringqp,int * val)
 43 {
 44    if(ringq_is_empty(ringqp))
 45     {
 46         printf("ringq is empty.\n");
 47         return -3;
 48     }
 49     *val = ringqp->array[ringqp->head];
 50     ringqp->head = (ringqp->head + 1) % ringqp->size ;
 51     return 0;
 52 }
 53 
 54 void ringq_display(RINGQ * ringqp)
 55 {
 56     int  i =0;
 57     unsigned head = ringqp->head;
 58     unsigned tail = ringqp->tail;
 59     unsigned size = ringqp->size;
 60 
 61     if(ringq_is_empty(ringqp))
 62     {
 63         printf("ringq is empty.\n");
 64         return;
 65     }
 66     while(head != tail){
 67         printf("%04d ",ringqp->array[head]);
 68         i++;
 69         if(i == 5){
 70             printf("\n");
 71             i = 0;
 72         }
 73         head = (head + 1)%(size);
 74     }
 75     printf("\n");
 76     return;
 77 }

• 测试文件：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include "ringq.h"
  4 
  5 #define RQ_SIZE 50 
  6 
  7 int main(void)
  8 {
  9     int data_in = 0;
 10     int data_out = 0;
 11     int select = 0;
 12 
 13     int array[RQ_SIZE]={};
 14     RINGQ rq, *rqp;
 15     rqp = &rq;
 16 
 17     ringq_init(rqp, array, RQ_SIZE);
 18     ringq_display(rqp);
 19 
 20     int index = RQ_SIZE - 1;    //allways a bank between head and tail
 21     while (index > 0){
 22         ringq_push(rqp,1);
 23         index -= 1;
 24     }
 25 
 26     ringq_display(rqp);
 27 
 28     while (index < RQ_SIZE-1){
 29         ringq_poll(rqp,&data_out);
 30         index += 1;
 31     }
 32 
 33     ringq_display(rqp);
 34 
 35     while (index > 0){
 36         ringq_push(rqp,2);
 37         index -= 1;
 38     }
 39 
 40     ringq_display(rqp);
 41     
 42    return 0;
 43 }

• 实验结果：

• 测试文件2

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include "ringq.h"
  4 
  5 #define RQ_SIZE 5 
  6 
  7 int main(void)
  8 {
  9     int data_in = 0;
 10     int data_out = 0;
 11     int select = 0;
 12 
 13     int array[RQ_SIZE]={};
 14     RINGQ rq, *rqp;
 15     rqp = &rq;
 16 
 17     ringq_init(rqp, array, RQ_SIZE);
 18     ringq_display(rqp);
 19       
 42 
 43 loop:  puts("push or poll or quit? [i/o/q]");
 44     select = getchar();
 45     getchar();  //丢弃回车
 46     switch(select){
 47         case 'i':
 48             printf("The push data is:");
 49             scanf("%d",&data_in);
 50             getchar();  //丢弃回车
 51             ringq_push(rqp, data_in);
 52             break;
 53         case 'o':
 54             ringq_poll(rqp, &data_out);
 55             printf("%d poll successfull.\n",data_out);
 56             break;
 57         case 'q':
 58             
 59             return 0;
 60         default:
 61             printf("Wrong choice!enter i or o!\n");
 62     }
 63     ringq_display(rqp);
 64     printf("\n");
 65     goto loop;
 66 }

• 实验结果：

• 有关getchar()和输入缓冲区的关系，请查看一文搞懂getchar()和putchar()的奇怪现象_Leon的博客-CSDN博客或者C语言 getchar()原理及易错点解析_Kevin.wang-CSDN博客_c语言getchar

3、附加满空标志位的环形队列

• 数据结构

typedef struct ringq{
   int head;
   int tail;
   int tag ;
   int size ;
   int space[RINGQ_MAX];

}RINGQ;

• 规则
  • 初始化状态: q->head = q->tail = q->tag = 0;
  • 队列为空:(q->head == q->tail) && (q->tag == 0)
  • 队列为满**: ((q->head == q->tail) && (q->tag == 1))**
  • 入队操作:如队列不满，则写入q->tail = (q->tail + 1) % q->size ;
  • 出队操作：如果队列不空，则从head处读出。下一个可读的位置在 q->head = (q->head + 1) % q->size
• 头文件

#ifndef __RINGQ_H__
#define __RINGQ_H__

#ifdef __cplusplus
extern "C" {
#endif

#define QUEUE_MAX 20
typedef struct ringq{
   int head;
   int tail;
   int tag ;
    int size ;
   int space[QUEUE_MAX];
}RINGQ;


extern int ringq_init(RINGQ * p_queue);
extern int ringq_free(RINGQ * p_queue);
extern int ringq_push(RINGQ * p_queue,int data);
extern int ringq_poll(RINGQ * p_queue,int *p_data);
#define ringq_is_empty(q) ( (q->head == q->tail) && (q->tag == 0))
#define ringq_is_full(q) ( (q->head == q->tail) && (q->tag == 1))
#define print_ringq(q) printf("ring head %d,tail %d,tag %d\n", q->head,q->tail,q->tag);
#ifdef __cplusplus
}
#endif

#endif

• 实现代码

#include <stdio.h>
#include "ringq.h"

int ringq_init(RINGQ * p_queue)
{
   p_queue->size = QUEUE_MAX ;
   p_queue->head = 0;
   p_queue->tail = 0;
   p_queue->tag = 0;
   return 0;
}

int ringq_free(RINGQ * p_queue)
{
    return 0;
}
//Write data to the queue
int ringq_push(RINGQ * p_queue,int data)
{
    print_ringq(p_queue);
    if(ringq_is_full(p_queue))
    {
        printf("ringq is full\n");
        return -1;
    }
    p_queue->space[p_queue->tail] = data;
    p_queue->tail = (p_queue->tail + 1) % p_queue->size ;
    if(p_queue->tail == p_queue->head)
    {
        p_queue->tag = 1;
    }
    return p_queue->tag ;
}
//Get data from the queue
int ringq_poll(RINGQ * p_queue,int * p_data)
{
    print_ringq(p_queue);
    if(ringq_is_empty(p_queue))
    {
        printf("ringq is empty\n");
        return -1;
    }
    *p_data = p_queue->space[p_queue->head];
    p_queue->head = (p_queue->head + 1) % p_queue->size ;
    if(p_queue->tail == p_queue->head)
    {
        p_queue->tag = 0;
    }
    return p_queue->tag ;
}

• 测试代码

//请参考上节的test.c

参考资料：【转】环形队列理论（C语言） - 程序天空下的骆驼 - 博客园 (cnblogs.com)