Nodachisoft Nodachi Sword Icon
  
@あまじ✎ 2021年3月5日に更新

第2章46 データ構造・スタックの実装

イチからゲーム作りで覚えるC言語
第2章45 構造体を使う : PREV
NEXT : 第2章47 リスト構造 :

概要

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

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

スタックとは

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

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

スタックはデータを積み重ねて管理する仕組みであり、 一番上に積んであるデータを取る 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システムを構築する際の基本的な考え方になるので非常に便利です!

参考

特になし

イチからゲーム作りで覚えるC言語
第2章45 構造体を使う : PREV
NEXT : 第2章47 リスト構造 :
 
 
送信しました!

コメント、ありがとうございます。

なんかエラーでした

ごめんなさい。エラーでうまく送信できませんでした。ご迷惑をおかけします。しばらくおいてから再度送信を試していただくか、以下から DM などでご連絡頂ければと思います。

Twitter:@NodachiSoft_jp
お名前:
 
連絡先:
 
メッセージ:
 
戻る
内容の確認!

以下の内容でコメントを送信します。よろしければ、「送信」を押してください。修正する場合は「戻る」を押してください

お名前:
 
連絡先:
 
メッセージ:
 
Roboto からの操作ではないという確認のため確認キーを入れてください。
確認キー=95
戻る
 / 
送信確認へ
コメント欄
コメント送信確認へ

関連ありそうな記事(5件)です!

第4章3 C言語コンソール上で迷路脱出プログラム・迷路の自動生成

#C11仕様#C言語#ゲームプログラミング✎ 2021-05-15
C言語のコンソールゲームで迷路脱出ゲームプログラムの作り方を確認します。迷路は自動生成されます
広告領域
追従 広告領域
目次
第2章46 データ構造・スタックの実装
第2章46 データ構造・スタックの実装
概要
概要
スタックとは
スタックとは
実装例
実装例
配列での stack 管理
配列での stack 管理
push 関数
push 関数
pop 関数
pop 関数
Window UI への利用
Window UI への利用
参考
参考
Nodachisoft © 2021