C で循環リスト (リング バッファ) を実装するにはどうすればよいですか?

C で表現された非常に単純な実装です。循環バッファ スタイルの FIFO キューを実装します。キュー サイズ、キュー データ、およびキュー インデックス (インおよびアウト) を含む構造体を作成することで、より一般的なものにすることができます。これは、キューに追加またはキューから削除するデータと共に渡されます。これらの同じルーチンは、複数のキューを処理できます。また、これにより任意のサイズのキューが許可されることに注意してください。ただし、2 の累乗を使用してコードをさらにカスタマイズすると、スピードアップを使用できます。

/* Very simple queue
 * These are FIFO queues which discard the new data when full.
 *
 * Queue is empty when in == out.
 * If in != out, then 
 *  - items are placed into in before incrementing in
 *  - items are removed from out before incrementing out
 * Queue is full when in == (out-1 + QUEUE_SIZE) % QUEUE_SIZE;
 *
 * The queue will hold QUEUE_ELEMENTS number of items before the
 * calls to QueuePut fail.
 */

/* Queue structure */
#define QUEUE_ELEMENTS 100
#define QUEUE_SIZE (QUEUE_ELEMENTS + 1)
int Queue[QUEUE_SIZE];
int QueueIn, QueueOut;

void QueueInit(void)
{
    QueueIn = QueueOut = 0;
}

int QueuePut(int new)
{
    if(QueueIn == (( QueueOut - 1 + QUEUE_SIZE) % QUEUE_SIZE))
    {
        return -1; /* Queue Full*/
    }

    Queue[QueueIn] = new;

    QueueIn = (QueueIn + 1) % QUEUE_SIZE;

    return 0; // No errors
}

int QueueGet(int *old)
{
    if(QueueIn == QueueOut)
    {
        return -1; /* Queue Empty - nothing to get*/
    }

    *old = Queue[QueueOut];

    QueueOut = (QueueOut + 1) % QUEUE_SIZE;

    return 0; // No errors
}

リンクされたリストを使用します。頭と尾に別々のポインターを維持します。リストの先頭からポップし、末尾にプッシュします。円形にしたい場合は、新しい尾が常に頭を向いていることを確認してください。

リンク リストを使用して FIFO を実装したい理由は理解できますが、循環リストにする理由は何ですか?

固定長の循環リストが必要な場合。 (動的) 配列を使用できます。ハウスキーピングには 2 つの変数を使用します。 1 つは次の要素の位置、もう 1 つは要素の数をカウントします。

Put:要素を自由な場所に置きます。位置を移動します (モジュロ長さ)。カウントがリストの長さと等しくない限り、カウントに 1 を追加します。取得:カウント> 0 の場合のみ。位置を左に移動します (モジュロ長さ)。カウントを減らします。