スタック構造

再帰呼び出しや総当たり検索で使われる
スタック構造
スタック構造は、キュー構造とは逆に、最後に追加した要素を最初に処理するときに使う。再帰呼び出しの時、システム内部ではスタック構造が利用されている。また、総当たり探索を行う場合も、探索分岐点をスタックに積み上げてゆく。

サンプル・プログラム

再帰呼び出しと階乗計算

階乗計算は再帰呼び出しによって実装することができる。
import sys

""" * 階乗計算 * @param int n * @return int 計算結果 """ def fact(n): if (n == 1): m = 1 else: m = n * fact(n - 1) return (m)
# メイン・プログラム ====================================================== n = 5 sys.stdout.write("\n{0:4d} ! = ".format(n)) m = fact(n) sys.stdout.write("{0:4d}\n\n".format(m))
プログラム "dt03-34-01.py" は、Pythonで再帰呼び出しによって階乗計算を行うプログラムである。
再帰呼び出しによる階乗計算
プログラムの実行結果は左図の通りである。

Pythonによるスタック構造

push - スタック構造
処理系の内部では、再帰呼び出しを行う際、左図のように引数をスタック構造に積み上げていく(push)。
そして、引数が1になったら取り出し(pop)をはじめ、スタックが空になるまで掛け算を行う。
pop - スタック構造
スタック構造は、push はリスト構造と同じで tail に追加してゆくが、ppop は逆に tail から取り出してゆくと考えれば良い。
したがって、Pythonの場合は、リスト構造と同じ deque オブジェクトを使って実装できる。popleft メソッドの代わりに popt メソッドを使えば良い。
import sys
from collections import deque

# メイン・プログラム ====================================================== stack = deque([]) #スタック n = 5
sys.stdout.write("\n{0:4d} ! = ".format(n))
# スタックに積んでゆく while (n > 0): if (n == 1): m = n else: stack.append(n) n -= 1
# スタックから取り出して掛け算 while stack: n = stack.pop() m *= n
sys.stdout.write("{0:4d}\n\n".format(m))
プログラム "dt03-34-02.py" は、再帰呼び出しプログラム "dt03-34-01.py" をスタック構造を使って書き直したものである。

C++によるスタック構造

C++はPythonと同じクラス deque を備えているので、Pythonプログラム "dt03-34-02.py" をほぼそのまま移植し、"dt03-34-04.cpp" とした

   8: #include <iostream>
   9: #include <iomanip>
  10: #include <deque>
  11: 
  12: using namespace std;
  13: 
  14: // メイン・プログラム ======================================================
  15: int main() {
  16:     deque<int> stack;       //スタック
  17:     int n = 5;
  18:     int m = 0;
  19: 
  20:     cout << setw(4<< n << " ! = ";
  21: 
  22:     //スタックに積んでゆく
  23:     while (n > 0) {
  24:         if (n == 1)     m = n;
  25:         else            stack.push_back(n); //末尾に追加
  26:         n--;
  27:     }
  28: 
  29:     //スタックから取り出して掛け算
  30:     while (! stack.empty()) {
  31:         n = stack.back();                       //末尾を参照
  32:         stack.pop_back();                       //末尾を削除
  33:         m *n;
  34:     }
  35: 
  36:     cout << setw(4<< m << endl;
  37: 
  38:     return (0);
  39: }

まず、クラス deque をスタックとして用意し、メソッド push_back によって末尾に積んでゆく。

スタックからの取り出しは、メソッド back によって末尾を参照し、続いてメソッド pop_back によって末尾を削除する。

PHPによるスタック構造

PHPにはスタック構造が用意されていないので、リスト構造向けのクラス "pahooList" を利用してスタック構造を実装する。

1110:  * @return  なし
1111: */
1112: function __construct() {
1113:     $this->error  = FALSE;
1114:     $this->errmsg = '';
1115:     $this->plist = new pahooList();
1116: }
1117: 
1118: /**
1119:  * デストラクタ
1120:  * @param   なし
1121:  * @return  なし
1122: */
1123: function __destruct() {
1124:     $this->plist = NULL;
1125: }
1126: 
1127: /**
1128:  * キューに要素を1つ追加する
1129:  * @param   mixed $data 追加する要素
1130:  * @return  なし
1131: */
1132: function push($data) {
1133:     $this->plist->append($data);
1134:     $this->error = $this->plist->error;
1135:     $this->errmsg = $this->plist->errmsg;
1136:     return (! $this->error);
1137: }
1138: 
1139: /**
1140:  * キューから要素を1つ取り出す
1141:  * @param   なし
1142:  * @return  mixed 取り出した要素/NULL 要素がない
1143: */
1144: function pop() {
1145:     if ($this->len() == 0) {
1146:         $this->error  = TRUE;
1147:         $this->errmsg = 'que: No data';
1148:         return NULL;
1149:     } else {
1150:         $this->plist->moveRoot();
1151:         $data = $this->plist->get();
1152:         $this->plist->delete();
1153:         return $this->error ? NULL : $data;
1154:     }
1155: }
1156: 
1157: /**
1158:  * キューに残っている要素数を数える
1159:  * @param   なし
1160:  * @return  int キューの要素数
1161: */
1162: function len() {
1163:     return $this->plist->len();
1164: }
1165: 
1166: /**
1167:  * リストの内容を成形して返す
1168:  * @param   なし
1169:  * @return  string リストの内容
1170: */
1171: function list2() {
1172:     return $this->plist->list2();
1173: }
1174: 
1175: // End of Class
1176: }
1177: 
1178: // pahooStack クラス =========================================================
1179: class pahooStack {
1180:     var $plist;             //スタックの実体としての配列
1181:     var $error, $errmsg;        //エラーフラグ,エラーメッセージ
1182: 
1183: /**

スタックに要素を追加するのは、リストの tail に追加すればいいから、[pahooList::append] メソッドを利用する。
スタックから要素を取り出すには、リストの tail から取り出し、これを削除すればいいから、pahooList::moveTail メソッドを使って tailへ移動し、pahooList::get メソッドと、pahooList::delete メソッドを利用する。

スタック構造を実現する pahooStack クラスには、以下のメソッドを用意した。
メソッド機能
push()スタックに要素を1つ追加する。
pop()スタックから要素を1つ取り出す。
len()スタックに残っている要素数を数える。
list()スタックの内容を成形して返す。

 

クラス pahooStack を使ってPythonプログラム "dt03-31-02.py" をPHPに移植したものが "dt03-31-03.php" である。

  11: //データ構造クラス
  12: require_once('pahooDataStructure.php');
  13: 
  14: // メイン・プログラム ======================================================
  15: $stack = new pahooStack;    //スタック
  16: $n = 5;
  17: 
  18: printf("\n%4d ! = ", $n);
  19: 
  20: //スタックに積んでゆく
  21: while ($n > 0) {
  22:     if ($n == 1)    $m = $n;
  23:     else            $stack->push($n);
  24:     $n -1;
  25: }
  26: 
  27: //スタックから取り出して掛け算
  28: while ($stack->len() > 0) {
  29:     $n = $stack->pop();
  30:     $m *$n;
  31: }
  32: 
  33: printf("%4d\n\n", $m);

(この項おわり)
header