スタックとは
C言語では、データ型として、文字型、整数型、実数型、配列、構造体、共用体、ポインタが用意されています。
これらの標準型とは別に、プログラムを作ってデータのやり取りをする構造として、スタックがあります。
スタックは、配列とポインタを使ってデータの保存、取り出しを行います。
配列、ポインタについては、こちらにまとめています。
スタック構造
スタックの構造は、スタックと呼ばれるデータ保管構造にデータを下部から順に積んでいき、必要に応じて上部からデータを取り出していくというものです。
この構造では、最後に保管したデータから最初に取り出していくということからLIFO(Last In First Out)と呼ばれます。
スタック動作
スタックの動作は、プッシュ動作とポップ動作の２つの動作からなります。
プッシュ動作は、データをスタックに積む動作で、ポップ動作は、スタックからデータを取り出す動作になります。
スタックは、この２つの動作とスタック上のデータがどこまで入っているかを管理するスタックポインタというデータの取り出し位置を管理する変数を持ちます。
スタックは、データがない状態からの開始となるので、スタックポインタの初期値は、ゼロとなります。
サンプルプログラム
スタック構造のサンプルプログラムです。
スタックは、最大１００個の整数型データを保存できるようになっています。
コンソール上に「 ] 」と表示されている状態で、「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スタックに１，２，３という値をプッシュして、順番にポップしたときの出力結果です。データの取り出しは、最後にプッシュした値である３から取り出されます。
スタック上にデータがなくなると、stack emptyの表示となっています。
コメント