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

この章の概要 🔗

この章の概要です。

スタック
配列による実装
連結リストによる実装
まとめ
練習問題
参考リンク
更新履歴

スタック 🔗

この章では、スタックというデータ構造を説明します。

スタックは非常に重要なデータ構造です。たとえ、自分でスタックを実装することがないとしても、色々な場面でその考え方が登場するので、確実に理解しておきましょう。

スタックは、データの入れ方と取り出し方に特徴があります。スタックは、一番最後に格納したデータしか取り出せません。このような特徴を、後入れ先出しだとか、LIFO (Last In First Out)と呼びます。

後入れ先出しのイメージとして、机の上に積み重ねた本がよく使われます。本をどんどん積んでいくとすれば、上へ上へ重ねていくことになるでしょう。逆に、積み重なった本を手に取るとすれば、一番上にある本から順番に取ります。このとき、１冊１冊の本が、スタックに格納されたデータであるというわけです。

スタックにデータを格納することを、プッシュ（積む）と表現し、また、データを取り出すことを、ポップ（降ろす）と表現します。

スタックにとって、最低限必要な機能は以下のとおりです。

データを積む (push)
データを降ろす (pop)

これらの機能を持ってさえいれば、スタック自身がどのようにデータを管理していても構わないといえます。

このように、必要な機能だけを提供し、それ以外を不用意に利用者に見せないように、データ構造を実現した型を抽象データ型と呼びます。

実際には、push と pop に加えて、補助的な機能が必要かもしれません。よく必要になるのは、

スタックが空かどうか調べる (is_empty)

です。

スタックが空のときに pop を呼び出したらどうなるのか、という問題があります。int型のデータを管理しているスタックが空だったとき、pop は何を返せばいいのでしょうか？　どうしても、エラーの類として扱わざるを得ないため、pop を呼び出す前に、呼び出し側で確認できる機能が欲しいのです。

また、スタックに積まれているデータを、スタックが空になるまで pop したいという場面もあるでしょう。そういうときにも、is_empty の機能が欲しくなります。

当然、スタックは複数のデータを保持できるわけですが、具体的にはどのような形で保持すればよいでしょうか。

スタックを抽象データ型であると考えると、スタックを使う側に push、pop、is_empty といった最小限の機能が公開されていれば、内部でデータをどのように管理しても構わないということになります。配列を使っても、連結リストを使っても（あるいはそれ以外の何かでも）構わないのです。

抽象データ “型” なので、まずはスタックを型として表現しましょう。

struct Stack_tag {
    // 複数個のデータがある。
    // その管理は、配列で行ってもいいし、連結リストで行ってもいい。
};

抽象データ型の発想では、値の管理をどうするかだけでなく、提供すべき機能のことも考えなければなりません。処理まで含めた “型” なのです。

この考え方はＣ言語プログラマーには馴染みがないかもしれません。オブジェクト指向プログラミング言語においてのオブジェクトの考え方とほぼ同じです。つまり、データと処理をひとまとめにします。

提供するべき機能（つまり push、pop、is_empty）は、関数として用意すればいいでしょう。スタックがデータをどのように管理しているとしても、使用者に提供する関数のかたちを変えないことが重要です。変えていいのは、関数の中身の実装だけです。

Ｃ言語でいえば、ヘッダファイルに公開する関数宣言を記述し、これは変更しないようにします。そして、ソースファイルのほうに実装を書けば、実装はいつでも変更可能になります。

// ヘッダファイル側

// 機能を公開する。これらは一度決めたら変えない
void stack_push(struct stack_tag* stack, int value);
int stack_pop(struct stack_tag* stack);
bool stack_is_empty(const struct stack_tag* stack);

// ソースファイル側

void stack_push(struct stack_tag* stack, int value)
{
    // データが配列で管理されているなら、配列に存在する最後の要素の後ろへ格納するだろうし、
    // 連結リストで管理されているなら、新しい要素を生成して登録するだろう。
    // その違いは、stack_push関数を呼び出す側からはみえない。
}

int stack_pop(struct stack_tag* stack)
{
    // データが配列で管理されているなら、配列の最後の要素を取り除いて、その値を返すだろうし、
    // 連結リストで管理されているなら、該当要素を解放して、その値を返すだろう。
    // その違いは、stack_pop関数を呼び出す側からはみえない。
}

