隊列的概念

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

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

類似售票排隊窗口，先到的人看到能先買到票，然后先走，后來的人只能后買到票隊列的常見兩種形式：普通隊列、環(huán)形隊列。

普通隊列


????



在計算機中，每個信息都是存儲在存儲單元中的，比喻一下吧，上圖的一些小正方形格子就是一個個存儲單元，你可以理解為常見的數(shù)組，存放我們一個個的信息。

當(dāng)有大量數(shù)據(jù)的時候，我們不能存儲所有的數(shù)據(jù)，那么計算機處理數(shù)據(jù)的時候，只能先處理先來的，那么處理完后呢，就會把數(shù)據(jù)釋放掉，再處理下一個。那么，已經(jīng)處理的數(shù)據(jù)的內(nèi)存就會被浪費掉。因為后來的數(shù)據(jù)只能往后排隊，如過要將剩余的數(shù)據(jù)都往前移動一次，那么效率就會低下了，肯定不現(xiàn)實，所以，環(huán)形隊列就出現(xiàn)了。

環(huán)形隊列



????



它的隊列就是一個環(huán)，它避免了普通隊列的缺點，就是有點難理解而已，其實它就是一個隊列，一樣有隊列頭，隊列尾，一樣是先進先出（FIFO）。我們采用順時針的方式來對隊列進行排序。

隊列頭 (Head) :允許進行刪除的一端稱為隊首。

隊列尾 (Tail) :允許進行插入的一端稱為隊尾。

環(huán)形隊列的原理與實現(xiàn)

環(huán)形隊列的實現(xiàn)：在計算機中，也是沒有環(huán)形的內(nèi)存的，只不過是我們將順序的內(nèi)存處理過，讓某一段內(nèi)存形成環(huán)形，使他們首尾相連，簡單來說，這其實就是一個數(shù)組，只不過有兩個指針，一個指向列隊頭，一個指向列隊尾。指向列隊頭的指針(Head)是緩沖區(qū)可讀的數(shù)據(jù)，指向列隊尾的指針(Tail)是緩沖區(qū)可寫的數(shù)據(jù)，通過移動這兩個指針(Head) &(Tail)即可對緩沖區(qū)的數(shù)據(jù)進行讀寫操作了，直到緩沖區(qū)已滿（頭尾相接），將數(shù)據(jù)處理完，可以釋放掉數(shù)據(jù)，又可以進行存儲新的數(shù)據(jù)了。

實現(xiàn)的原理：初始化的時候，列隊頭與列隊尾都指向0，當(dāng)有數(shù)據(jù)存儲的時候，數(shù)據(jù)存儲在‘0’的地址空間，列隊尾指向下一個可以存儲數(shù)據(jù)的地方‘1’，再有數(shù)據(jù)來的時候，存儲數(shù)據(jù)到地址‘1’，然后隊列尾指向下一個地址‘2’。當(dāng)數(shù)據(jù)要進行處理的時候，肯定是先處理‘0’空間的數(shù)據(jù)，也就是列隊頭的數(shù)據(jù)，處理完了數(shù)據(jù)，‘0’地址空間的數(shù)據(jù)進行釋放掉，列隊頭指向下一個可以處理數(shù)據(jù)的地址‘1’。從而實現(xiàn)整個環(huán)形緩沖區(qū)的數(shù)據(jù)讀寫。



????



看圖，隊列頭就是指向已經(jīng)存儲的數(shù)據(jù)，并且這個數(shù)據(jù)是待處理的。下一個CPU處理的數(shù)據(jù)就是1；而隊列尾則指向可以進行寫數(shù)據(jù)的地址。當(dāng)1處理了，就會把1釋放掉。并且把隊列頭指向2。當(dāng)寫入了一個數(shù)據(jù)6，那么隊列尾的指針就會指向下一個可以寫的地址。

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

環(huán)形隊列數(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ù)到隊列

/**
 - @brief:         寫一字節(jié)的數(shù)據(jù)到環(huán)形隊列
 - @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;
}

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

判斷隊列是否寫滿

/**
 - @brief:         判斷環(huán)形隊列是否滿
 - @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ù)據(jù)結(jié)構(gòu)增加一個變量來計數(shù)寫入數(shù)據(jù)的個數(shù)

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

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

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


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


    return TRUE;
}

判斷隊列是否為空寫入位置和讀出位置相等時為空

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

寫多個字節(jié)到隊列

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

從隊列中讀出多個字節(jié)

/**
 * @brief:         從環(huán)形隊列讀出len個字節(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)寫入隊列的數(shù)據(jù)長度有這個方便知道接收完了要從隊列中讀出多少個數(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;
}

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

到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ù)初始化   
 NVIC_PriorityGroupConfig(NVIC_PriorityGroup_2); //設(shè)置NVIC中斷分組2:2位搶占優(yōu)先級，2位響應(yīng)優(yōu)先級
 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ā)測試

審核編輯：湯梓紅