隊列的概念

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

隊列 (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);   
 }  
}

串口收發測試

審核編輯：湯梓紅