データ構造 スタック

C言語

スタックとは

C言語では、データ型として、文字型、整数型、実数型、配列、構造体、共用体、ポインタが用意されています。

これらの標準型とは別に、プログラムを作ってデータのやり取りをする構造として、スタックがあります。

スタックは、配列とポインタを使ってデータの保存、取り出しを行います。

配列、ポインタについては、こちらにまとめています。

C言語 配列
C言語の配列についての書き方、使い方をまとめます。
C言語 ポインタ
C言語のポインタについてまとめます。

スタック構造

スタックの構造は、スタックと呼ばれるデータ保管構造にデータを下部から順に積んでいき、必要に応じて上部からデータを取り出していくというものです。

この構造では、最後に保管したデータから最初に取り出していくということからLIFO(Last In First Out)と呼ばれます。

スタック動作

スタックの動作は、プッシュ動作とポップ動作の2つの動作からなります。

プッシュ動作は、データをスタックに積む動作で、ポップ動作は、スタックからデータを取り出す動作になります。

スタックは、この2つの動作とスタック上のデータがどこまで入っているかを管理するスタックポインタというデータの取り出し位置を管理する変数を持ちます。

スタックは、データがない状態からの開始となるので、スタックポインタの初期値は、ゼロとなります。

サンプルプログラム

スタック構造のサンプルプログラムです。

スタックは、最大100個の整数型データを保存できるようになっています。

コンソール上に「 ] 」と表示されている状態で、「i」または、「I」を入力すると、「data –> 」という文字列が表示されるので、そこに整数値を入力して、「Enter」キーを押します。

これで、スタック上に入力したデータがプッシュされます。

スタック上のデータを取り出す場合は、コンソール上に「 ] 」と表示されている状態で、「o」または、「O」を入力すると、「stack data –> 」に続けて最後にプッシュした整数値が取り出され、表示されます。

プッシュするデータがない場合は、「stack empty」と表示されます。

プログラムを終了するときは、「ctrl + Z」を押し、「Enter」キーで終了します。

c:\prog\algorithm>stack
]i
data --> 1
]i
data --> 2
]i
data --> 3
]o
stack data -->3
]o
stack data -->2
]o
stack data -->1
]o
stack empty
]o
stack empty
]^Z
test end

スタックに1,2,3という値をプッシュして、順番にポップしたときの出力結果です。データの取り出しは、最後にプッシュした値である3から取り出されます。

スタック上にデータがなくなると、stack emptyの表示となっています。

コメント

タイトルとURLをコピーしました