队列的概念
在此之前,我们来回顾一下队列的基本概念:
队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。
类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票队列的常见两种形式:普通队列、环形队列。
普通队列
在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。
当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。
环形队列
它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。
队列头 (Head) :允许进行删除的一端称为队首。
队列尾 (Tail) :允许进行插入的一端称为队尾。
环形队列的原理与实现
环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。
实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。
看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。
环形队列的代码实现
环形队列数据结构
typedef struct ringBuff{ unsigned int in; //写入的位置 unsigned int out; //读出的位置 unsigned char buffer[RING_BUFF_SIZE]; //数据域 }stRingBuff;
写一字节数据到队列
/** - @brief: 寫一字節的數據到環形隊列 - @param[in]: None - @retval[out]: None - @note: - @author: AresXu - @version: v1.0.0 */ char WriteOneByteToRingBuffer(stRingBuff *ringBuf,char data) { if (ringBuf == NULL) { printf("pointer is null "); return; } if(IsRingBufferFull(ringBuf)) //写之前先判断队列是否写满 { return FALSE; } ringBuf->buffer[ringBuf->in] = data; ringBuf->in = (++ringBuf->in) % RING_BUFF_SIZE; //防止越界 return TRUE; }
写入数据时要判断队列是否满,满了肯定就不能写入。
判断队列是否写满
/** - @brief: 判斷環形隊列是否满 - @param[in]: None - @retval[out]: None - @note: - @author: AresXu - @version: v1.0.0 */ bool IsRingBufferFull(stRingBuff *ringBuf) { if (ringBuf == NULL) { printf("pointer is null "); return; } if(((ringBuf->in+1) % RING_BUFF_SIZE) == ringBuf->out) { // printf("Ring buffer is Full "); return TRUE; } return FALSE; }
当写满时,读写位置也是相等,无法判断是否写满。这种情况有两种办法解决:
数据结构增加一个变量来计数写入数据的个数
像这种((ringBuf->in+1) % RING_BUFF_SIZE) == ringBuf->out,空出一个字节来不写数据
读一字节的数据
/** - @brief: 从環形隊列中读一字节数据 - @param[in]: None - @retval[out]: None - @note: - @author: AresXu - @version: v1.0.0 */ char ReadOneByteFromRingBuffer(stRingBuff *ringBuf,char *data) { if (ringBuf == NULL) { printf("pointer is null "); return; } if(IsRingBufferEmpty(ringBuf)) //读之前判断队列是否为空 { return FALSE; } *data = ringBuf->buffer[ringBuf->out]; ringBuf->out = (++ringBuf->out) % RING_BUFF_SIZE; //防止越界 return TRUE; }
判断队列是否为空写入位置和读出位置相等时为空
/** - @brief: 判斷環形隊列是否空 - @param[in]: None - @retval[out]: None - @author: AresXu - @version: v1.0.0 */ bool IsRingBufferEmpty(stRingBuff *ringBuf) { if (ringBuf == NULL) { printf("pointer is null "); return; } if(ringBuf->in == ringBuf->out) //写入位置和读出位置相等时为空 { // printf("Ring buffer is Empty "); return TRUE; } return FALSE; }
写多个字节到队列
/** * @brief: 寫len個字節數據到環形隊列 * @param[in]: None * @retval[out]: None * @note: * @author: AresXu * @version: v1.0.0 */ void WriteRingBuffer(stRingBuff *ringBuf,char *writeBuf,unsigned int len) { unsigned int i; if (ringBuf == NULL) { printf("pointer is null "); return; } for(i = 0; i < len; i++) { WriteOneByteToRingBuffer(ringBuf,writeBuf[i]); } }
从队列中读出多个字节
/** * @brief: 從環形隊列讀出len個字節的數據 * @param[in]: None * @retval[out]: None * @note: * @author: AresXu * @version: v1.0.0 */ void ReadRingBuffer(stRingBuff *ringBuf,char *readBuf,unsigned int len) { unsigned int i; if (ringBuf == NULL) { printf("pointer is null "); return; } for(i = 0; i < len; i++) { ReadOneByteFromRingBuffer(ringBuf,&readBuf[i]); } }
获取已经写入队列的数据长度有这个方便知道接收完了要从队列中读出多少个数据。
/** * @brief: 獲取已經寫入的長度 * @param[in]: None * @retval[out]: None * @note: * @author: AresXu * @version: v1.0.0 */ int GetRingBufferLength(stRingBuff *ringBuf) { if (ringBuf == NULL) { printf("pointer is null "); return; } return (ringBuf->in - ringBuf->out + RING_BUFF_SIZE) % RING_BUFF_SIZE; }
画个图,画画就可以知道为什么这样可以判断写入的长度。
到STM32上测试
串口接收部分:
static stRingBuff g_stRingBuffer = {0,0,0}; static u8 g_recvFinshFlag = 0; stRingBuff *GetRingBufferStruct(void) { return &g_stRingBuffer; } u8 *IsUsart1RecvFinsh(void) { return &g_recvFinshFlag; } void USART1_IRQHandler(void) //串口1中断服务程序 { u8 res; if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断(接收到的数据必须是0x0d 0x0a结尾) { res = USART_ReceiveData(USART1); //读取接收到的数据 WriteOneByteToRingBuffer(GetRingBufferStruct(),res); } if(USART_GetITStatus(USART1, USART_IT_IDLE) != RESET) //空闲中断 { USART_ReceiveData(USART1); //清除空闲中断 g_recvFinshFlag = 1; //接收完成 } }
主函数:
int main(void) { char readBuffer[100]; u16 t; u16 len; u16 times = 0; delay_init(); //延时函数初始化 NVIC_PriorityGroupConfig(NVIC_PriorityGroup_2); //设置NVIC中断分组2:2位抢占优先级,2位响应优先级 uart_init(115200); //串口初始化为115200 LED_Init(); //LED端口初始化 KEY_Init(); //初始化与按键连接的硬件接口 while(1) { times++; if(*IsUsart1RecvFinsh()) { ReadRingBuffer(GetRingBufferStruct(),readBuffer,GetRingBufferLength(GetRingBufferStruct())); printf("%s",readBuffer); memset(readBuffer,0,100); *IsUsart1RecvFinsh() = 0; } if(times%500==0) LED0=!LED0; delay_ms(1); } }
串口收发测试
审核编辑:汤梓红
-
缓冲区
+关注
关注
0文章
33浏览量
9107 -
计算机
+关注
关注
19文章
7490浏览量
87877 -
STM32
+关注
关注
2270文章
10897浏览量
355790 -
串口
+关注
关注
14文章
1551浏览量
76451 -
队列
+关注
关注
1文章
46浏览量
10893
原文标题:STM32进阶之串口环形缓冲区实现
文章出处:【微信号:c-stm32,微信公众号:STM32嵌入式开发】欢迎添加关注!文章转载请注明出处。
发布评论请先 登录
相关推荐
评论