Nodachisoft Nodachisoft logo, Katana Sword Icon

@あまじ✎ 2021年3月5日に更新

第２章４６データ構造・スタックの実装

#C11仕様 #C言語 #ゲームプログラミング

イチからゲーム作りで覚えるC言語

連載ページ一覧へ

第２章４５構造体を使う : PREV

NEXT : 第２章４７リスト構造 :

概要

データを扱うときの便利な構造の一つに、スタック（stack）があります。

スタックは、例えば簡易的なウィンドウ管理システムやインタプリタとよばれる種類の自作スクリプトの作成の基本動作として使われていることが多く、スタックの考え方を把握し、自分で実装できるようにしておくことで、 C言語に限らず様々なプログラミング言語で応用できるアルゴリズムです。

スタックとは

スタック（stack）とは「積み重なった」とか、「折り重なって身動きがとれない」といった意味で使われることが多いです。

３Dゲームでキャラクタや３Dオブジェクトがつっかえて動かなくなったときには後者の意味で使いますが、今回は前者の、「積み重なった」の意味のほうが、ニュアンスが近いかと思います。

スタックはデータを積み重ねて管理する仕組みであり、一番上に積んであるデータを取る pop 機能と、一番上にデータを追加で積む push 機能があります。

スタックのpushとpop

実装例

簡単なスタックの例をみてみます。

stack_ex1.c:

#include <stdio.h>
char stack[64]; // スタックデータが保存される
int pilecount = 0;  // スタックされているデータ数
void push(char pile){
    stack[pilecount] = pile;
    pilecount++;
}
char pop(){
    pilecount--;
    return stack[pilecount];
}

int main(){
    push('3');
    push('A');
    push('6');
    printf("%d 枚カードが裏返しで積んであります。\n", pilecount);
    printf("1枚、上のカードを手に取ると「%c」でした。\n", pop());
    printf("1枚、上のカードを手に取ると「%c」でした。\n", pop());
    printf("1枚、上のカードを手に取ると「%c」でした。\n", pop());
}

実行すると下の結果となります。

実行結果

3 枚カードが裏返しで積んであります。
1枚、上のカードを手に取ると「6」でした。
1枚、上のカードを手に取ると「A」でした。
1枚、上のカードを手に取ると「3」でした。

トランプのカードを最初に3枚つみ、一番上のカードから取って中身を確認することをイメージしています。

スタック機能を実現しているのは、2～11行目です。

stack_ex1.c:

char stack[64]; // スタックデータが保存される
int pilecount = 0;  // スタックされているデータ数
void push(char pile){
    stack[pilecount] = pile;
    pilecount++;
}
char pop(){
    pilecount--;
    return stack[pilecount];
}

2行目で char型配列の stack を定義しています。スタックのデータはこの中で管理されます。今回、配列の数は 64 個ですから、最大でも 64 個までのデータを push 関数で "のせる" ことができます。

3行目の pilecount は、現在スタックに乗っているデータの数を記録しています。最初はスタックには何もデータが入っていないので、データの数は 0 として初期化をしています。

配列での stack 管理

スタックは様々な実装方法がありますが、今回は配列でスタックのデータを管理しています。 push 関数でデータを ”のせる" と、下の図のように新しく配列にデータが記録されていきます。

pop 関数でデータを "とる" と、下の図のように配列から一つデータを抜き出します。

push 関数

push 関数はスタックの一番上に、一つデータをのせる（追加する）ための関数です。

今回作ったスタックは char 型を扱うスタックですので、push 関数の引数には、追加したい char 型を渡すように関数を宣言しました。

配列変数 stack の配列の添え字、 [0]～[pilecount -1] まではすでにデータが入っていますから、新しく添え字 [pilecount] にデータを格納し、格納後、管理しているデータの数を pilecount++ でカウントアップしています。

今回のプログラムでは、下のようにスタックにデータを 3 件追加しています。

stack_ex1.c:

    push('3');
    push('A');
    push('6');

pop 関数

pop 関数はスタックの一番上に積まれたデータを一つ取り出すための関数です。 push 関数の逆の動きをします。

呼び出された時点で、配列変数 stack の配列の添え字、 [0]～[pilecount -1] まではすでにデータが入っていますから、まず pilecount をカウントダウンして、stack[pilecount] のデータを返せばよいです。

今回のプログラムでは下のように、スタックからデータを取り出しています。

