前言

隊列，也稱作FIFO，常用數據結構之一，特點是先進先出。

隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

設計思想

首先從理想的無限緩沖區(qū)到實際的使用進行設計思考。

理想化的無限緩沖區(qū)

在理想情況下，寫入器（數據生產者）和讀取器（數據消費者）在使用過程中，能夠訪問相同的、連續(xù)的、并且是無限的緩沖區(qū)。寫入器和讀取器各自保存一個索引，分別指向緩沖區(qū)中寫和讀的位置，即與之對齊的“寫”和“讀”指針開始進行操作。

當寫入器想要在末端加入數據時，它會將數據追加到“寫索引”后面的位置，之后將“寫索引”移動到新寫數據塊的末尾。而讀取器在頂端讀取數據時，如果“寫索引”比“讀索引”位置大時，讀寫器就可以對已有數據進行讀取操作。完成之后，讀寫器將“讀索引”移動到讀取數據塊的末尾，以跟蹤記錄已經處理至緩沖區(qū)的哪一部分。

讀取器永遠不會試圖讀取超過“寫索引”位置的數據，因為不能保證那里有有效的數據，即寫入器在那里寫入了東西。這也意味著“讀索引”永遠不能超過“寫索引”。目前為止，我們假設這個理想內存系統(tǒng)總是連貫一致的，也就是說一旦執(zhí)行了寫操作，數據可以立即地、順序地進行讀取出來。

有界限的緩沖區(qū)

而現實中計算機并沒有神奇的無限緩沖區(qū)。我們必須分配有限的內存空間，以供寫入器和讀取器之間進行或許無限的使用。在循環(huán)緩沖區(qū)中，“寫索引”可以在抵達緩沖區(qū)末尾時跨越緩沖區(qū)的邊界回繞到緩沖區(qū)的開始位置。

當“寫索引”接近緩沖區(qū)末尾并且又有新數據輸入進來時，會將寫操作分成兩個數據塊：一個寫入緩沖區(qū)末尾剩余的空間，另一個將剩下的數據寫入緩沖區(qū)開頭。請注意，如果此時“讀索引”位置接近緩沖區(qū)開頭，那么這個寫入操作可能會破壞尚未被讀取器處理的數據。由于這個原因，“寫索引”在被回繞后不允許超過“讀索引”。

這樣下來，可能會得到兩種內存分布情況：

• “寫索引”在前面，“讀索引”在后面，即在索引移動方向上，“寫索引”超前于“讀索引”，已寫入但未被讀取器處理的有效數據位于“讀索引”和“寫索引”之間的緩沖區(qū)內；
• “讀索引”在前面，“寫索引”在后面，即在索引移動方向上，“讀索引”超前于“寫索引”，有效數據開始于“讀索引”，結束于緩沖區(qū)末尾，并回繞到緩沖區(qū)開頭直至“寫索引”位置。

注意：上述第二種情況下，“寫索引”和“讀索引”可能存在重合，為了區(qū)分這兩種情況，一般規(guī)定第二種情況下“寫索引”和“讀索引”不允許重合，即“寫索引”位置必須落后于“讀索引”一步。

因此，在循環(huán)緩沖區(qū)中，不斷地從內存分布情況 1 進行到內存分布情況 2，又從 2 再回到 1，如此循環(huán)往復，當“讀索引”到達緩沖區(qū)的末尾時，也回繞到緩沖區(qū)開頭繼續(xù)進行讀取。

并發(fā)性設計

通常在使用緩沖區(qū)隊列時，讀數據和寫數據大部分情況都是多線程或者前后臺（中斷）分別處理的，為了減少寫入器、讀取器兩個線程之間或者前后臺系統(tǒng)之間需要發(fā)生的協(xié)調，一種常見策略是，將讀寫變量獨立出來，分別由讀取器和寫入器進行改變。這也簡化了并發(fā)性設計中的邏輯推理，因為誰負責更改哪個變量總是很清楚。

讓我們從一個簡單的循環(huán)緩沖區(qū)開始，它具有原始的“寫索引”和“讀索引”。唯有寫入器能更改“寫索引”，而唯有讀取器能更改“讀索引”。

這樣就可以不用鎖進行操作，提高效率。

如何保證地址的連續(xù)性

在上述提到的有界緩沖區(qū)內存分布情況，第二種情況無法保證地址的連續(xù)性，因為有些場景需要使用到連續(xù)的內存塊地址，解決這種場景的辦法有：可以對緩存區(qū)進行分塊，每一塊固定的長度，即固定長度的隊列，這樣就能在一定程度上保證了地址的連續(xù)性。

代碼實現

隊列結構體定義

先定義一個隊列結構體，包含了每個塊的大小、數目、寫入塊索引、讀取塊索引等，為了解決“寫索引”和“讀索引”可能存在重合的兩種情況，加入狀態(tài)變量用來區(qū)分。

typedef uint16_t queuesize_t;

