C言語関数辞典

≫ ホーム ≫ C言語Tips集 ≫ 配列・メモリ領域 ≫ 配列を簡易的なキューとして使用する

C言語Tips集 - 配列を簡易的なキューとして使用する

C言語でキュー (queue) を実装するにはさまざまな方法がありますが，ここではあくまで配列を簡易的なキューとして扱えるようにすることを目的とします．

キューの構造

キューのデータ構造をそのまま配列で実装しようとすると，膨大なサイズの配列が必要になります．そこで，ここではリングバッファ (ring buffer) と呼ばれる手法で実装します．リングバッファは，配列を (配列の) 末尾と先頭がつながっている環状の循環構造とみなします．(図1) キューに格納されたデータを管理するために以下の2つの変数を使用します．

head: キューの先頭要素を指し示す変数
tail: キューの末尾要素を指し示す変数

図1 リングバッファのイメージ図

キューにはエンキュー (enqueue) 操作とデキュー (dequeue) 操作の 2 種類の動作が存在します．これらの動作を行う関数を作成することで配列を簡易的なキューとして使用可能にします．

エンキュー操作の実装

エンキュー操作は以下の 2 つの手順が必要になります．

キューにデータを追加する
tail をインクリメントする

図2 エンキュー操作のイメージ図

データの追加の際には tail をそのまま配列の添え字にするのではなく，tail と配列の最大要素数の余剰を計算し，添え字にするのがポイントです．また，実用上，配列の最大要素数を超えるデータがエンキューされたときのことを考えて，場合わけをする必要があります．以下にエンキュー操作を行う関数の実装例を示します．

/**
 * 配列にエンキューする
 * @param[in,out] queue 配列
 * @param[in] data データ
 * @param[in,out] head キューの先頭要素
 * @param[in,out] tail キューの末尾要素
 * @param[in] n 配列の要素数
 * @retval >=1 配列に格納されている要素の数
 * @retval 0 配列へのエンキューに失敗
 */
 */
int ArrayEnqueue(int *queue, int data, int *head, int *tail, size_t n) {
    if (*head % n != (*tail + 1) % n) {
        queue[(*tail)++ % n] = data;
        return *tail - *head;
    } else {
        return 0;
    }
}

head と tail は引数として受け取り，ポインタ渡しで返すようにしています．(値が更新されるのは tail のみ)

デキュー操作の実装

デキュー操作は以下の 2 つの手順が必要になります．

キューからデータを取り出す
head をインクリメントする

図3 デキュー操作のイメージ図

エンキュー操作と同じように tail と配列の最大要素数の余剰を計算し，添え字にするのがポイントです．

/**
 * 配列からデキューする
 * @param[in,out] queue 配列
 * @param[in,out] head キューの先頭要素
 * @param[in,out] tail キューの末尾要素
 * @param[in] n 配列の要素数
 * @return デキューしたデータ
 */
int ArrayDequeue(int *queue, int *head, int *tail, size_t n) {
    if (*head != *tail) {
        return queue[(*head)++ % n];
    } else {
        return 0;
    }
}

head と tail は引数として受け取り，ポインタ渡しで返すようにしています．(値が更新されるのは head のみ)

C言語サンプルプログラム

上記で例に挙げた関数を使用して，配列を簡易的なキューとして使用する例を以下に示します．

/* header files */
#include <stdio.h>
#include <stdlib.h>

/* macros */
#define N 8

/* functions */
int ArrayEnqueue(int *queue, int data, int *head, int *tail, size_t n);
int ArrayDequeue(int *queue, int *head, int *tail, size_t n);

/* main */
int main(void) {
    int queue[N];
    int head = 0, tail = 0;
    int data;

    /* 配列にエンキューする */
    ArrayEnqueue(queue, 10, &head, &tail, N);
    printf("Enqueue: %d\n", 10);

    ArrayEnqueue(queue, 20, &head, &tail, N);
    printf("Enqueue: %d\n", 20);

    ArrayEnqueue(queue, 30, &head, &tail, N);
    printf("Enqueue: %d\n", 30);

    ArrayEnqueue(queue, 40, &head, &tail, N);
    printf("Enqueue: %d\n", 40);

    /* 配列からデキューする */
    while ( tail - head ) {
        data = ArrayDequeue(queue, &head, &tail, N);
        printf("Dequeue: %d\n", data);
    }


    return EXIT_SUCCESS;
}

/**
 * 配列にエンキューする
 * @param[in,out] queue 配列
 * @param[in] data データ
 * @param[in,out] head キューの先頭要素
 * @param[in,out] tail キューの末尾要素
 * @param[in] n 配列の要素数
 * @retval >=1 配列に格納されている要素の数
 * @retval 0 配列へのエンキューに失敗
 */
int ArrayEnqueue(int *queue, int data, int *head, int *tail, size_t n) {
    if (*head % n != (*tail + 1) % n) {
        queue[(*tail)++ % n] = data;
        return *tail - *head;
    } else {
        return 0;
    }
}

/**
 * 配列からデキューする
 * @param[in,out] queue 配列
 * @param[in,out] head キューの先頭要素
 * @param[in,out] tail キューの末尾要素
 * @param[in] n 配列の要素数
 * @return デキューしたデータ
 */
int ArrayDequeue(int *queue, int *head, int *tail, size_t n) {
    if (*head != *tail) {
        return queue[(*head)++ % n];
    } else {
        return 0;
    }
}

実行例

サンプルプログラムの実行結果は以下のようになります．

Enqueue: 10
Enqueue: 20
Enqueue: 30
Enqueue: 40
Dequeue: 10
Dequeue: 20
Dequeue: 30
Dequeue: 40

Cプログラマの必読書

たくさんあるC言語関連の書籍の中でも特に役に立った本です．よかったら参考にしてみてください．

C実践プログラミング第3版

C言語の実践的参考書．少々値段は張りますが初心者を脱しようとしている人は絶対に読むべきです．
文法だけでなく，コーディングスタイルやデバッグなど文字通り「実践的」なことが書かれているので非常にためになります．オライリーの本は，読みにくい本が多いのですが本書はとても読みやすくオススメです．

C言語ポインタ完全制覇 (標準プログラマーズライブラリ)

ポインタの解説書としては最高の書籍です．
この1冊でポインタを完全に理解することができます．全くの初学者が読むには敷居が高いですが，入門書を読み終えた後に読むと非常に有益です．

データ構造

配列を簡易的なキューとして使用する

スポンサー