stack_ex1.c:

    printf("1枚、上のカードを手に取ると「%c」でした。\n", pop());
    printf("1枚、上のカードを手に取ると「%c」でした。\n", pop());
    printf("1枚、上のカードを手に取ると「%c」でした。\n", pop());

Window UI への利用

もう少し具体的な例として、ウィンドウの表示システムをスタックを使って実現してみましょう。スタックの一つ一つのデータを”ウィンドウ”とします。

今回は MacOS や Linux、 Windows OS のグラフィカルなウィンドウではなく、簡単に表示できるコンソールで自作して理解を深めます。

ウインドウのデータは構造体で定義しておきます。デスクトップ上のどの位置にウィンドウを表示するか、という情報を持ちたいので、表示する開始位置の(x,y)座標、ウィンドウの幅と高さとして w（幅）、h（高さ）の情報を持たせます。

図にするとこんな感じです。

window管理システムのウィンドウの座標

一応ウィンドウっぽい情報として、ウィンドウのタイトルの情報を持たせることにしました。 (ウィンドウの中身は今回は本題からそれちゃうので、実装はしていません)

下のような構造体で実現することにします。

ウィンドウの構造体

typedef struct {
    char* title;
    int x, y, w, h;
} Window;

この構造体をスタックとして扱い、ウィンドウを複数追加した状態で表示してみます。

stack_windowui_ex1.c

typedef struct {
    char* title;
    int x, y, w, h;
} Window;
Window stack[64];
int pilecount = 0;
Window pop() {
    pilecount--;
    return stack[pilecount];
}
void push(Window pile) {
    stack[pilecount] = pile;
    pilecount++;
}
void printWindow() {
    char result;
    for (int y = 0; y < 16; y++) {
        for (int x = 0; x < 60; x++) {
            result = '.';
            for (int z = pilecount -1 ; z >= 0; z--) {
                Window w = stack[z];
                if (   (w.x <= x && x <= w.x + w.w)
                     &&(w.y <= y && y <= w.y + w.h) ){
                    if ((w.x == x)||(w.x + w.w == x)) { // Window 枠
                        result = '|';
                    } else if ((w.y == y) || (w.y + w.h == y)) { // Window枠
                        result = '-';
                    } else if ( w.y +1 == y) { // Window Title
                        int titlepos = x - w.x - 1;
                        if (titlepos < strlen(w.title)) {
                            result = w.title[titlepos]; // Title 表示
                        } else {
                            result = ' ';
                        }
                    } else if ( w.y + 2 == y) { // Title との境目 
                        result = '~';
                    } else {
                        result = ' ';  // Window の本体内部
                    }
                    break;
                }
            }
            printf("%c", result);
        }
        printf("\n");
    }
}
int main() {
    Window paint = { "Paint Tool", 3, 2, 15, 7 };
    Window notepad = { "Notepad", 10, 7, 24, 5 };
    Window alert = { "Alert", 27, 3, 10, 6 };
    push(paint);
    push(notepad);
    push(alert);
    printWindow();
}

実行すると下のような結果になります。

実行結果

............................................................
............................................................
...|--------------|.........................................
...|Paint Tool    |........|---------|......................
...|~~~~~~~~~~~~~~|........|Alert    |......................
...|              |........|~~~~~~~~~|......................
...|              |........|         |......................
...|      |----------------|         |......................
...|      |Notepad         |         |......................
...|------|~~~~~~~~~~~~~~~~|---------|......................
..........|                       |.........................
..........|                       |.........................
..........|-----------------------|.........................
............................................................
............................................................
............................................................

コンソール画面上ですが、疑似的に、目で見て分かるようなインターフェイスの GUI （グラフィカル）なウィンドウ管理のような仕組みが出来上がりました。この簡易ウィンドウ管理システムでは、よくある Windows 等の OS のウィンドウシステムと同じように、後から push したウィンドウほど表示の優先度が高くなるように表示しています。 Windows だと一番トップに表示しているウィンドウで操作する対象となるものを「アクティブウィンドウ」と読んだりしますね。

また、スタックの最初にpush した "Paint Tool" のウィンドウは "Notepad" のウィンドウの裏側に隠れて表示されています。

このウィンドウシステムで例えば、一番スタックの上に積んである「Alert」ウィンドウを削除するときは、pop() 関数を実行すれば OK です。

このあたりのウィンドウのシステムは、ゲームエンジンの上に独自のUIシステムを構築する際の基本的な考え方になるので非常に便利です！