bool stack_is_empty(const struct stack_tag* stack)
{
    // 空かどうかを判定して返す。
    // データ構造による違いは、stack_is_empty関数を呼び出す側からはみえない。
}

本章では、データ管理に配列を使う実装方法を見た後、連結リストを利用した実装方法も取り上げます。

配列による実装 🔗

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

// main.c

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


// コマンド
enum Cmd_tag {
    CMD_PUSH,
    CMD_POP,
    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] = {
    { "u", "push" },
    { "o", "pop" },
    { "e", "exit" }
};


static void create_stack(void);
static void delete_stack(void);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_push(void);
static enum CmdRetValue_tag cmd_pop(void);
static enum CmdRetValue_tag cmd_exit(void);
static void push_elem(int value);
static int pop_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_push,
    cmd_pop,
    cmd_exit
};


static Stack gStack;


int main(void)
{
    create_stack();

    while( 1 ){
        print_explain();

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

        print_blank_lines();
    }

    delete_stack();

    return 0;
}

/* 
    スタックを作成
*/
void create_stack(void)
{
    gStack = stack_create( 128 );
}

/*
    スタックを削除
*/
void delete_stack(void)
{
    stack_delete( gStack );
    gStack = NULL;
}

/*
    説明文を出力
*/
void print_explain(void)
{
    puts( "コマンドを入力してください。" );
    printf( "　スタックに要素を積む: %s (%s)\n", CMD_STR[CMD_PUSH][CMD_STR_SHORT], CMD_STR[CMD_PUSH][CMD_STR_LONG] );
    printf( "　スタックから要素を降ろす: %s (%s)\n", CMD_STR[CMD_POP][CMD_STR_SHORT], CMD_STR[CMD_POP][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];
    get_line( buf, sizeof(buf) );

    enum Cmd_tag cmd = CMD_NUM;
    for( int 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[cmd]();
    }
    else{
        puts( "そのコマンドは存在しません。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

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

    puts( "積む数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    push_elem( value );

    return CMD_RET_VALUE_CONTINUE;
}

/*
    popコマンドの実行
*/
enum CmdRetValue_tag cmd_pop(void)
{
    if( stack_is_empty( gStack ) ){
        puts( "スタックは空です。" );
    }
    else{
        printf( "%d を降ろしました。\n", pop_elem() );
    }

    return CMD_RET_VALUE_CONTINUE;
}

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

    return CMD_RET_VALUE_EXIT;
}

/*
    要素を積む

    引数：
        value:  積む要素の数値データ。
*/
void push_elem(int value)
{
    stack_push( gStack, value );
}

/*
    要素を降ろす

    戻り値：
        降ろされた要素。
*/
int pop_elem(void)
{
    return stack_pop( gStack );
}

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

    受け取った文字列の末尾には '\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';
    }
}

// stack.c

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

static void* xmalloc(size_t size);


struct Stack_tag {
    int*    data;    // 要素を格納する動的配列
    size_t  size;    // data の要素数
    size_t  top;     // 最上段の添字
};


/* 
    スタックを作る
*/
Stack stack_create(size_t size)
{
    assert( size > 0 );

    struct Stack_tag* stack = xmalloc( sizeof(struct Stack_tag) );
    stack->data = xmalloc( sizeof(int) * size );
    stack->size = size;
    stack->top = 0;

    return stack;
}

/*
    スタックを削除する
*/
void stack_delete(Stack stack)
{
    free( stack->data );
    free( stack );
}

/*
    スタックに要素を積む
*/
void stack_push(Stack stack, int value)
{
    assert( stack->top < stack->size );

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

/*
    スタックから要素を降ろす
*/
int stack_pop(Stack stack)
{
    assert( !stack_is_empty(stack) );

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

/*
    スタックが空かどうか調べる
*/
bool stack_is_empty(Stack stack)
{
    return stack->top <= 0;
}


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

// stack.h

#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

#include <stdbool.h>
#include <stddef.h>

typedef struct Stack_tag* Stack;


/*
    スタックを作る

    引数：
        size:   格納できる要素数
    戻り値：
        作成されたスタック。
        使い終わったら、stack_delete関数に渡して削除する。
*/
Stack stack_create(size_t size);

/*
    スタックを削除する

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

/*
    スタックに要素を積む

    引数：
        stack:  スタック
        value:  積む要素
*/
void stack_push(Stack stack, int value);

/*
    スタックから要素を降ろす

    引数：
        stack:  スタック
    戻り値：
        降ろされた要素
*/
int stack_pop(Stack stack);

/*
    スタックが空かどうか調べる

    引数：
        stack:  スタック
    戻り値：
        スタックが空であれば true を返し、空でなければ false を返す。
*/
bool stack_is_empty(Stack stack);

#endif

main.c は、これまでの章と同様に、実際の動作を確認するために、標準入力からコマンドを受け付けて実行するスタイルになっています。

前述したとおり、スタックの機能をヘッダファイル（stack.h）に関数宣言として公開し、その実装をソースファイル（stack.c）に隠しました。後で取り上げる連結リスト版は、stack.h を一切変更せずに実現できます。

stack.h では、Stack という型を typedef（Ｃ言語編第１９章参照）で作っています。

typedef struct Stack_tag* Stack;

その元になる struct Stack_tag の定義は、stack.c の方にあります。ヘッダファイルの側から、ソースファイル内にある構造体型の定義が見えるのかと疑問に思うかもしれませんが、これは可能です。

このテクニックを使うと、スタックの内部構造を隠せます。抽象データ型の考え方では、提供すべき機能だけが公開されているべきであって、中身が配列なのか連結リストなのかといった部分は見せたくないのです。

配列版のスタックでは、struct Stack_tag の定義は次のようになります。

struct Stack_tag {
    int*    data;    // 要素を格納する動的配列
    size_t  size;    // data の要素数
    size_t  top;     // 最上段の添字
};

data メンバがデータを管理する配列です。汎用的な作りを目指さなければ、固定配列でも構わないですが、必要な要素数は、使用者側のプログラムの内容によって大きく異なるでしょうから、使用者側から指定させて、動的に割り当てるようにします。

size メンバは、配列の大きさ（要素数）を管理するためにあります。前述のとおり、使用者側から指定させるので、このような変数をつくって覚えておきます。

top メンバは、最後にスタックに積まれたデータが、配列内のどの位置にあるかを管理する変数です。この位置をつねに管理しておくことで、push の際にはデータを格納すべき位置がすぐに定まりますし、pop の際には取り除くデータの位置がすぐ分かります。このような、スタックの最上段にあるデータを管理する仕組みは、スタックポインタと呼ばれることがあります。

スタックポインタの「ポインタ」は、Ｃ言語のポインタとは直接的には関係ありません。ポインタで実現することもできますが、このサンプルプログラムのように、単なる int型の値でも実現できます。

stack_create関数で動的にメモリ割り当てを行い、Stack型のオブジェクトを作り、そのポインタを返します。使い終わったら、stack_delete関数に渡すことで解放されます。

このような作りは、第３章で複数の連結リストを同時に使えるようにしたのと同じです。つまり、複数のスタックを同時に使えるようにするために、このような作りにしています（このサンプルプログラムでは、結局１つのスタックしか作っていませんが）。

stack_create関数を呼び出すたびに、新しいスタックが作られて、それは以前に作ったスタックとは別物です。

stack_push関数、stack_pop関数の引数が Stack型になっています。これはつまり、指定したスタックに対して、push や pop の操作を行うということです。

スタックを配列で実装する利点としては、添字による参照ができますから、push も pop も高速に行える点が挙げられます。

一方、スタックを配列で実装する欠点としては、いつか満杯になってしまう可能性を考えておかねばならない点が挙げられます。サンプルプログラムでは、満杯になったときの対処として、assert（Ｃ言語編第２８章参照）で停止させる道を選びましたが、エラーを呼び出し元に伝える手段を作ってもいいですし、realloc関数（Ｃ言語編　第３５章参照）を使って領域を拡張するといった手段も考えられます。

また、スタックを作るときに確保した要素数が大きすぎると、ほとんどの領域が使われずじまいになる可能性がありますから、メモリを無駄に浪費してしまうかもしれません。適切な要素数の選択が難しい場合、これは欠点といえます。

なお、配列は、途中の要素の挿入や削除を苦手としていますが（第１章）、スタックの実装に使う場合、末尾だけの操作で済むため、後続の要素をずらすような処理が起こらないので、問題になりません。

連結リストによる実装 🔗

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

// stack.c

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

static void* xmalloc(size_t size);


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

struct Stack_tag {
    struct StackList_tag*  head;    // 先頭の要素へのポインタ
};


/*
    スタックを作る
*/
Stack stack_create(size_t size)
{
    struct Stack_tag* stack = xmalloc( sizeof(struct Stack_tag) );
    stack->head = NULL;

    return stack;
}

/*
    スタックを削除する
*/
void stack_delete(Stack stack)
{
    struct StackList_tag* p = stack->head;
    struct StackList_tag* tmp;

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

    free( stack );
}

/*
    スタックに要素を積む
*/
void stack_push(Stack stack, int value)
{
    struct StackList_tag* p = xmalloc( sizeof(struct StackList_tag) );
    p->value = value;

    // 新たな要素を先頭に置く
    p->next = stack->head;
    stack->head = p;
}

/*
    スタックから要素を降ろす
*/
int stack_pop(Stack stack)
{
    assert( !stack_is_empty(stack) );

    struct StackList_tag* tmp = stack->head;
    int pop_value = stack->head->value;
    stack->head = stack->head->next;
    free( tmp );

    return pop_value;
}

/*
    スタックが空かどうか調べる
*/
bool stack_is_empty(Stack stack)
{
    return stack->head == NULL;
}


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

配列版を実装したときに使った stack.c だけを修正しています。stack.h および main.c に変更はありません。必要な機能の要件は stack.h に集められており、この形さえ壊さなければ、具体的な実装が書かれている stack.c を変更しても、使う側に影響を与えません。コンパイルが通りますし、正しく実行できます。

ただし、使い方は変わらないですが、内部の実装は変わっているのですから、性能面の特性は変わります。

実装をよく観察すると、たとえば、stack_create関数の引数size が実は使われていないことが分かります。仮引数を void に変えてしまうのではなく、あえて残しておくことで、配列版との共通性を維持しています。

この考え方はやり過ぎると逆効果になりますが、この程度であれば許される範囲でしょう。

連結リスト版のスタックでは、struct Stack_tag の定義は次のようになりました。

struct Stack_tag {
    struct StackList_tag*  head;    // 先頭の要素へのポインタ
};

StackList_tag はこうなっています。

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

連結リストといっても、いくつかタイプがありますが（第３章）、ここでは単方向線形リストを使っています。

単方向線形リストでは、末尾を探す処理が遅いので、スタックの push、pop の操作を行う対象になる最上段が、連結リストの先頭に来るようにしています。連結リストの先頭はいつも headメンバが指しているので、スタックポインタを別途作らなくても、head がその役目を担ってくれます。

スタックを連結リストで実装する利点としては、メモリが許す限りはいくらでも要素を追加していける点が挙げられます。満杯になるということがありません。

一方、スタックを連結リストで実装する欠点としては、nextポインタを必要とするためにメモリの利用効率が劣ることや、push や pop で行う処理が多いので、push、pop の頻度が高いと、処理速度的に不利であることが挙げられます。

まとめ 🔗

スタックの実装を通じて、抽象データ型という考え方を取り上げました。この考え方を使えば、スタックの内部実装が、配列を使用したものでも、連結リストを使用したものであっても、利用者は同じコードのまま取り扱えます。

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

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

それぞれに短所はありますが、これらへの解決策がないわけでもありません。

配列版の短所は、スタックが一杯になってきたときに領域を拡張させるような実装をすれば、ある程度解決できます（ただし、拡張の起こる瞬間に処理速度が大きく低下する欠点が生まれます）。

連結リスト版の短所のうち、push や pop のたびに起こる動的なメモリ確保・解放については、あらかじめ、別の場所に要素を複数個確保しておいて、push のときにその中から１つを取り出して連結リストへつなげることで効率化できます。pop されたら、メモリを解放するのではなく、連結リストから取り外して、元の場所に返却します。これは、フリーリストなどと呼ばれる手法で、さまざまな場面で応用が利く考え方です。

練習問題 🔗

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

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

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

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

解答ページはこちら。

参考リンク 🔗

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

更新履歴 🔗

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

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

≪さらに古い更新履歴を展開する≫

前の章へ　（第４章　連結リスト②（双方向・循環））

次の章へ　（第６章　キュー）

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

Programming Place Plus のトップページへ

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