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

トップページアルゴリズムとデータ構造編【データ構造】第6章

問題①

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


まずは配列版です。 queue.c の追加部分だけを取り上げます。

/*
    キューの中身を出力する
*/
void queue_report(Queue queue)
{
    if( queue_is_empty(queue) ){
        return;
    }

    size_t index = queue->front;
    size_t count = 0;
    do {
        printf( "%zu:  %d\n", count, queue->data[index] );
        count++;
        index = get_next_index( queue, index );
    } while( index != queue->tail );
}

/*
    キューに格納されている要素数を返す
*/
size_t queue_get_size(Queue queue)
{
    if( queue_is_empty(queue) ){
        return 0;
    }

    size_t index = queue->front;
    size_t count = 0;
    do {
        count++;
        index = get_next_index( queue, index );
    } while( index != queue->tail );

    return count;
}

/*
    キューを空にする
*/
void queue_clear(Queue queue)
{
    queue->front = 0;
    queue->tail = 0;
}

中身を出力する際も、要素数を数える際も、添字を先へ進めるには get_next_index関数を使うことに注意してください。

要素数を返す関数は、実際に front から tail までの要素の個数を数えて返しています。

queue_clear関数は、front と tail の値が同じになるようにしてやるだけです。0 である必要はありませんが、0 にするのが自然でしょう。

次に、連結リスト版の実装です。

/*
    キューの中身を出力する
*/
void queue_report(Queue queue)
{
    struct QueueList_tag* p = queue->front;
    size_t count = 0;
    while( p != NULL ){
        printf( "%zu:  %d\n", count, p->value );
        count++;
        p = p->next;
    }
}

/*
    キューに格納されている要素数を返す
*/
size_t queue_get_size(Queue queue)
{
    struct QueueList_tag* p = queue->front;
    size_t count = 0;

    while( p != NULL ){
        count++;
        p = p->next;
    }

    return count;
}

/*
    キューを空にする
*/
void queue_clear(Queue queue)
{
    struct QueueList_tag* p = queue->front;
    struct QueueList_tag* tmp;

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

    queue->front = NULL;
    queue->tail = NULL;
}

queue_report関数は、front から始めて、nextポインタを末尾の要素までたどっていきます。tail と比較する方法もありますが、単方向線形リストなので nextポインタが NULL かどうかを調べれば、そこは間違いなく末尾です。

queue_get_size関数の実装も、考え方としては同じです。

queue_clear関数は、queue_delete関数の中身とほとんど一緒です。同じ処理を2箇所に書くべきでないと考えれば、処理を別の関数に括り出してしまった方がいいかもしれません。たとえば次のようになります。

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

/*
    キューを空にする
*/
void queue_clear(Queue queue)
{
    clear( queue );

    queue->front = NULL;
    queue->tail = NULL;
}

/*
    キューを空にする
*/
void clear(Queue queue)
{
    struct QueueList_tag* p = queue->front;
    struct QueueList_tag* tmp;

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

clear関数は、queue.c の内部だけで使う関数なので、queue.h には書かないようにしましょう。


配列版、連結リスト版のどちらの実装でもそうですが、queue_get_size関数は、実際に要素数をカウントして返すようになっています。これは、要素数が多くなればなるほど、処理時間がかかる実装方法です。

これが問題だと考えるのなら、構造体Queue_tag に、現在の要素数を表すメンバを追加してやり、enqueue/dequeue のときに +1/-1 、clear のときに 0 にクリアするようにすれば、queue_get_size関数の中で要素数をカウントし直す必要がなくなるので、次のように変更できます。

/*
    キューに格納されている要素数を返す
*/
size_t queue_get_size(Queue queue)
{
    return queue->count;
}

これなら、queue_get_size関数は高速になりますし、要素数が何個あっても、つねに一定の速度で動作します。

ただし、これはどちらが正しいということはありません。queue_get_size関数が安定して高速になる代わりに、構造体Queue_tag の countメンバをインクリメントしたりデクリメントしたりする必要が出てくるので、enqueue や dequeue が少し遅くなります。最初に方針をはっきり決めて、それに従って実装することが重要です。

問題②

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


プログラム自体は、前章の練習問題とほとんど同じになります。

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

int main(void)
{
    static const size_t QUEUE_SIZE = 8;

    Queue a = queue_create( QUEUE_SIZE );
    Queue b = queue_create( QUEUE_SIZE );

    // a のキューに 0~QUEUE_SIZE-1 を順番に enqueue する
    for( size_t i = 0; i < QUEUE_SIZE; ++i ){
        queue_enqueue( a, i );
    }

    // a のキューから dequeue し、b のキューへ enqueue する
    for( size_t i = 0; i < QUEUE_SIZE; ++i ){
        queue_enqueue( b, queue_dequeue( a ) );
    }

    // b のキューの中身を出力
    queue_report( b );

    return 0;
}

実行結果:

0:  0
1:  1
2:  2
3:  3
4:  4
5:  5
6:  6
7:  7

1つ目のキューa には 0,1,2… となるように要素を enqueue しています。すると先頭には 0 が、末尾には QUEUE_SIZE-1 = 7 が来ます。

この状態から dequeue を繰り返すと、0,1,2… という順番に取り出されることになります。この順番にキューb へ enqueue していくので、結果としてキューb には 0,1,2… という順番で積まれていきます。

つまり、一方のキューの中身を、他方へ単純に移し変えると、元のキューと同じ並びになります。スタックだと、逆順になってしまいましたが、キューだとこのような結果になります。

問題③

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


enqueue するときに、先にキューの中身を確認するようにします。これは、「キューの中から、特定の値を持った要素があるかどうかを調べる」処理があれば良いのですが、このような機能は、キューを使う側にとっても有用かもしれません。有用だと判断するのなら、この部分を関数化して、queue.h から公開しても良いでしょう。

この関数の配列版は、次のように実装できます。

/*
    キューに、指定の値を持った要素があるかどうか調べる
*/
bool queue_search(Queue queue, int value)
{
    size_t index = queue->front;
    do {
        if( queue->data[index] == value ){
            return true;
        }
        index = get_next_index( queue, index );
    } while( index != queue->tail );

    return false;
}

仮引数value に一致する値があれば、true を返し、なければ false を返します。この関数を使って enqueue の前に要素が重複しないようにします。

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

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

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

連結リスト版でも、同じ考え方で実装できます。

/*
    キューに、指定の値を持った要素があるかどうか調べる
*/
bool queue_search(Queue queue, int value)
{
    struct QueueList_tag* p = queue->front;

    while( p != NULL ){
        if( p->value == value ){
            return true;
        }
        p = p->next;
    }

    return false;
}

/*
    キューに要素を入れる
*/
void queue_enqueue(Queue queue, int value)
{
    assert( !queue_search(queue, value) );

    struct QueueList_tag* 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;
    }
}



参考リンク


更新履歴

’2011/10/7 新規作成。



第6章のメインページへ

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る