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

問題① 🔗

問題①　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関数の中身とほとんど一緒です。同じ処理を２箇所に書くべきでないと考えれば、処理を別の関数に括り出してしまった方がいいかもしれません。たとえば次のようになります。

/*
    キューを削除する
*/
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 が少し遅くなります。最初に方針をはっきり決めて、それに従って実装することが重要です。

問題② 🔗

問題②　２つのキューを作り、一方のキューに適当なデータを積みます。その後、空になるまで 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;
}

実行結果：

１つ目のキュー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;
    }
}

参考リンク 🔗

Programming Place Plus　アルゴリズムとデータ構造編　参考書籍
　– 当サイトの参考書籍一覧ページ。アルゴリズムとデータ構造に関する書籍を多数紹介。
Programming Place Plus　アルゴリズムとデータ構造編　リンク集
　– 当サイトの参考Webサイト集。アルゴリズムとデータ構造の全般的な学習に有益なサイトを紹介。

更新履歴 🔗

2019/9/23
- 全体的に見直して、大幅に修正
2019/9/4
- 対応規格を C95 から C99 へ上げる
  - コメントに // を使う
2019/9/3
- 対応規格を C95 から C99 へ上げる
  - 変数宣言をブロックの先頭以外でも行う
2019/9/2
- 対応規格を C95 から C99 へ上げる
  - ループ制御変数を for文の初期設定式で宣言するように修正
’2011/10/7
- 新規作成。

第６章のメインページへ

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

Programming Place Plus のトップページへ

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー