スタックの実装・構造体で表現

スポンサーリンク
スポンサーリンク
ライフスタイル関連のコンテンツ
お金 | 仕事 | 勉強 | プライベート | 健康 |
プログラミング関連のコンテンツ
C言語/C++入門 | Ruby入門 | Python入門 | プログラミング全般

スタックを実装するクラスを作る前に、スタックを構造体で考えてみる。
スタック構造体は、以下のように表せます。

スポンサーリンク

const int STACK_SIZE = 100;    // スタックの最大サイズ
 
// スタック本体
struct stack {
    int count;                // スタック内の要素の数
    int data[STACK_SIZE];    // 要素
};

countは、スタックのサイズ(要素の数)を宣言。
data[STACK_SIZE]で、要素を入れる場所を宣言。

LIFO(Last-in First-out:後入れ先出し)、最後に追加して(push)、最初に取り出す(pop)、というルーチン(関数)を作ります。

/***********************************
Stack
 整数型のスタックを実装するルーチン
 
プロシジャ
 stack_init    :スタック初期化
 stack_push    :スタックに要素プッシュ
 stack_pop    :スタックから要素ポップ
***********************************/
 
#include <assert.h>
#include <cstdlib>
#include <iostream>
 
const int STACK_SIZE = 100;    // スタックの最大サイズ
 
// スタック本体
struct stack {
    int count;                // スタック内の要素の数
    int data[STACK_SIZE];    // 要素
};
 
/***********************************
stack_init
 スタックの初期化ルーチン
************************************/
 
inline void stack_init(struct stack& the_stack) {
    the_stack.count = 0;    // スタックの要素数を初期値0に設定
}
 
/***********************************
stack_push
 プッシュ演算のルーチン。
 スタックの最後に要素を追加して、
 要素数をインクリメントする。
 
引数
 the_stack    :スタック構造体の参照渡し
 item        :追加する要素の値
 
戻り値        :なし
************************************/
 
inline void stack_push(struct stack& the_stack, const int item) {
    assert((the_stack.count >= 0) &&
        (the_stack.count <= static_cast<int>(sizeof(the_stack.data)/sizeof(the_stack.data[0]))));
    
    the_stack.data[the_stack.count] = item;
    ++the_stack.count;
}
 
/***********************************
stack_pop
 ポップ演算のルーチン。
 スタックの先頭要素を取り出して、
 要素数をデクリメントする。
 
引数
 the_stack    :スタック構造体の参照渡し
 
戻り値        :スタックの最後の値
************************************/
 
inline int stack_pop(struct stack& the_stack) {
    // スタックの要素数をデクリメント
    --the_stack.count;
 
    assert((the_stack.count >= 0) &&
        (the_stack.count < static_cast<int>(sizeof(the_stack.data)/sizeof(the_stack.data[0]))));
    
    // 最後の値を返す
    return (the_stack.data[the_stack.count]);
}
 
// スタックをテストするためのルーチン
int main() {
    // stackを使用可能にする
    struct stack a_stack;    // stack構造体の宣言
    stack_init(a_stack);    // stackの初期化
 
    // 要素をスタックにプッシュ
    stack_push(a_stack, 5);
    stack_push(a_stack, 7);
    stack_push(a_stack, 2);
    stack_push(a_stack, 1);
    stack_push(a_stack, 2);
    stack_push(a_stack, 3);
 
    // スタックから要素をポップ
    std::cout << stack_pop(a_stack) << "\n";
    std::cout << stack_pop(a_stack) << "\n";
    std::cout << stack_pop(a_stack) << "\n";
    std::cout << stack_pop(a_stack) << "\n";
    std::cout << stack_pop(a_stack) << "\n";
    std::cout << stack_pop(a_stack) << "\n";
 
    return 0;
}

実行結果。

3
2
1
2
7
5

スタックやキューは、Lightweight Languageでも、配列の操作として馴染みがあります。
PHPやRubyには、配列操作の関数として、push, popなどの関数、メソッドが用意されていますが、これはスタックにより実装されていることが分かりました。
C++言語での、上記のようにスタックの実装を確認できたので、PHPやRubyの内部的な動作を少し理解できますね。

スポンサーリンク
 
スポンサーリンク