スタック構造

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

サンプル・プログラム

再帰呼び出しと階乗計算

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

0009: import sys
0010:
0011: """
0012:  * 階乗計算
0013:  * @param int n
0014:  * @return int 計算結果
0015: """
0016: def fact(n):
0017:     if (n == 1):
0018:         m = 1
0019:     else:
0020:         m = n * fact(n - 1)
0021:     return (m)
0022:
0023: # メイン・プログラム ======================================================
0024: n = 5
0025: sys.stdout.write("\n{0:4d} ! = ".format(n))
0026: m = fact(n)
0027: sys.stdout.write("{0:4d}\n\n".format(m))

プログラム "dt03-34-01.py" は、Pythonで再帰呼び出しによって階乗計算を行うプログラムである。

プログラムの実行結果は左図の通りである。

Pythonによるスタック構造

処理系の内部では、再帰呼び出しを行う際、左図のように引数をスタック構造に積み上げていく（push）。
そして、引数が1になったら取り出し（pop）をはじめ、スタックが空になるまで掛け算を行う。

スタック構造は、push はリスト構造と同じで tail に追加してゆくが、ppop は逆に tail から取り出してゆくと考えれば良い。
したがって、Pythonの場合は、リスト構造と同じ deque オブジェクトを使って実装できる。popleft メソッドの代わりに popt メソッドを使えば良い。

0009: import sys
0010: from collections import deque
0011:
0012: # メイン・プログラム ======================================================
0013: stack = deque([]) #スタック
0014: n = 5
0015:
0016: sys.stdout.write("\n{0:4d} ! = ".format(n))
0017:
0018: # スタックに積んでゆく
0019: while (n > 0):
0020:     if (n == 1):
0021:         m = n
0022:     else:
0023:         stack.append(n)
0024:     n -= 1
0025:
0026: # スタックから取り出して掛け算
0027: while stack:
0028:     n = stack.pop()
0029:     m *= n
0030:
0031: 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" とした

0008: #include <iostream>
0009: #include <iomanip>
0010: #include <deque>
0011:
0012: using namespace std;
0013:
0014: // メイン・プログラム ======================================================
0015: int main() {
0016:     deque<int> stack;        //スタック
0017:     int n = 5;
0018:     int m = 0;
0019:
0020:     cout << setw(4) << n << " ! = ";
0021:
0022:     //スタックに積んでゆく
0023:     while (n > 0) {
0024:         if (n == 1)     m = n;
0025:         else            stack.push_back(n);   //末尾に追加
0026:         n--;
0027:     }
0028:
0029:     //スタックから取り出して掛け算
0030:     while (! stack.empty()) {
0031:         n = stack.back();                     //末尾を参照
0032:         stack.pop_back();                     //末尾を削除
0033:         m *= n;
0034:     }
0035:
0036:     cout << setw(4) << m << endl;
0037:
0038:     return (0);
0039: }

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

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

PHPによるスタック構造

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

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

0011: //データ構造クラス
0012: require_once('pahooDataStructure.php');
0013:
0014: // メイン・プログラム ======================================================
0015: $stack = new pahooStack; //スタック
0016: $n = 5;
0017:
0018: printf("\n%4d ! = ", $n);
0019:
0020: //スタックに積んでゆく
0021: while ($n > 0) {
0022:     if ($n == 1)    $m = $n;
0023:     else            $stack->push($n);
0024:     $n -= 1;
0025: }
0026:
0027: //スタックから取り出して掛け算
0028: while ($stack->len() > 0) {
0029:     $n = $stack->pop();
0030:     $m *= $n;
0031: }
0032:
0033: printf("%4d\n\n", $m);