先頭へ戻る

スタック 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第5章

Programming Place Plus トップページアルゴリズムとデータ構造編

先頭へ戻る

問題①

問題① stack.c/h に、スタックの中身を標準出力へ出力する関数を追加してください。


stack.h には関数のプロトタイプを追加します。

/*
    スタックの中身を出力する

    引数:
        stack:  スタック
*/
void stack_report(Stack stack);

配列版のスタックなら、実装は次のようになるでしょう。

/* スタックの中身を出力する */
void stack_report(Stack stack)
{
    for( size_t i = 0; i < stack->top; ++i ){
        printf( "%zu:  %d\n", i, stack->data[i] );
    }
}

連結リスト版は、スタックの最上段がリストの先頭にあるので、上記の配列版と同じ順番で出力しようと思うと、リストを逆方向からたどっていく必要があります。単方向線形リストで実装されている場合、これは厄介な作業です。

基本的にデバッグ専用の関数と言えますから、楽をして、最上段から順番に出力してしまうのでも十分ですが、まじめに底の要素から並べるのなら、いったん、連結リストを逆順になるように並べ替えてしまうと手段があります。これは、第3章の練習問題②で実装したことがありますから、それを手直しして利用します。

/*
    リストを逆順にする。

    引数:
        head:   リストの先頭要素へのポインタのポインタ。
*/
void reverse_list(struct StackList_tag** head)
{
    struct StackList_tag* p = *head;
    struct StackList_tag* work = NULL;

    while( p != NULL ){

        // この後、p->next を書き換えるので退避しておく
        struct StackList_tag* tmp = p->next;

        // 1つ前の要素を p->next に設定
        // "1つ前の要素" とは先頭から末尾へ向かう流れの中でのことを言っており、
        // 逆順になった後のことを考えると、"次の要素" のことを言っている。
        // 初回は何もないので NULL になっている
        p->next = work;

        // 現在の注目要素を保存
        // これは、次のループにおいては "1つ前の要素" になる
        work = p;

        // 最初に退避させておいた p->next を次の注目要素として復帰させる
        p = tmp;
    }

    // 最終的な work は、逆順になった後の先頭要素
    *head = work;
}

これを使って、stack_report関数を実装します。

/*
    スタックの中身を出力する
*/
void stack_report(Stack stack)
{
    // リストを逆順にする
    reverse_list( &stack->head );

    struct StackList_tag* p = stack->head;
    int count = 0;
    while( p != NULL ){
        printf( "%d:  %d\n", count, p->value );
        count++;
        p = p->next;
    }

    // 再度、リストを逆順にして元に戻す
    reverse_list( &stack->head );
}

いったん、reverse_list関数を使って連結リストを逆順に並べ替えた後、先頭から順番に要素の値を出力します。出力作業を終えたら、再度、reverse_list関数を呼び出して、元の順番に並べ直して終了です。

なお、先ほど、基本的にデバッグ用の関数であると書きました。これは、そもそもスタックというデータ構造は、途中の要素を参照できるものではないはずだからです。便利そうだからといって、本来のインターフェースを壊すような機能を作るのは得策ではありません。

一方で、stack_report関数のような関数は、デバッグ作業には大きな助けになりますから、デバッグ専用だという割り切って実装するのが良いでしょう。

問題②

問題② 要素を降ろすことなく、最上段にある要素を参照したいことがよくあります。このような操作は peek あるいは top操作と呼ばれるのですが、これを実現する関数を stack.c/h に追加してください。


stack.h には関数のプロトタイプを追加します。

/*
    スタックの最上段の要素を調べる

    引数:
        stack:  スタック
    戻り値:
        最上段にある要素=次に pop される要素
*/
int stack_peek(Stack stack);

配列版の実装は次のようになります。

/*
    スタックの最上段の要素を調べる
*/
int stack_peek(Stack stack)
{
    assert( !stack_is_empty(stack) );

    return stack->data[stack->top - 1];
}

連結リスト版なら、次のようになります。

/*
    スタックの最上段の要素を調べる
*/
int stack_peek(Stack stack)
{
    assert( !stack_is_empty(stack) );

    return stack->head->value;
}

peek操作は、最上段の要素を pop せずに参照するというだけですから、stack_pop関数の実装から、最上段の位置を表す場所を調整するコードを取り除けば良いということです。

なお、スタックが空の場合に、異常な動作にならないように対策しましょう。ここでは assert で止めています。

問題③

問題③ 2つのスタックを作り、一方のスタックに適当なデータを積みます。その後、空になるまで pop を繰り返し、そのつど、他方のスタックへ pop された要素を push していくことを繰り返すプログラムを作成してください。この作業を終えた後、スタックの中身はどうなっていますか?


今度は main.c の方を作ります。stack.c/h は、問題①で作った stack_report関数が使えるような状態にしておいてください。

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

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

    Stack a = stack_create( STACK_SIZE );
    Stack b = stack_create( STACK_SIZE );

    // a のスタックに 0~STACK_SIZE-1 を順番に push する
    for( size_t i = 0; i < STACK_SIZE; ++i ){
        stack_push( a, i );
    }

    // a のスタックから pop し、b のスタックへ push する
    for( size_t i = 0; i < STACK_SIZE; ++i ){
        stack_push( b, stack_pop( a ) );
    }

    // b のスタックの中身を出力
    stack_report( b );

    return 0;
}

実行結果:

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

1つ目のスタックa には 0,1,2… となるように要素を push しています。すると最上段には STACK_SIZE-1 = 7 が来ます。

この状態から pop を繰り返すと、7,6,5… という順番に取り出されることになります。この順番にスタックb へ push していくので、結果としてスタックb には 0,1,2… という順番で積まれていきます。

つまり、一方のスタックの中身を、他方へ単純に移し変えると、逆順に積まれるということになります。

問題④

問題④ この章の配列版のサンプルでは、stack_create関数に渡した要素数を超えたとき assert によって停止させています。これをやめて、領域が不足したときには、領域を倍に自動的に拡張するように stack.c を書き換えてください。


stack_push関数の実装だけを修正します。

/*
    スタックに要素を積む
*/
void stack_push(Stack stack, int value)
{
    if( stack->top >= stack->size ){
        // 領域が足りない場合は、2倍に拡張する

        stack->size *= 2;
        int* tmp = realloc( stack->data, sizeof(int) * stack->size );
        if( tmp == NULL ){
            stack_delete( stack );
            fputs( "スタック領域の拡張に失敗しました。", stderr );
            exit( EXIT_FAILURE );
        }
        stack->data = tmp;
    }

    stack->data[stack->top] = value;
    stack->top += 1;
}

領域が足りなくなったら、realloc関数を呼び出して拡張しています。


参考リンク


更新履歴

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

’2011/9/30 新規作成。



第5章のメインページへ

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー