キュー | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第6章

アルゴリズムとデータ構造編【データ構造】 第6章 キュー

先頭へ戻る

この章の概要

この章の概要です。


キュー

この章では、キューというデータ構造を説明します。前章のスタックと並んで重要なデータ構造です。キューのことを待ち行列と呼ぶこともあります。

キューは、一番最初に格納したデータからしか取り出せないという特徴があります。これを、先入れ先出しとか、FIFO (First In First Out) と呼びます。

キューへデータを格納することをエンキューといい、データを取り出すことをデキューといいます。

キューの構造のイメージは、待ち行列とも呼ばれるということから分かるように、現実世界で店などの前に行列を作ることと同じです。先に行列に加わった人から用を済ますことができ、後から来た人は行列の最後尾に並びます。それと同じ構造だと言えます。

キューも抽象データ構造であると考えられえますから、前章と同じように、配列版連結リスト版を作っていきたいと思います。

キューというデータ構造にとって、最低限必要な機能は以下のものです。

配列による実装

まずは配列を使った実装を確認します。

スタックが後入れ先出しで、キューが先入れ先出しです。これはデータが取り出されるときの法則が異なるだけであり、何となく、pop の関数を dequeue の操作になるように書き換えるだけで済みそうに思えるかも知れません。しかし、配列による実装は、意外にも簡単にはいきません。

最初に enqueue されたデータは array[0] にあるとします。続けて2個のデータを enqueue すると、array[1], array[2] に格納されます。

次に dequeue を行うと、array[0] のデータを取り除くことになります。続けて dequeue すると、array[1] を取り除きます。

更に続けて enqueue します。今度は、array[3] に格納されます。この時点で、データが格納されている位置は、array[2] と array[3] です。

このように、enqueue と dequeue を繰り返していくうちに、先頭のデータが入っている位置(=次に dequeue される位置)が後方へずれていってしまうのです。配列は要素数が決まっているので、いずれ、領域が足りなくなります(この例の場合、array[0],array[1] は2度と使われることがないので、領域が無駄になっています)。

この問題を解決するには、配列の末尾まで使いきってしまったら、先頭に戻ってこさせるような仕組みを導入します。これは、データを格納する領域(バッファ)が、輪のように周回しているような状態であることから、リングバッファと呼ばれます。配列版キューを実装するには、配列をリングバッファのように利用することがポイントです。

では、前章と同様に、実験ができる形でプログラムを作っていきます。

/* main.c */

#include <stdio.h>
#include <string.h>
#include "queue.h"


/* コマンド */
enum Cmd_tag {
    CMD_ENQUEUE,
    CMD_DEQUEUE,
    CMD_EXIT,

    CMD_NUM
};

/* コマンド文字列の種類 */
enum CmdStr_tag {
    CMD_STR_SHORT,
    CMD_STR_LONG,

    CMD_STR_NUM
};

/* コマンドの戻り値 */
enum CmdRetValue_tag {
    CMD_RET_VALUE_CONTINUE,
    CMD_RET_VALUE_EXIT,
};

/* コマンド文字列 */
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
    { "n", "enqueue" },
    { "d", "dequeue" },
    { "e", "exit" }
};


static void create_queue(void);
static void delete_queue(void);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_enqueue(void);
static enum CmdRetValue_tag cmd_dequeue(void);
static enum CmdRetValue_tag cmd_exit(void);
static void enqueue_elem(int value);
static int dequeue_elem(void);
static void get_line(char* buf, size_t size);


/* コマンド実行関数 */
typedef enum CmdRetValue_tag (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
    cmd_enqueue,
    cmd_dequeue,
    cmd_exit
};


static Queue gQueue;


int main(void)
{
    create_queue();

    while( 1 ){
        print_explain();

        if( get_cmd() == CMD_RET_VALUE_EXIT ){
            break;
        }

        print_blank_lines();
    }

    delete_queue();

    return 0;
}

/* キューを作成 */
void create_queue(void)
{
    gQueue = queue_create( 128 );
}

/* キューを削除 */
void delete_queue(void)
{
    queue_delete( gQueue );
    gQueue = NULL;
}

/*
    説明文を出力
*/
void print_explain(void)
{
    puts( "コマンドを入力して下さい。" );
    printf( " キューに要素を入れる: %s (%s)\n", CMD_STR[CMD_ENQUEUE][CMD_STR_SHORT], CMD_STR[CMD_ENQUEUE][CMD_STR_LONG] );
    printf( " キューから要素を取り出す: %s (%s)\n", CMD_STR[CMD_DEQUEUE][CMD_STR_SHORT], CMD_STR[CMD_DEQUEUE][CMD_STR_LONG] );
    printf( " 終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
    puts( "" );
}

/*
    空白行を出力
*/
void print_blank_lines(void)
{
    puts( "" );
    puts( "" );
}

/*
    コマンドを受け付ける
*/
enum CmdRetValue_tag get_cmd(void)
{
    char buf[20];
    enum Cmd_tag cmd;
    int i;

    get_line( buf, sizeof(buf) );

    cmd = CMD_NUM;
    for( i = 0; i < CMD_NUM; ++i ){
        if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
         || strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
        ){
            cmd = i;
            break;
        }
    }

    if( 0 <= cmd && cmd < CMD_NUM ){
        return CMD_FUNC[i]();
    }
    else{
        puts( "そのコマンドは存在しません。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    enqueueコマンドの実行
*/
enum CmdRetValue_tag cmd_enqueue(void)
{
    char buf[40];
    int value;

    puts( "キューに入れる数値データを入力して下さい。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    enqueue_elem( value );

    return CMD_RET_VALUE_CONTINUE;
}

/*
    dequeueコマンドの実行
*/
enum CmdRetValue_tag cmd_dequeue(void)
{
    if( queue_is_empty( gQueue ) ){
        puts( "キューは空です。" );
    }
    else{
        printf( "%d を降ろしました。\n", dequeue_elem() );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    exitコマンドの実行
*/
enum CmdRetValue_tag cmd_exit(void)
{
    puts( "終了します。" );

    return CMD_RET_VALUE_EXIT;
}

/*
    要素を入れる

    引数:
        value:	入れる要素の数値データ。
*/
void enqueue_elem(int value)
{
    queue_enqueue( gQueue, value );
}

/*
    要素を取り出す

    戻り値:
        取り出された要素。
*/
int dequeue_elem(void)
{
    return queue_dequeue( gQueue );
}

/*
    標準入力から1行分受け取る

    受け取った文字列の末尾には '\0' が付加される。
    そのため、実際に受け取ることができる最大文字数は size - 1 文字。

    引数:
        buf:    受け取りバッファ
        size:   buf の要素数
    戻り値:
        buf が返される
*/
void get_line(char* buf, size_t size)
{
    fgets(buf, size, stdin);

    /* 末尾に改行文字があれば削除する */
    char* p = strchr(buf, '\n');
    if (p != NULL) {
        *p = '\0';
    }
}
/* queue.c */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queue.h"

static int get_next_index(Queue queue, int index);
static void* xmalloc(size_t size);


struct Queue_tag {
    int*    data;    /* 要素を格納する動的配列 */
    int     size;    /* data の要素数 */
    int     front;   /* 先頭の要素の位置 */
    int     tail;    /* 末尾の要素の位置 */
};


/* キューを作る */
Queue queue_create(int size)
{
    struct Queue_tag* queue;

    assert( size > 0 );

    /* front == tail を空の状態にしようとすると、配列全体を使い切った状態を作れない。
       そこで、指定された size を +1 して、1つ余分に領域を確保しておく。
    */
    size += 1;

    queue = xmalloc( sizeof(struct Queue_tag) );
    queue->data  = xmalloc( sizeof(int) * size );
    queue->size  = size;
    queue->front = 0;
    queue->tail  = 0;

    return queue;
}

/* キューを削除する */
void queue_delete(Queue queue)
{
    free( queue->data );
    free( queue );
}

/* キューに要素を入れる */
void queue_enqueue(Queue queue, int value)
{
    assert( get_next_index(queue, queue->tail) != queue->front );

    queue->data[queue->tail] = value;

    /* 次に要素を入れるときに使う位置を求める */
    /* リングバッファ構造なので、単純に +1 するだけではダメ */
    queue->tail = get_next_index( queue, queue->tail );
}

/* キューから要素を取り出す */
int queue_dequeue(Queue queue)
{
    int pop_value;

    assert( !queue_is_empty(queue) );

    pop_value = queue->data[queue->front];

    /* 先頭から要素が1つ取り出されるので、先頭位置を更新する */
    /* リングバッファ構造なので、単純に +1 するだけではダメ */
    queue->front = get_next_index( queue, queue->front );

    return pop_value;
}

/* キューが空かどうか調べる */
int queue_is_empty(Queue queue)
{
    return queue->front == queue->tail;
}


/* 1つ後ろの添字を取得する */
int get_next_index(Queue queue, int index)
{
    return (index + 1) % queue->size;
}

/* エラーチェック付きの malloc関数 */
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}
/* queue.h */

#ifndef QUEUE_H
#define QUEUE_H


typedef struct Queue_tag* Queue;


/*
    キューを作る

    引数:
        size:	格納できる要素数
    戻り値:
        作成されたキュー。
        使い終わったら、queue_delete関数に渡して削除する。
*/
Queue queue_create(int size);

/*
    キューを削除する

    引数:
        queue:	キュー
*/
void queue_delete(Queue queue);

/*
    キューに要素を入れる

    引数:
        queue:	キュー
        value:	入れる要素
*/
void queue_enqueue(Queue queue, int value);

/*
    キューから要素を取り出す

    引数:
        queue:	キュー
    戻り値:
        取り出された要素
*/
int queue_dequeue(Queue queue);

/*
    キューが空かどうか調べる

    引数:
        queue:	キュー
    戻り値:
        キューが空であれば 0以外を返し、空でなければ 0 を返す。
*/
int queue_is_empty(Queue queue);


#endif

プログラムの作りは、前章のスタックのサンプルと同じになっています。

ポイントとなるのは、queue.c だけです。

まず、構造体Queue_tag の実装ですが、最上段の位置だけ管理していればよかったスタックと違い、キューでは(というより、リングバッファでは)先頭と末尾の両方を管理する必要があります。 先頭(front) が取り出される側、末尾(tail) が入れる側になります。

front と tail はいずれも、queue_create関数で新規のキューを作成した段階では、0 になっています。このように、front と tail の値が一致している状態を、キューが空の状態となるように実装しています。ただし、front や tail が 0 であるかどうかは無関係だという点に注意して下さい。

例えば、enqueue を 1回すると「front == 0, tail == 1」になり、その後 dequeue すると「front == 1, tail == 1」になりますが、この状態も空なのです。実際の値とは関係なく「front == tail」かどうかだけが判断の基準になります。

なお、このように実装すると、配列全体を使い切ることができなくなります。そこで、queue_create関数では、仮引数size の値をこっそり +1 しています。

queue_create関数の中で size を +1 するのをやめて、「指定した数 - 1 までしか要素を格納できない」ことを仕様として、queue.h の queue_create関数の説明コメントに書いておくという方法も考えられます。しかしそういう方法を採ると、連結リスト版の方もその仕様に合わせて実装しないといけなくなります。抽象データ型という考え方から言って、特定の実装に依存した部分は、実装側(queue.c) の中だけで解決すべきです。

enqueue するときには、まずキューが満杯になっていないかどうかを確認します。ここで、満杯かどうかをどう判断すればいいかが問題になります。前述の通り、front == tail の状態のとき空の状態であるという前提を設けたのですから、満杯の状態というのは、tail + 1 == front の状態になります。例えば、最大数10 のキューであれば、「front == 0, tail == 9」のときは満杯です。

しかし実際にはリングバッファになっているので、front や tail の値は増え続けた後、0 に戻ってきます。この点まで考慮すると、満杯の状態というのは、「(tail + 1) % max_size == front」のときです。max_size は、キューの最大数のことです。

このように、リングバッファでは、"末尾の次は先頭" なので、その辺りを踏まえて添字を計算しなければならない機会が多くあります。サンプルでは、get_next_index関数を作り、これを何箇所かで使用しています。

dequeue の方も、基本的な考え方は同じです。

まずはキューが既に空になっていないかを確認します。この判定は、最初に作った前提の通り、「front == tail」かどうかです。これは、外部へ公開するインタフェースの一部として、queue_is_empty関数に実装されているので、そのまま使えます。

要素を取り出した後、front の位置をずらしますが、ここでもリングバッファであることを踏まえて、get_next_index関数を使って添字計算を行っています。

配列版の実装の利点と欠点は、スタックのときと同様です。この章のまとめのところで改めて書くので、ここでは省略させて頂きます。


連結リストによる実装

次に、連結リストによる実装を試してみます。

連結リストの場合の実装は、配列版よりも簡単です。スタックのときとの違いは、連結リストの先頭と末尾を指すポインタを両方持つ必要がある点だけです。配列版との違いは、queue.c だけなので、queue.c だけ掲載します。

/* queue.c */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queue.h"

static void* xmalloc(size_t size);


struct QueueList_tag {
    struct QueueList_tag*  next;    /* 次の要素へのポインタ */
    int                    value;   /* 要素の値 */
};

struct Queue_tag {
    struct QueueList_tag*  front;   /* 先頭の要素へのポインタ */
    struct QueueList_tag*  tail;    /* 末尾の要素へのポインタ */
};


/* キューを作る */
Queue queue_create(int size)
{
    struct Queue_tag* queue;

    assert( size > 0 );

    queue = xmalloc( sizeof(struct Queue_tag) );
    queue->front = NULL;
    queue->tail = NULL;

    return queue;
}

/* キューを削除する */
void queue_delete(Queue queue)
{
    struct QueueList_tag* p = queue->front;
    struct QueueList_tag* tmp;

    /* 連結リストの要素を削除 */
    while( p != NULL ){
        tmp = p->next;
        free( p );
        p = tmp; 
    }

    free( queue );
}

/* キューに要素を入れる */
void queue_enqueue(Queue queue, int value)
{
    struct QueueList_tag* p;

    p = xmalloc( sizeof(struct QueueList_tag) );
    p->value = value;
    p->next = NULL;

    /* 新たな要素を末尾に置く */
    if( queue->tail != NULL ){
        queue->tail->next = p;
    }
    queue->tail = p;

    if( queue->front == NULL ){
        queue->front = p;
    }
}

/* キューから要素を取り出す */
int queue_dequeue(Queue queue)
{
    struct QueueList_tag* p;
    int pop_value;

    assert( !queue_is_empty(queue) );

    p = queue->front;

    pop_value = p->value;
    queue->front = p->next;

    /* 取り出された要素が末尾の要素でもあったとき(キューの中に要素が1つしか無かったとき)
       には、tailポインタの付け替えも必要 */
    if( p == queue->tail ){
        queue->tail = NULL;
    }

    free( p );

    return pop_value;
}

/* キューが空かどうか調べる */
int queue_is_empty(Queue queue)
{
    return queue->front == NULL;
}


/* エラーチェック付きの malloc関数 */
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}

構造体Queue_tag が持つ front と tail が、それぞれ連結リストの先頭の要素と、末尾の要素とを管理しています。enqueue のときには tail側に追加し、dequeue のときには front側から取り出すように実装します。

front と tail は、queue_create関数で、NULL で初期化されています。キューが空かどうかの判断は、front が NULL かどうかで行うようにしています。配列版のときのように、front == tail で判定すると、要素が1つだけ格納されているときにも空と判定されてしまうので不適切です。

enqueue するときに、キューが満杯かどうかを確認する必要はありません。連結リストなら、メモリが許す限りは、新しい要素を作り続けられるからです。

連結リストのこの特性のおかげで、末尾から先頭に戻ってこさせるような実装にする必要もありません。配列版でのリングバッファのイメージが強いと、循環リストにしないといけないような錯覚に陥るかも知れませんが、その必要はありません。

少し面倒なのは、要素は tail側に追加されるものの、最初の1個に関しては front も変更しないといけないという点です。これをしないと、キューが空かどうかの条件式 front == NULL が、いつまでも真のままになってしまいます。

dequeue するときには、キューが空かどうかを調べます。これは前述のように、front が NULL かどうかで調べられます。この部分は queue_is_empty関数に関数化されていますから、これを呼び出すだけです。

enqueue のときと同様、こちらでも少し面倒な作業があります。取り出される要素が、末尾の要素だった場合(これはキューの中身が1個しか無いときにだけ起こります)、tail も変更しないといけません。これをしないと、tail が不正な場所を指し続けてしまいます。

連結リスト版の実装の利点と欠点は、スタックのときと同様です。この章のまとめのところで改めて書くので、ここでは省略させて頂きます。

まとめ

配列版と連結リスト版の長所と短所をまとめておきます。

実装方法 長所 短所
配列
  • enqueue/dequeue ともに高速に行える。
  • キューが満杯になる可能性を考慮しなければならない。
  • 事前に大きさを決めなければならず、決定を誤ると、多くの領域が無駄になってしまう。
連結リスト
  • メモリが許す限り、幾らでも enqueue できる。
  • enqueue/dequeue のたびに動的なメモリ確保および解放処理が発生するため、速度的に不利。
  • 次の要素を指し示すポインタを保持しなければならないので、メモリの使用効率が劣る。

このように、長所・短所はスタックと同様です。これは結局、実装方法の問題に帰結するからです。


練習問題

問題① queue.c/h に、次の機能を追加して下さい。

問題② 2つのキューを作り、一方のキューに適当なデータを積みます。その後、空になるまで dequeue を繰り返し、そのつど、他方のキューへ dequeue された要素を enqueue していくことを繰り返すプログラムを作成して下さい。この作業を終えた後、キューの中身はどうなっていますか?
前章の練習問題でスタックで同じことをしました。キューならどのような結果になるでしょう?)

問題③ queue.c を改造して、キューの中に同じ値を持った要素が重複しないようにして下さい。


解答ページはこちら


参考リンク



更新履歴

'2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

'2018/2/12 サンプルプログラムの改善(fgets が受け取った改行文字の削除の方法を修正。const、static の付加)

'2017/11/13 サンプルプログラムで、存在しないコマンドが入力されたときに、未初期化の変数を参照していたのを修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2014/12/20 サンプルプログラムで、コマンド処理の方法を整理。

'2011/10/7 新規作成。



前の章へ(第5章 スタック)

次の章へ(第7章 二分木)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS