在算法的学习过程中，应当从功能和原理出发理解代码，而不能从代码出发尝试倒推功能和原理，后者不仅效率极低而且还给人带来挫败感，损伤学习兴趣。
队列的应用场景
循环缓冲区（也被称为环形缓冲区或循环队列）在许多产品和应用中都有着重要的作用，特别是在需要处理数据流的场景中。以下是一些常见的使用案例：
- 数据流处理: 循环缓冲区常用于处理不断流入的数据，例如网络数据包、串口数据、音视频数据等。循环缓冲区可以保持数据的连续性，并能平滑处理数据流的速率差异（例如，数据的生成速率和处理速率不匹配的情况）。
- 操作系统: 在操作系统中，循环缓冲区被广泛用于内核和驱动程序，处理如键盘输入、鼠标移动等硬件事件。这些事件由硬件在任何时刻产生，而操作系统需要在适当的时机处理它们。
- 实时系统: 在实时系统中，循环缓冲区用于处理实时任务，例如传感器数据的收集和处理。实时系统需要快速响应，循环缓冲区可以作为一个"先进先出"（FIFO）的队列，保证数据的实时性。
- 音频和视频处理: 在音频和视频处理中，循环缓冲区用于缓存音频样本和视频帧。这样可以保持数据的连续性，并允许多个处理步骤（例如解码、处理、渲染）同时进行。
- 网络通信: 在网络通信中，循环缓冲区用于处理网络数据包。这可以保持数据包的顺序，并处理网络的速率差异。
以上是一些常见的应用，但并不限于这些。实际上，任何需要处理不断流入的数据，或者需要在不同速率的生产者和消费者之间进行数据传递的场景，都可能会使用循环缓冲区。
队列的原理和作用
原理
队列就像是一个管道，如果不断往管道里塞乒乓球，每个乒乓球就会在管道里排成一条队形，先进去的乒乓球就会先出来，这就是队列的“先进先出”规则。
球从左边进去，进去的动作叫“入列”，进去的球在管道里拍成一个队列，叫做队列缓存，说白了就是数组，内部存了5个球就相当于是buff[5]；最右边出来的1号球是最早进去的球，这个出来的动作叫出列，所以遵循了先进先出的规则。
作用
队列最主要的作用是缓存数据。串口接收数据时，我们一般定义一个数组来存储数据，但是假如串口数据频率很快，可能这个数组里存储的数据还没处理完，下一组串口数据又过来了，那么这时候数组里的数据就会被新数据覆盖，导致老数据丢失。像这种情况就可以通过队列来处理，每收到一个字节数据都先入列，然后在应用程序同步解析处理，根据队列先进先出的规则，老数据就不会被新数据“插队”了。
基于这种缓存数据的技术可以灵活应用在各种场景，比如：
- 操作系统的消息传递
- 大数据处理（一两百字节）
队列程序设计思路
实现队列的方法很多，但工作原理都一样。有三个核心关键点：
- 队列缓存（管道）。
- 入列（进去的球）。
- 出列（出去的球）。
队列缓存
队列缓存直接通过定义数组、链表等数据结构来实现。
入列
入列有两个要点：
-
队列缓存应当存储数组下标位置（“队尾”的位置）。如下图，数据①入列前，队尾指针变量指向数组第0个元素；然后将①存放在队尾指针指向位置，成功入列，指针自增，指针变量又指向队尾；将②存放在队尾指针指向位置，成功入列，指针自增，指针变量又指向队尾；以此类推，实现后进后出。
-
如果队列缓存满了又有新的数据入列，一般将最早入列的数据丢弃，从而入列新的数据。
出列
出列则是从最早入列的数据地址开始取，出列的数组下标称为“队头”，同样使用指针变量指向队头，称为队头指针。如下图，一个满编队的队列，有5个数据，队头指针指向队列缓存首地址；①出列后，队头指针自增，指向②的地址；②出列后，队头指针自增，指向③的地址；以此类推，实现先进先出。
队列程序的编写
在了解队列原理与作用，分析队列程序设计思路之后，就可以开始用程序实现队列。一个产品中会有很多个队列缓存不同的数据，消息有消息缓存，串口有串口缓存，所以将队列的基本操作（比如入列、出列）单独写成函数接口，方便程序调用。此处例子是一个“环形队列”。
queue.cpp
入列函数
入列函数形参。管道（缓存空间）：头指针(head)、尾指针(tail)、缓存区地址(pBuff)、缓存区长度(Len)；入列参数：入列数据地址(pData)、入列数据长度(DataLen)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void S_QueueDataIn(unsigned char **head, unsigned char **tail, unsigned char *pBuff, unsigned char len, unsigned char *pData, unsigned char DataLen)
{
for (unsigned char num = 0; num < DataLen; num++,pData++)
{
(**tail) = (*pData);
(*tail)++;
if(*tail == pBuff+len)
{
*tail = pBuff;
}
if (*tail == *head)
{
if (++(*head) == pBuff+len) *head = pBuff;
else ++head;
}
}
}
|
此函数用于向队列中添加数据。它将数据 (*pData) 添加到队列的尾部，如果队列已满（即，尾部指针与头部指针相等），它将移动头部指针来覆盖最旧的数据。如果尾指针超出缓冲区，它将被重置到缓冲区的头部。
出列函数
出列函数形参在形式上与入列函数相似，但其出列参数pData代表出列数据地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| unsigned char S_QueueDataOut(unsigned char **head, unsigned char **tail, unsigned char *pBuff, unsigned char len, unsigned char *pData)
{
unsigned char status = 0;
if (*head != *tail)
{
*pData = **head;
status = 1;
if (++(*head) == pBuff+len)
{
*head = pBuff;
}
}
return status;
}
|
此函数用于从队列中拿取数据。如果队列不为空，则它将头指针指向的数据传输到指定地址(*pData)。如果头指针超出缓冲区，它将被重置到缓冲区的头部。
初始化函数
缓冲区需要初始化才能避免出现不受控制的指针，否则有可能导致程序陷入死循环。
1
2
3
4
5
| void S_QueueEmpty(unsigned char **head, unsigned char **tail, unsigned char *pBuff)
{
*head = pBuff;
*tail = pBuff;
}
|
将缓冲区的头指针和尾指针都初始化到队头。
返回缓冲区数据量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| unsigned short S_QueueDataLen(unsigned char **head, unsigned char **tail, unsigned char *pBuff, unsigned char Len)
{
if (*tail > *head)
{
return *tail-*head;
}
else if (*tail == *head)
{
return 0;
}
else
{
return Len-(*head-*tail);
}
}
|
头文件(queue.h)
以下是以上函数的头文件，定义了结构体，并且利用结构体简化形参，使得函数更具可用性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #ifndef _QUEUE_H_
#define _QUEUE_H_
extern void S_QueueEmpty(unsigned char **head, unsigned char **tail, unsigned char *pBuff);
extern void S_QueueDataIn(unsigned char **head, unsigned char **tail, unsigned char *pBuff, unsigned char len, unsigned char *pData, unsigned char DataLen);
extern unsigned char S_QueueDataOut(unsigned char **head, unsigned char **tail, unsigned char *pBuff, unsigned char len, unsigned char *pData);
extern unsigned short S_QueueDataLen(unsigned char **head, unsigned char **tail, unsigned char *pBuff, unsigned char Len);
#define QueueEmpty(x) S_QueueEmpty((unsigned char**)&(x).head,(unsigned char**)&(x).tail,(unsigned char*)(x).Buff)
#define QueueDataIn(x,y,z) S_QueueDataIn((unsigned char **)&(x).head, (unsigned char **)&(x).tail, (unsigned char *)(x).Buff, sizeof((x).Buff), (unsigned char *)y, z)
#define QueueDataOut(x,y) S_QueueDataOut((unsigned char **)&(x).head, (unsigned char **)&(x).tail, (unsigned char *)(x).Buff, sizeof((x).Buff), (unsigned char *)y)
#define QueueDataLen(x) S_QueueDataLen((unsigned char **)&(x).head, (unsigned char **)&(x).tail, (unsigned char *)(x).Buff, sizeof((x).Buff))
typedef struct
{
unsigned char *head;
unsigned char *tail;
unsigned char Buff[4];
}queue4;
#endif
|
在出(入)列函数前关闭中断，在出(入)列函数后开启中断
在处理串口通信时，我们常常使用中断服务程序 (Interrupt Service Routine, ISR) 来响应串口接收或发送的事件。然而，当我们进行入列（enqueue）或出列（dequeue）操作时，我们通常会关闭中断，这是为了防止数据的不一致性或竞态条件。
让我们考虑一下这样一个场景：你正在主程序中进行出列操作，即从队列中移除一个元素，同时，串口接收中断发生了，并且在ISR中需要向队列添加一个元素。如果你没有在出列操作时关闭中断，ISR可能会在主程序完成出列操作前就开始运行。结果，两个操作可能同时尝试访问和修改队列，可能会导致数据的不一致或错误。
为了避免这种情况，我们在进行出列或入列操作时，会先关闭中断，确保在操作完成前，ISR不会被触发。这就确保了对队列的操作是原子的（不可中断的），从而保证了数据的一致性。操作完成后，我们再重新开启中断，以便能够响应串口事件。
然而，需要注意的是，长时间关闭中断可能会导致丢失中断，因此，需要尽可能快地完成操作，以便能尽快重新开启中断。在设计代码时，应尽量减少需要关闭中断的代码段的长度和复杂性，避免影响系统的响应性。
主函数(main.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include"iostream"
#include"queue.h"
#include"queue.cpp"
queue4 keyMsg;
int main ()
{
printf("初始化缓冲区：\r\n");
QueueEmpty(keyMsg);
printf("keyMsg.head = 0x%x, keyMsg.tail = 0x%x, &keyMsg.Buff = 0x%x\r\n", keyMsg.head, keyMsg.tail, &keyMsg.Buff);
printf("缓冲区内数据数量：%d bit\r\n", QueueDataLen(keyMsg));
printf("入列 a[2] = {5, 6}数列：\r\n");
unsigned char a[2] = {5, 6};
QueueDataIn(keyMsg,&a,sizeof(a));
printf("keyMsg.head = 0x%x, keyMsg.tail = 0x%x, &keyMsg.Buff = 0x%x\r\n", keyMsg.head, keyMsg.tail, &keyMsg.Buff);
printf("keyMsg.Buff[0] = %d, keyMsg.Buff[1] = %d, keyMsg.Buff[2] = %d, keyMsg.Buff[3] = %d\r\n",keyMsg.Buff[0], keyMsg.Buff[1],keyMsg.Buff[2], keyMsg.Buff[3]);
printf("缓冲区内数据数量：%d bit\r\n", QueueDataLen(keyMsg));
printf("出列一个数据到b:\r\n");
unsigned char b = 0;
unsigned char status = QueueDataOut(keyMsg, &b);
printf("keyMsg.head = 0x%x, keyMsg.tail = 0x%x, &keyMsg.Buff = 0x%x\r\n", keyMsg.head, keyMsg.tail, &keyMsg.Buff);
printf("keyMsg.Buff[0] = %d, keyMsg.Buff[1] = %d, keyMsg.Buff[2] = %d, keyMsg.Buff[3] = %d, b = %d, status = %d\r\n",keyMsg.Buff[0], keyMsg.Buff[1],keyMsg.Buff[2], keyMsg.Buff[3],b, status);
printf("缓冲区内数据数量：%d bit\r\n", QueueDataLen(keyMsg));
printf("入列 c[3] = {7,8,9}数列：\r\n");
unsigned char c[3] = {7,8,9};
QueueDataIn(keyMsg,&c,sizeof(c));
printf("keyMsg.head = 0x%x, keyMsg.tail = 0x%x, &keyMsg.Buff = 0x%x\r\n", keyMsg.head, keyMsg.tail, &keyMsg.Buff);
printf("keyMsg.Buff[0] = %d, keyMsg.Buff[1] = %d, keyMsg.Buff[2] = %d, keyMsg.Buff[3] = %d\r\n",keyMsg.Buff[0], keyMsg.Buff[1],keyMsg.Buff[2], keyMsg.Buff[3]);
printf("缓冲区内数据数量：%d bit\r\n", QueueDataLen(keyMsg));
return 0;
}
|
定义好我们需要操作的循环缓冲区，然后就可以使用上面的函数对这个对象进行操作。
