在学习驱动的过程中，接触到了环形缓冲区的概念，发现这个缓冲区和数据结构中的队列具有惊人的相似之处，因此借此来复习相关知识
如果应用层来不及读取数据时，我们可以先将数据放入环形缓冲区中用来记录数据，防止数据丢失。当然，缓冲区越大，那么可以缓存的数据就越多。
1. 队列的定义
队列是限制在两端进行插入操作和删除操作的线性表。特点 ：先进先出（FIFO）
- 允许进行存入操作的一端称为“队尾”
- 允许进行删除操作的一端称为“队头”
- 当线性表中没有元素时，称为“空队”
顺序队列 的本质就是一个数组，只不过限制在一端进行插入（入队），一端限制删除（出队）
2. 顺序队列的数据结构
#define MaxSize 8
typedef struct {
int data[MaxSize];
int front,rear;
} SqQueue;
3.队列相关函数实现
3.1 队列初始化
初始时，默认rear和front都指向下标0的位置。
void fifo_init(SqQueue *sq)
{
sq.rear = sq.front = 0;
}
3.2 判断队列是否为空
初始时，队列的 rear == front 队列为空，当经过几次入队和出队操作后，队列空的条件依然是：rear == front
int fifo_empty(SqQueue *sq)
{
if(sq.rear == sq.front)
{
return 1;
}
return 0;
}
3.3 入队
入队时，需要判断是否队列已满，如果满了就不能入队。前面已经已经指定过 rear == front ，假设让队列全部放满元素，那么rear和front又指向同一个位置。这种情况下，我们选择牺牲掉一个存储单元。当 rear+1指向 front位置时，就表示队列已经满了。
int fifo_put(SqQueue *sq, int value)
{
if((sq.rear + 1) % MaxSize == sq.front)//队列满
{
return -1;
}
sq.data[sq.rear] = value;
sq.rear = (sq.rear + 1) % MaxSize;
return 0;
}
3.4 出队
出队时，需要判断队列是否为空，只有有数据的时候才可以出队。
int fifo_get(SqQueue *sq)
{
int temp_data;
if(sq.rear == sq.front)//队列空
{
return -1;
}
int fifo_out_data = sq.data[sq.front];
sq.front = (sq.front + 1) % MaxSize;
return fifo_out_data;
}
4.测试
模拟一个缓冲区，假设接收处理数据比写入数据的速度慢，可以体现环形缓冲区的好处。
#include <stdio.h>
#include <unistd.h>
/* 定义队列 */
#define MaxSize 8
typedef struct {
int data[MaxSize];
int front,rear;
} SqQueue;
/* 队列初始化 */
void fifo_init(SqQueue *sq)
{
sq->rear = sq->front = 0;
}
/* 判断队列是否为空 */
int fifo_empty(SqQueue *sq)
{
if(sq->rear == sq->front)
{
return 1;
}
return 0;
}
/* 入队 */
int fifo_put(SqQueue *sq, int value)
{
if((sq->rear + 1) % MaxSize == sq->front)//队列满
{
return -1;
}
sq->data[sq->rear] = value;
sq->rear = (sq->rear + 1) % MaxSize;
return 0;
}
/* 出队 */
int fifo_get(SqQueue *sq)
{
int temp_data;
if(sq->rear == sq->front)//队列空
{
return -1;
}
int fifo_out_data = sq->data[sq->front];
sq->front = (sq->front + 1) % MaxSize;
return fifo_out_data;
}
int main(int argc,char **argv)
{
SqQueue sq;
fifo_init(&sq);
int uart_data[10] = {1, 2, 3, 4, 5, 6, 7 ,8 ,9 ,10};
int count = sizeof(uart_data)/sizeof(uart_data[0]);
for(int i = 0; i < count; i++)
{
fifo_put(&sq,uart_data[i]);
printf("fifo_put:%d rear = %d\n", uart_data[i], sq.rear);
if(i % 2 == 0)
{
int ret = fifo_get(&sq);
printf("fifo_get:%d front = %d\n", ret, sq.front);
}
sleep(1);
}
while(!fifo_empty(&sq))
{
int ret = fifo_get(&sq);
printf("fifo_get:%d front = %d\n", ret, sq.front);
}
return 0;
}
结果输出：
fifo_put:1 rear = 1
fifo_get:1 front = 1
fifo_put:2 rear = 2
fifo_put:3 rear = 3
fifo_get:2 front = 2
fifo_put:4 rear = 4
fifo_put:5 rear = 5
fifo_get:3 front = 3
fifo_put:6 rear = 6
fifo_put:7 rear = 7
fifo_get:4 front = 4
fifo_put:8 rear = 0
fifo_put:9 rear = 1
fifo_get:5 front = 5
fifo_put:10 rear = 2
fifo_get:6 front = 6
fifo_get:7 front = 7
fifo_get:8 front = 0
fifo_get:9 front = 1
fifo_get:10 front = 2
当处理完数据时，front == rear 缓冲区为空。
5. 改进方案
为了不牺牲一个存储单元，其实有很多办法，下面总结一些方案：
5.1 增加一个成员表示队列当前长度
#define MaxSize 10
typedef struct {
int data[MaxSize];
int front,rear;
int size;//队列当前长度
} SqQueue;
初始化时
rear = front = 0;
size = 0;
插入成功：size++;
删除成功：size--;
队列空：size = 0;
队列满：size = MaxSize;
5.2 增加一个标记位，记录最近一次操作
在队列的结构体中，增加一个 tag 成员
- 当最近一次进行的删除操作 tag = 0
- 当最近一次进行的插入操作 tag = 1
- 只有删除操作，才可能导致队空
- 只有插入操作，才可能导致队满
#define MaxSize 10
typedef struct {
ElemType data[MaxSize];
int front,rear;
int tag;//最近进行的是删除/插入
} SqQueue;
初始时
rear = front = 0;
tag = 0;
每次删除操作成功时，都令 tag = 0
每次插入操作成功时，都令 tag = 1
队列空：front == rear && tag == 0
队列满：front == rear && tag == 1