【アルゴリズム】スタックの格納・取り出しのアルゴリズムについて
こんにちは。行未です。
先日、こちらの記事にてスタックの考え方を用いました。
今回は、スタックの格納・取り出しのアルゴリズムについて説明致します。
嘘です。説明できる能力ないです。自分用です。
そもそもスタックとは
スタックとは、データ構造の1つです。
もう少しくどく説明するならば、「扱うデータをどのようにカテゴライズ、記憶しておくか」という考え方の1つです。
スタック以外のデータ構造の例としては、キュー、リスト等が代表的なものとして挙げられます。
スタックの特徴としては、
後に格納されたデータが先に取り出される
という点です。
俗にいう後入れ先出し（LIFO）です。
尚、スタックにおいて、格納する操作をプッシュダウン、取り出す操作をポップアップといいます。
定義
アルゴリズムに入る前に諸々定義しておきます。
スタックは1次元の配列で表現できます。この1次元配列をS（Stack）とします。
更に、配列Sの大きさをmaxとします。
また、格納するデータをaとします。
データ型については数値型、文字列型等色々ありますが、これは時と場合によって変わるでしょう。
次が重要な点です。
スタックの先頭の要素の位置を記憶する変数を定義します。
要は現状何個データを格納しているかを表す変数です。
この変数をtopとします。
アルゴリズム
格納する場合（pushdown）
データを格納する場合は、topを+1し、
S[top+1]にデータaを格納すればOKです。
pushdown(S,a){
if(top<max){
top←top+1;
S[top]←a;
}
else{
//オーバーフロー時の処理
}
}取り出す場合（popup）
逆に、データを取り出す場合は、
topを-1し、S[top+1]を値として返せばOKです。
こちらの注意点としては、
先にtopを-1（下にずらす）し、その次（上）を返却するという順序
という点です。
S[top]を返却し、その後topの値を-1しても、考え方としては間違いではありませんが、
アルゴリズムの構造上、値が返却された(returnされた)時点で処理は終了となります。
回避する方法もないわけではありませんが、前述の方法がスマートでしょう。
popup(S){
if(top>0){
top←top-1;
return(S[top+1]);
}
else{
//Sが空になった時の処理
}
}終わりに
ソースコード見にくくて申し訳ありません…
ブロックエディタにまだ慣れていなくて…。おいおい修正したいと思います…。