typedef struct{
    volatile uint8_t state; /*!< 控制狀態(tài) */

    queuesize_t end;        /*!< 循環(huán)隊列尾哨兵 */

    queuesize_t head;       /*!< 循環(huán)隊列首哨兵 */

    queuesize_t num;        /*!< 循環(huán)隊列中能存儲的最多組數 */

    queuesize_t size;       /*!< 單組內存大小 */

    char  *pBufMem;         /*!< Buf 指針 */
} QueueCtrl_t;

隊列初始化

定義結構體后一定要對數據初始化，同時為接口提供一些入參變量設置隊列的信息進行封裝，如緩存區(qū)地址、隊列的組數目、組內存大小和是否內存覆蓋等信息。

/**
  * @brief      隊列控制初始化, 可采用的是動態(tài)/靜態(tài)內存分配方式
  *
  * @param[in,out] pCtrl 隊列控制句柄
  * @param[in]  buf      buf 地址
  * @param[in]  queueNum 隊列數目大小
  * @param[in]  size     隊列中單個內存大小
  * @param[in]  isCover  false,不覆蓋; true,隊列滿了覆蓋未讀取的最早舊數據
  * @return     0,成功; -1,失敗
  */
int Queue_Init(QueueCtrl_t *pCtrl, const void *pBufMem, queuesize_t queueNum, queuesize_t size, bool isCover)
{
    if (pCtrl == NULL || pBufMem == NULL || queueNum == 0 || size == 0)
    {
        return -1;
    }

    pCtrl->end     = 0;
    pCtrl->head    = 0;
    pCtrl->pBufMem = (char *)pBufMem;
    pCtrl->num  = queueNum;
    pCtrl->size    = size;
    pCtrl->state   = 0x00;

    if (isCover)
    {
        QUEUE_STATE_SET(pCtrl, QUEUE_ENABLE_COVER);
    }

    return 0;
}

隊列寫操作

隊列都是在末端增加數據，因為隊列組的大小已經固定，因此在寫操作數據時可以省略新數據的內存大小。

/**
  * @brief      在隊列末尾加入新的數據
  *
  * @param[in,out] pCtrl 隊列控制句柄
  * @param[in]     src   新的數據
  * @retval     返回的值含義如下
  *             @arg 0: 寫入成功
  *             @arg -1: 寫入失敗
  */
extern int Queue_Push(QueueCtrl_t *pCtrl, const void *src)
{
    if (pCtrl == NULL || src == NULL)
    {
        return -1;
    }

    if (IS_QUEUE_STATE_SET(pCtrl, QUEUE_DISABLE_PUSH))
    {
        return -1;
    }

    memcpy(&pCtrl->pBufMem[pCtrl->end * pCtrl->size], src, pCtrl->size);
    pCtrl->end++;
    QUEUE_STATE_SET(pCtrl, QUEUE_EXIT_DATA);

    if ((pCtrl->end) >= (pCtrl->num))
    {
        (pCtrl->end) = 0;
    }

    if (IS_QUEUE_STATE_SET(pCtrl, QUEUE_DATA_FULL))
    {
        (pCtrl->head) = (pCtrl->end);
    }
    else if ((pCtrl->end) == (pCtrl->head))
    {
        QUEUE_STATE_SET(pCtrl, QUEUE_DATA_FULL);

        if (!IS_QUEUE_STATE_SET(pCtrl, QUEUE_ENABLE_COVER))
        {
            QUEUE_STATE_SET(pCtrl, QUEUE_DISABLE_PUSH);
        }
    }

    return 0;
}

隊列讀操作

隊列都是在頂端讀取數據，因為隊列組的大小已經固定，因此在都操作數據時可以省略數據讀取存入的內存大小（必須保證讀取的內存大小足夠）。

/**
  * @brief      讀取并彈出隊列頂端的數據
  *
  * @param[in,out] pCtrl 隊列控制句柄
  * @param[in]     dest  讀取的數據
  * @retval     返回的值含義如下
  *             @arg 0: 成功
  *             @arg -1: 失敗
  */
int Queue_Pop(QueueCtrl_t *pCtrl, void *dest)
{
    if (pCtrl == NULL)
    {
        return -1;
    }

    if (!IS_QUEUE_STATE_SET(pCtrl, QUEUE_EXIT_DATA))
    {
        return -1;
    }

    memcpy((char *)dest, &pCtrl->pBufMem[pCtrl->head * pCtrl->size], pCtrl->size);
    pCtrl->head++;

    if ((pCtrl->head) >= (pCtrl->num))
    {
        pCtrl->head = 0;
    }

    if ((pCtrl->head) == (pCtrl->end))
    {
        if (!IS_QUEUE_STATE_SET(pCtrl, QUEUE_DATA_FULL))
        {
            QUEUE_STATE_CLEAR(pCtrl, QUEUE_EXIT_DATA);
        }
    }

    QUEUE_STATE_CLEAR(pCtrl, QUEUE_DISABLE_PUSH);
    QUEUE_STATE_CLEAR(pCtrl, QUEUE_DATA_FULL);

    return 0;
}