【アルゴリズム】スタックの格納・取り出しのアルゴリズムについて

2019年4月23日

プログラミング系列サムネイル画像1

こんにちは。行未です。

先日、こちらの記事にてスタックの考え方を用いました。

今回は、スタックの格納・取り出しのアルゴリズムについて説明致します。
嘘です。説明できる能力ないです。自分用です。

そもそもスタックとは

スタックとは、データ構造の1つです。
もう少しくどく説明するならば、「扱うデータをどのようにカテゴライズ、記憶しておくか」という考え方の1つです。

スタック以外のデータ構造の例としては、キュー、リスト等が代表的なものとして挙げられます。

スタックの特徴としては、

後に格納されたデータが先に取り出される

という点です。
俗にいう後入れ先出し(LIFO)です。

尚、スタックにおいて、格納する操作をプッシュダウン、取り出す操作をポップアップといいます。

pushdownイメージ画像

popupイメージ画像

定義

アルゴリズムに入る前に諸々定義しておきます。

スタックは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が空になった時の処理
	}
}

終わりに

ソースコード見にくくて申し訳ありません…

ブロックエディタにまだ慣れていなくて…。おいおい修正したいと思います…。