隊(duì)列的概念 在此之前，我們來回顧一下隊(duì)列的基本概念： 隊(duì)列 (Queue)：是一種先進(jìn)先出(First In First Out ,簡(jiǎn)稱 FIFO)的線性表，只允許在一端插入（入隊(duì)），在另一端進(jìn)行刪除（出隊(duì)）。 隊(duì)列的特點(diǎn) 類似售票排隊(duì)窗口，先到的人看到能先買到票，然后先走，后來的人只能后買到票 隊(duì)列的常見兩種形式 普通隊(duì)列 在計(jì)算機(jī)中，每個(gè)信息都是存儲(chǔ)在存儲(chǔ)單元中的，比喻一下吧，上圖的一些小正方形格子就是一個(gè)個(gè)存儲(chǔ)單元，你可以理解為常見的數(shù)組，存放我們一個(gè)個(gè)的信息。 當(dāng)有大量數(shù)據(jù)的時(shí)候，我們不能存儲(chǔ)所有的數(shù)據(jù)，那么計(jì)算機(jī)處理數(shù)據(jù)的時(shí)候，只能先處理先來的，那么處理完后呢，就會(huì)把數(shù)據(jù)釋放掉，再處理下一個(gè)。那么，已經(jīng)處理的數(shù)據(jù)的內(nèi)存就會(huì)被浪費(fèi)掉。因?yàn)楹髞淼臄?shù)據(jù)只能往后排隊(duì)，如過要將剩余的數(shù)據(jù)都往前移動(dòng)一次，那么效率就會(huì)低下了，肯定不現(xiàn)實(shí)，所以，環(huán)形隊(duì)列就出現(xiàn)了。 環(huán)形隊(duì)列 它的隊(duì)列就是一個(gè)環(huán)，它避免了普通隊(duì)列的缺點(diǎn)，就是有點(diǎn)難理解而已，其實(shí)它就是一個(gè)隊(duì)列，一樣有隊(duì)列頭，隊(duì)列尾，一樣是先進(jìn)先出（FIFO）。我們采用順時(shí)針的方式來對(duì)隊(duì)列進(jìn)行排序。 隊(duì)列頭?(Head) : 允許進(jìn)行刪除的一端稱為隊(duì)首。 隊(duì)列尾?(Tail) : 允許進(jìn)行插入的一端稱為隊(duì)尾。 環(huán)形隊(duì)列的實(shí)現(xiàn)：在計(jì)算機(jī)中，也是沒有環(huán)形的內(nèi)存的，只不過是我們將順序的內(nèi)存處理過，讓某一段內(nèi)存形成環(huán)形，使他們首尾相連，簡(jiǎn)單來說，這其實(shí)就是一個(gè)數(shù)組，只不過有兩個(gè)指針，一個(gè)指向列隊(duì)頭，一個(gè)指向列隊(duì)尾。指向列隊(duì)頭的指針(Head)是緩沖區(qū)可讀的數(shù)據(jù)，指向列隊(duì)尾的指針(Tail)是緩沖區(qū)可寫的數(shù)據(jù)，通過移動(dòng)這兩個(gè)指針(Head) &(Tail)即可對(duì)緩沖區(qū)的數(shù)據(jù)進(jìn)行讀寫操作了，直到緩沖區(qū)已滿（頭尾相接），將數(shù)據(jù)處理完，可以釋放掉數(shù)據(jù)，又可以進(jìn)行存儲(chǔ)新的數(shù)據(jù)了。 實(shí)現(xiàn)的原理：初始化的時(shí)候，列隊(duì)頭與列隊(duì)尾都指向0，當(dāng)有數(shù)據(jù)存儲(chǔ)的時(shí)候，數(shù)據(jù)存儲(chǔ)在‘0’的地址空間，列隊(duì)尾指向下一個(gè)可以存儲(chǔ)數(shù)據(jù)的地方‘1’，再有數(shù)據(jù)來的時(shí)候，存儲(chǔ)數(shù)據(jù)到地址‘1’，然后隊(duì)列尾指向下一個(gè)地址‘2’。當(dāng)數(shù)據(jù)要進(jìn)行處理的時(shí)候，肯定是先處理‘0’空間的數(shù)據(jù)，也就是列隊(duì)頭的數(shù)據(jù)，處理完了數(shù)據(jù)，‘0’地址空間的數(shù)據(jù)進(jìn)行釋放掉，列隊(duì)頭指向下一個(gè)可以處理數(shù)據(jù)的地址‘1’。從而實(shí)現(xiàn)整個(gè)環(huán)形緩沖區(qū)的數(shù)據(jù)讀寫。 看圖，隊(duì)列頭就是指向已經(jīng)存儲(chǔ)的數(shù)據(jù)，并且這個(gè)數(shù)據(jù)是待處理的。下一個(gè)CPU處理的數(shù)據(jù)就是1；而隊(duì)列尾則指向可以進(jìn)行寫數(shù)據(jù)的地址。當(dāng)1處理了，就會(huì)把1釋放掉。并且把隊(duì)列頭指向2。當(dāng)寫入了一個(gè)數(shù)據(jù)6，那么隊(duì)列尾的指針就會(huì)指向下一個(gè)可以寫的地址。 從隊(duì)列到串口緩沖區(qū)的實(shí)現(xiàn) 串口環(huán)形緩沖區(qū)收發(fā)：在很多入門級(jí)教程中，我們知道的串口收發(fā)都是：接收一個(gè)數(shù)據(jù)，觸發(fā)中斷，然后把數(shù)據(jù)發(fā)回來。這種處理方式是沒有緩沖的，當(dāng)數(shù)量太大的時(shí)候，亦或者當(dāng)數(shù)據(jù)接收太快的時(shí)候，我們來不及處理已經(jīng)收到的數(shù)據(jù)，那么，當(dāng)再次收到數(shù)據(jù)的時(shí)候，就會(huì)將之前還未處理的數(shù)據(jù)覆蓋掉。那么就會(huì)出現(xiàn)丟包的現(xiàn)象了，對(duì)我們的程序是一個(gè)致命的創(chuàng)傷。 那么如何避免這種情況的發(fā)生呢，很顯然，上面說的一些隊(duì)列的特性很容易幫我們實(shí)現(xiàn)我們需要的情況。將接受的數(shù)據(jù)緩存一下，讓處理的速度有些許緩沖，使得處理的速度趕得上接收的速度，上面又已經(jīng)分析了普通隊(duì)列與環(huán)形隊(duì)列的優(yōu)劣了，那么我們肯定是用環(huán)形隊(duì)列來進(jìn)行實(shí)現(xiàn)了。下面就是代碼的實(shí)現(xiàn)： 定義一個(gè)結(jié)構(gòu)體： typedef struct { u16 Head; u16 Tail; u16 Lenght; u8 Ring_Buff[RINGBUFF_LEN]; }RingBuff_t; RingBuff_t ringBuff;//創(chuàng)建一個(gè)ringBuff的緩沖區(qū) 初始化 初始化結(jié)構(gòu)體相關(guān)信息：使得我們的環(huán)形緩沖區(qū)是頭尾相連的，并且里面沒有數(shù)據(jù)，也就是空的隊(duì)列。 /** * @brief RingBuff_Init * @param void * @return void * @author 杰杰 * @date 2018 * @version v1.0 * @note 初始化環(huán)形緩沖區(qū) */ void RingBuff_Init(void) { //初始化相關(guān)信息 ringBuff.Head = 0; ringBuff.Tail = 0; ringBuff.Lenght = 0; } 初始化效果如下： 寫入環(huán)形緩沖區(qū)的代碼實(shí)現(xiàn)： /** * @brief Write_RingBuff * @param u8 data * @return FLASE:環(huán)形緩沖區(qū)已滿，寫入失敗;TRUE:寫入成功 * @author 杰杰 * @date 2018 * @version v1.0 * @note 往環(huán)形緩沖區(qū)寫入u8類型的數(shù)據(jù) */ u8 Write_RingBuff(u8 data) { if(ringBuff.Lenght >= RINGBUFF_LEN) //判斷緩沖區(qū)是否已滿 { return FLASE; } ringBuff.Ring_Buff[ringBuff.Tail]=data; // ringBuff.Tail ; ringBuff.Tail = (ringBuff.Tail 1)%RINGBUFF_LEN;//防止越界非法訪問 ringBuff.Lenght ; return TRUE; } 讀取緩沖區(qū)的數(shù)據(jù)的代碼實(shí)現(xiàn)： /** * @brief Read_RingBuff * @param u8 *rData，用于保存讀取的數(shù)據(jù) * @return FLASE:環(huán)形緩沖區(qū)沒有數(shù)據(jù)，讀取失敗;TRUE:讀取成功 * @author 杰杰 * @date 2018 * @version v1.0 * @note 從環(huán)形緩沖區(qū)讀取一個(gè)u8類型的數(shù)據(jù) */ u8 Read_RingBuff(u8 *rData) { if(ringBuff.Lenght == 0)//判斷非空 { return FLASE; } *rData = ringBuff.Ring_Buff[ringBuff.Head];//先進(jìn)先出FIFO，從緩沖區(qū)頭出 // ringBuff.Head ; ringBuff.Head = (ringBuff.Head 1)%RINGBUFF_LEN;//防止越界非法訪問 ringBuff.Lenght--; return TRUE; } 對(duì)于讀寫操作需要注意的地方有兩個(gè)： 判斷隊(duì)列是否為空或者滿，如果空的話，是不允許讀取數(shù)據(jù)的，返回FLASE。如果是滿的話，也是不允許寫入數(shù)據(jù)的，避免將已有數(shù)據(jù)覆蓋掉。那么如果處理的速度趕不上接收的速度，可以適當(dāng)增大緩沖區(qū)的大小，用空間換取時(shí)間。 防止指針越界非法訪問，程序有說明，需要使用者對(duì)整個(gè)緩沖區(qū)的大小進(jìn)行把握。 那么在串口接收函數(shù)中： void USART1_IRQHandler(void) { if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中斷 { USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚標(biāo)志位 Write_RingBuff(USART_ReceiveData(USART1)); //讀取接收到的數(shù)據(jù) } } 測(cè)試效果 測(cè)試數(shù)據(jù)沒有發(fā)生丟包現(xiàn)象 補(bǔ)充 對(duì)于現(xiàn)在的階段，我本人寫代碼也慢慢學(xué)會(huì)規(guī)范了。所有的代碼片段均使用了可讀性很強(qiáng)的，還有可移植性也很強(qiáng)的。我使用了宏定義來決定是否開啟環(huán)形緩沖區(qū)的方式來收發(fā)數(shù)據(jù)，移植到大家的代碼并不會(huì)有其他副作用，只需要開啟宏定義即可使用了。 #define USER_RINGBUFF 1 //使用環(huán)形緩沖區(qū)形式接收數(shù)據(jù) #if USER_RINGBUFF /**如果使用環(huán)形緩沖形式接收串口數(shù)據(jù)***/ #define RINGBUFF_LEN 200 //定義最大接收字節(jié)數(shù) 200 #define FLASE 1 #define TRUE 0 void RingBuff_Init(void); u8 Write_RingBuff(u8 data); u8 Read_RingBuff(u8 *rData); #endif 當(dāng)然，我們完全可以用空閑中斷與DMA傳輸，效率更高，但是某些單片機(jī)沒有空閑中斷與DMA，那么這種環(huán)形緩沖區(qū)的作用就很大了，并且移植簡(jiǎn)便。 原文鏈接：