隊(duì)列的概念

在此之前，我們來回顧一下隊(duì)列的基本概念：

隊(duì)列 (Queue)：是一種先進(jìn)先出(First In First Out ,簡稱 FIFO)的線性表，只允許在一端插入（入隊(duì)），在另一端進(jìn)行刪除（出隊(duì)）。

類似售票排隊(duì)窗口，先到的人看到能先買到票，然后先走，后來的人只能后買到票隊(duì)列的常見兩種形式：普通隊(duì)列、環(huán)形隊(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)

環(huán)形隊(duì)列的實(shí)現(xiàn)：在計(jì)算機(jī)中，也是沒有環(huán)形的內(nèi)存的，只不過是我們將順序的內(nèi)存處理過，讓某一段內(nèi)存形成環(huá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è)可以寫的地址。

環(huán)形隊(duì)列的代碼實(shí)現(xiàn)

環(huán)形隊(duì)列數(shù)據(jù)結(jié)構(gòu)

typedef struct ringBuff{
    unsigned int in;               //寫入的位置
    unsigned int out;              //讀出的位置
    unsigned char buffer[RING_BUFF_SIZE];     //數(shù)據(jù)域
}stRingBuff;

寫一字節(jié)數(shù)據(jù)到隊(duì)列

/**
 - @brief:         寫一字節(jié)的數(shù)據(jù)到環(huán)形隊(duì)列
 - @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))   //寫之前先判斷隊(duì)列是否寫滿
    {
        return FALSE;
    }


    ringBuf->buffer[ringBuf->in] = data;
    ringBuf->in = (++ringBuf->in) % RING_BUFF_SIZE;    //防止越界
 return TRUE;
}

寫入數(shù)據(jù)時(shí)要判斷隊(duì)列是否滿，滿了肯定就不能寫入。

判斷隊(duì)列是否寫滿

/**
 - @brief:         判斷環(huán)形隊(duì)列是否滿
 - @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;
}

當(dāng)寫滿時(shí)，讀寫位置也是相等，無法判斷是否寫滿。這種情況有兩種辦法解決：

數(shù)據(jù)結(jié)構(gòu)增加一個(gè)變量來計(jì)數(shù)寫入數(shù)據(jù)的個(gè)數(shù)

像這種((ringBuf->in+1) % RING_BUFF_SIZE) == ringBuf->out，空出一個(gè)字節(jié)來不寫數(shù)據(jù)

讀一字節(jié)的數(shù)據(jù)

/**
 - @brief:         從環(huán)形隊(duì)列中讀一字節(jié)數(shù)據(jù)
 - @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))    //讀之前判斷隊(duì)列是否為空
    {
        return FALSE;
    }


    *data = ringBuf->buffer[ringBuf->out];
    ringBuf->out = (++ringBuf->out) % RING_BUFF_SIZE;    //防止越界


    return TRUE;
}

判斷隊(duì)列是否為空寫入位置和讀出位置相等時(shí)為空

/**
 - @brief:        判斷環(huán)形隊(duì)列是否空
 - @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)   //寫入位置和讀出位置相等時(shí)為空
    {
//  printf("Ring buffer is Empty
");
        return TRUE;
    }
    return FALSE;
}

寫多個(gè)字節(jié)到隊(duì)列

/**
 * @brief:         寫len個(gè)字節(jié)數(shù)據(jù)到環(huán)形隊(duì)列
 * @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]);
    }
}

從隊(duì)列中讀出多個(gè)字節(jié)

/**
 * @brief:         從環(huán)形隊(duì)列讀出len個(gè)字節(jié)的數(shù)據(jù)
 * @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]);
    }
}

獲取已經(jīng)寫入隊(duì)列的數(shù)據(jù)長度有這個(gè)方便知道接收完了要從隊(duì)列中讀出多少個(gè)數(shù)據(jù)。

/**
  * @brief:         獲取已經(jīng)寫入的長度
  * @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;
}

畫個(gè)圖，畫畫就可以知道為什么這樣可以判斷寫入的長度。

到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中斷服務(wù)程序
{
 u8 res;


 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET)  //接收中斷(接收到的數(shù)據(jù)必須是0x0d 0x0a結(jié)尾)
 {
  res = USART_ReceiveData(USART1); //讀取接收到的數(shù)據(jù)
  WriteOneByteToRingBuffer(GetRingBufferStruct(),res); 
    }
 if(USART_GetITStatus(USART1, USART_IT_IDLE) != RESET)        //空閑中斷
 {
  USART_ReceiveData(USART1);           //清除空閑中斷
  g_recvFinshFlag = 1;                  //接收完成
 }
} 

主函數(shù)：

int main(void)
{  
 char readBuffer[100];
 u16 t;  
 u16 len; 
 u16 times = 0;
 delay_init();       //延時(shí)函數(shù)初始化   
 NVIC_PriorityGroupConfig(NVIC_PriorityGroup_2); //設(shè)置NVIC中斷分組2:2位搶占優(yōu)先級(jí)，2位響應(yīng)優(yōu)先級(jí)
 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);   
 }  
}

串口收發(fā)測試

審核編輯：湯梓紅