データ構造とアルゴリズム 第5回 スタック ～ データ構造（2）～

前回の解答 ROOT 0091 0093 0094 009D 0000 0100 0091 0106 009C 0104 009D 0000 内容 番地 00FF 0101 0102 0103 0105 0093 0108 0094 010E 009A 010C 009B 0102 内容 番地 0106 0107 0109 010A 010B 010D 0095 010A 0096 0112 0098 0114 0099 0000 内容 番地 010E 010F 0110 0111 0113 0115 ROOT

前回の復習と補足 抽象データ型としての「リスト」 リストの実現方法 一定の型の要素を０個以上一列に並べたもの リスト中のどの位置でも自由に参照，挿入(Insert)，削除(Delete)の操作を行える リストの実現方法 配列を用いる方法 ： 「要素の配列」と「最後の要素の位置を示す変数」で実現 ポインタを用いる方法 ： 「要素」と「次のセルを指すポインタ」でセルを構成し，セルを順次つなぐことで，連結リストを作成し，実現

スタック(Stack)

本日の内容：スタック スタック 抽象データ型としてのスタック 配列によるスタックの実現 単方向リストによるスタックの実現 スタックの利用例 ポーランド記法，逆ポーランド記法 再帰呼び出し(リカーシブ・コール，recursive call）

スタック 宿題をする 本を調べる 電話に出る 本 心の中の スタック 宿題 宿題 宿題 時間の経過

スタック(Stack) a4 a3 a2 a1 スタック：要素の挿入や削除がいつも一方の端（先頭）からしかできないリスト 後から入れた要素ほど，先に出る 別名 後入れ先出しリスト LIFO 　(last-in first-out) push down list スタックの先頭→ （top） a4 a3 a2 a1 スタックの底→ （bottom）

抽象データ型としてのスタック スタック 操作 要素を 並べたもの 抽象データ型： データ構造＋操作 先頭への要素の挿入 Push 抽象データ型：　データ構造＋操作 スタック 操作 先頭への要素の挿入 Push 要素を 並べたもの 先頭からの要素の取出し Pop

スタックの操作 CREATE(S )：空スタックSを準備しその先頭の位置を返す PUSH(x, S )：要素ｘをSの先頭に入れる スタックの操作　 CREATE(S )：空スタックSを準備しその先頭の位置を返す PUSH(x, S )：要素ｘをSの先頭に入れる POP(S )：先頭の要素を削除する ＜同時にSの先頭の要素を返す場合もある＞

単方向リストによるスタックの実現 init an-1 an-2 a0 Push, Popを行うために使用するスタックの先頭へのポインタ スタックの底の要素が格納されているセルのnextはNULL

スタックの型定義(単方向リスト版)とPUSHのプログラム例（p33） /* セルを表わす構造体の定義 */ struct cell { int element; struct cell *next; }; … main() struct cell *push(int x, struct cell *init) struct cell *q, *r; r = (struct cell *)malloc(sizeof(struct cell)); q = init; init =r; r->element = x; r->next = q; return(init); } セルのデータ構造はリストのときと同じ。 ここではint型の要素としたが、どのような型でも良い。 struct cell型への ポインタを返す関数

① r = (struct cell *)malloc(sizeof(struct cell)); Pushの実現(単方向リスト版)　 Pushが始まる直前 initはあるリストの先頭要素を指す． Push(x, S) [struct cell *push(int x, struct cell *init)] ① 新しいセル用のメモリを確保し、rはそのセルを指すポインタとする init an-1 an-2 a0 r ① r = (struct cell *)malloc(sizeof(struct cell));

Pushの実現(単方向リスト版) Push(x, S) init q r an-1 an-2 a0 ② qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく） ③ initにrを代入する（＝initを新しい要素用セルへのポインタとする） init q ② q = init; an-1 an-2 a0 ③ init = r; r

Pushの実現(単方向リスト版) x Push(x, S) init q r an-1 an-2 a0 ② qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく） ③ initにrを代入する（＝initを新しい要素用セルへのポインタとする） ④ 新しいセルに要素ｘを代入 ⑤ r->nextが，前の先頭要素のセルを指すようにする init q an-1 an-2 a0 ④ r->element = x; x ⑤ r->next = q; r

Pushの実現(単方向リスト版) x Push(x, S) q r init an-1 an-2 a0 ② qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく） ③ initにrを代入する（＝initを新しい要素用セルへのポインタとする） ④ 新しいセルに要素ｘを代入 ⑤ r->nextが，前の先頭要素のセルを指すようにする ⑥ 新しい要素を指すinitを返す 呼び出し元（mainなど）へ ⑥ return(init); 新要素を指すinitだよ〜 q init x an-1 an-2 a0 r

POPのプログラム例 （p33） … main() struct cell *pop(struct cell *init) { 空の場合はエラーメッセージ … main() struct cell *pop(struct cell *init) { struct cell *q; if(init !=NULL) q = init; init = init->next;free(q); return(init); } else printf(“Error: Stack is empty.\n”); exit(1); return; exit文はプログラムを終了させる標準関数で，この関数が０を返せば正常終了，それ以外を返せば異常終了と判断される．exit文を使用する場合には，#include <stdlib.h>が必要である．

Popの実現(単方向リスト版) Popが始まる直前 initはあるリストの先頭要素を指す． Pop(S) init q initがNULLではない場合以下を実行 ① qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく） an-1 an-2 a0 init ① q = init; q an-1 an-2 a0

Popの実現(単方向リスト版) Pop(S) q init initがNULLではない場合以下を実行 an-1 an-2 a0 ① qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく） ② initを前の先頭要素の次（＝前の２番目）へのポインタとする ③ 削除するセルの領域を解放 ④ 書き換えられたinitを呼び出し元（main関数など）へ返す 呼び出し元（mainなど）へ init変えました〜 q ③ free(q); init an-1 an-2 a0 ② init = init->next; ④ return(init);

Popの実現(単方向リスト版) Pop(S) init initがNULLではない場合以下を実行 initがNULLの場合 ① qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく） ② initを前の先頭要素の次（＝前の２番目）へのポインタとする ③ 削除するセルの領域を解放 ④ 書き換えられたinitを返す initがNULLの場合 ⑤ エラーメッセージを表示して関数を終了 init ⑤ printf(“Error: stack is empty.¥n”);exit(1);

スタックの型の定義(配列版) #define N 100 /* 配列の最大サイズ */ struct stack /* 構造体stackの定義 */ { int top; int element[N]; }; … main() データ構造はリスト(配列版)のときと基本的には同じ．タグ名，メンバー名を変更しただけ．

配列によるpushのプログラム例（p34） void push(int x,struct stack *S) { if(S->top >=N || S->top < 0) S->top = N; if(S->top == 0) printf(“Error: Stack is full.\n”);exit(1); } else S->top = S->top-1; S->element[S->top]=x; return;

配列によるスタックの実現 element [0] [1] an-1(先頭) an-2 a1 [N-1] a0(底) スタックが伸びる方向 topはスタックの先頭位置を示すint型変数 ポインタ型変数ではない (矢印の根元に注意！教科書は一貫性がない。 図2.5はいいが、図2.9はポインタと同じ?!） [1] スタックが伸びる方向 top an-1(先頭) ［N-1］に，スタックの底を固定する点がポイント． 要素を挿入/削除するたびにリスト全体を上げ下げしなくて済む． an-2 a1 [N-1] a0(底)

Pushの実現 (配列版) 初期状態 S Ａ Ｂ Ｃ 5 top Ａ1 push関数を呼ぶ Ａ0 N=7の場合 初期状態 Stack型:スタックの要素が入る配列element 　　　　 スタックの先頭位置を示すtop から成る構造体で、elementには既に要素あり Sはstack型を指すポインタ　 (つまりtopの先頭アドレスを指す） element [0] [1] [2] [3] S [4] Ａ Ｂ Ｃ 準備ができたら 5 top [5] Ａ1 push関数を呼ぶ [6] Ａ0 void push(int x,struct stack *S)

Pushの実現 (配列版) S top -1 ? S S top 7 top 8 ? ①if(S->top >=N || S->top < 0) S->top = N; element element [0] [0] topが7以上又はtopが負ならスタックは空 その場合はtop=7とする [1] [1] S [2] [2] top -1 ? [3] [3] [4] [4] S S [5] [5] top 7 top 8 ? [6] [6]

Pushの実現 (配列版) Ａ6 Ａ4 Ａ2 topが0ならば、スタックは満杯。 エラーメッセージを表示して関数を終了 [0] top N=7の場合 topが0ならば、スタックは満杯。 エラーメッセージを表示して関数を終了 element top [0] Ａ6 [1] Ａ5 [2] Ａ4 ② [3] Ａ3 if(S->top == 0) { printf(“Error: Stack is full.\n”); exit(1); } [4] Ａ2 [5] Ａ1 [6] Ａ0

Pushの実現 (配列版) それ以外の場合： topを1減らす [0] topが指しているelementの位置に要素xを挿入 [1] [2] [3] ③ else { S->top = S->top-1; 　　　　　S->element[s->top]=x; } 4 top [4] x [5] 5 top Ａ1 [6] Ａ0

配列によるpopのプログラム例（p34） void pop(struct stack *S) { if(S->top < N) S->top = S->top + 1; } else printf(“Error: Stack is empty.\n”); exit(1); return;

Popの実現 (配列版) topが7未満なら要素はある その場合は topを1増やす [0] [1] [2] [3] [4] Ａ Ｂ Ｃ N=7の場合 element topが7未満なら要素はある その場合は topを1増やす [0] [1] [2] ① if(S->top < N) { S->top = S->top + 1; } [3] [4] Ａ Ｂ Ｃ [5] A1 5 ① top [6] Ａ0 6

Popの実現 (配列版) それ以外（N以上）なら エラーメッセージを表示して関数を終了 [0] [1] [2] [3] [4] Ａ Ｂ Ｃ element それ以外（N以上）なら エラーメッセージを表示して関数を終了 [0] [1] [2] else { printf(“Error: Stack is empty.\n”); exit(1); } [3] [4] Ａ Ｂ Ｃ [5] ？ 7 [6]

配列によるスタックの実現（参考） スタックが伸びる方向 element [0] a0 (底) [1] a1 an-2 top スタックの底を，配列のインデクス[0]に固定してもよい． この場合，上下を逆にする点に注意． an-2 top an-1(先頭) [N-1]

練習問題 S1 S2 次の手順で操作を行うと スタックS1,S2の中身は 最終的にどのようになるか？ Push Pop Push Pop 練習問題　　　　　　　　　　 Push Pop Push Pop 次の手順で操作を行うと スタックS1,S2の中身は 最終的にどのようになるか？ Push(A,S1) Push(B,S2) Push(C,S1) D=Pop(S1)で削除した要素 Push(D, S2) Pop(S1) S1 S2

練習問題 C A B S1 S2 Push(A,S1) Push(B,S2) Push(C,S1) D=Pop(S1)で削除した要素 練習問題　　　　　　　　　 Push Pop Push Pop Push(A,S1) Push(B,S2) Push(C,S1) D=Pop(S1)で削除した要素 Push(D, S2) Pop(S1) C A B S1 S2

練習問題 A B D(=C) S1 S2 Push(A,S1) Push(B,S2) Push(C,S1) D=Pop(S1)で削除した要素 練習問題　　　　　　　　　 D(=C) Push Pop Push Pop Push(A,S1) Push(B,S2) Push(C,S1) D=Pop(S1)で削除した要素 Push(D, S2) Pop(S1) A B S1 S2

練習問題 A B D(=C) S1 S2 Push(A,S1) Push(B,S2) Push(C,S1) D=Pop(S1)で削除した要素 練習問題　　　　　　　　　 Push Pop Push Pop Push(A,S1) Push(B,S2) Push(C,S1) D=Pop(S1)で削除した要素 Push(D, S2) Pop(S1) D(=C) A B S1 S2

練習問題 A B D(=C) S1 S2 Push(A,S1) Push(B,S2) Push(C,S1) D=Pop(S1)で削除した要素 練習問題　　　　　　　　　 A Push Pop Push Pop Push(A,S1) Push(B,S2) Push(C,S1) D=Pop(S1)で削除した要素 Push(D, S2) Pop(S1) D(=C) B S1 S2

スタックの利用例1：算術式の評価 予備知識： 数式の表記法 ポーランド記法，逆ポーランド記法では括弧 大切 予備知識：　数式の表記法 前置表現（prefix notation） ポーランド記法(polish notation) 中置表現（infix notation） 　 通常の数式表記法 後置表現（postfix notation） 逆ポーランド記法(reverse polish notation) ポーランド記法，逆ポーランド記法では括弧 [“（”と“）”]を使わずに数式を表現できる

歴史 ポーランド記法は，ポーランドの論理学者Jan Łukasiewicz(1878-1956) が1920年に提案 1957年には，オーストラリアの計算機科学者Charles L. Hamblin (1922-1985) がNew South Wales University of Technologyで，スタックを実装 出典http://www.calculator.org/Lukasiewicz.html 出典http://www.csc.liv.ac.uk/~peter/hamblin.html

A+Bの表記法 前置表現 （ポーランド記法） 中置表現 後置表現 （逆ポーランド記法） 演算子を変数の前に置く 例：+AB 足すことのAB 前置表現　（ポーランド記法） 演算子を変数の前に置く　　　例：+AB　足すことのAB 演算子の優先順位は存在しない．括弧が不要． 中置表現　 演算子を変数の間に置く　　　例：A+B　A足すB 演算子の優先順位が存在する．括弧が必要． 後置表現　（逆ポーランド記法） 演算子を変数の後に置く　　　例：AB+　AとBを足す

後置表現への変換 ( A – B ) * ( C + D ) ( A – B ) ( C + D ) ＊ A B - ( C + D ) ＊ (式1)　演算子　(式2) (式1) 演算子 (式2) ( A – B ) ( C + D ) ＊ (式1) (式2) 演算子 個々の式を 後置表現に する (式1) 演算子 (式2) A B - ( C + D ) ＊ a*c+a*d-b*c-b*d ac* + ad* -bc* -bd* ac*ad*bc*bd*+-- A B – C D + ＊ 後置表現

その他の数式の例 ++ABC A+B+C AB+C+ *-AB+CD (A-B)*(C+D) AB-CD+* -*47+53 前置表現 ポーランド記法 中置表現 通常の表記法 後置表現 逆ポーランド記法 ++ABC A+B+C AB+C+ *-AB+CD (A-B)*(C+D) AB-CD+* -*47+53 4*7-(5+3) 47*53+- -A÷BC A-B÷C ABC÷-

練習問題 逆ポーランド記法では，例えば，式(A-B)*CをAB-C*と表現する．次の式を逆ポーランド記法で表現したものはどれか 練習問題　 逆ポーランド記法では，例えば，式(A-B)*CをAB-C*と表現する．次の式を逆ポーランド記法で表現したものはどれか 　　　　　（A+B）*(C-D÷E) ア　AB+CDE÷-* イ　AB+C-DE÷* ウ　AB+EDC÷-* エ　BA+CD-E÷*

（A+B）*(C-D÷E) （A+B） (C-D÷E) * AB+ (C-D÷E) * AB+ (C-DE÷) * 練習問題　　　 （A+B）*(C-D÷E) （A+B） (C-D÷E) * AB+ (C-D÷E) * AB+ (C-DE÷) * AB+ CDE÷- *　　　　答ア　

スタックの利用例1：算術式の評価 スタックを使うと，逆ポーランド記法で書かれた式を左から順に読んで演算処理できる． 処理手順 一要素ずつ読み込み，要素が“数”ならスタックにPush “演算子”ならスタックから２つの要素をPopして演算し，演算結果をスタックにPush 最終的にスタックに式の演算結果が残る

算術式の評価例1 例：６＋４＊７ 　　後置表現⇒６ ４ ７ * ＋ ６ ４ ７ ２８ ３４ 4*7 6+28

算術式の評価例2 例２：６＋｛４＊（７＋４）－３｝ 　　　　　⇒６４７４＋＊３－＋ ７＋４ ４＊１１ ４４－３ ６＋４１ ４ ７ １１ ３ ４ ４ ４４ ４４ ４１ ６ ６ ６ ６ ６ ４７

利用例2：再帰呼び出し （p.35） (リカーシブ・コール，recursive call） 手続きの中から，さらに自分自身を呼び出すような処理 再帰呼び出しを利用することで，複雑な処理を非常に単純なコードで実装できる場合がある 再帰呼び出しを行なうプログラムの実行時にはスタックメモリが消費される

nの階乗（再帰を用いない場合） n! = n×(n-1)×(n-2)× … ×2×1 int fact(int n) { int result = 1; for( ; n >= 1; n--) result *= n; } return result; 結果を格納する変数を用意

nの階乗 以下のように表現することができる 3! 3×2! 2×1! 1 階乗を求める関数を 呼び出す 階乗を求める関数を 呼び出す

nの階乗の再帰的計算方法 以下のように表現することができる 6を返す 2を返す 1を返す 3! 3×2! 2×1! 1 階乗を求める関数を 呼び出す 3! 階乗を求める関数を 呼び出す 3×2! 階乗を求める関数を 呼び出す 6を返す 2×1! 2を返す 1 1を返す

関数factを呼び出すたびに引数と戻り番地が積まれていく 再帰呼び出しを用いた実装(p34) スタック メモリ int fact(int n) { if (n<=0) printf(“Illegal input n = %d¥n”, n); exit(1) } else if (N==1) return(1); else return(n*fact(n-1)); return; nの値 戻り番地 関数factの中で，関数fact自身を呼出す nの値 戻り番地 nの値 戻り番地 関数factを呼び出すたびに引数と戻り番地が積まれていく

再帰呼び出しを使用する時の注意 良くない例 int fact(int n) { return n * fact(n - 1); } スタック メモリ 良くない例 int fact(int n) { return n * fact(n - 1); } 注意1 終了条件を，正しく記述しないと 無限に繰り返される 注意2 実行時に与えるデータのサイズが大きいと，スタックメモリが満杯になり，プログラムが異常終了する

スタックのまとめ スタック 抽象データ型としてのスタック 連結リストによるスタックの実現 配列によるスタックの実現 スタックの利用例 ポーランド記法，逆ポーランド記法 再帰呼び出し(リカーシブ・コール，recursive call）

010C番地および010D番地からなるセルをリストから削除するには、何番地の内容をどのように変えればよいか答えよ。 問題１ 010C番地および010D番地からなるセルをリストから削除するには、何番地の内容をどのように変えればよいか答えよ。 ROOT 0091 0093 0094 009D 0000 0100 0091 0106 009C 0104 009D 0000 内容 番地 00FF 0101 0102 0103 0105 0093 0108 010E 009A 010C 009B 0102 内容 番地 0106 0107 0109 010A 010B 010D 0095 010A 0096 0112 0098 0114 0099 0000 内容 番地 010E 010F 0110 0111 0113 0115 ROOT 0094 削除

問題２ 0110番地から0115番地に格納されている3要素からなるサブリストを、問題１で削除する前のリストの要素009Aの直前に挿入するには、 （ 　　　　）番地の内容を0110に、（　　　　）番地の内容を010Aに 各々変えればよい。 0100 0091 0106 009C 0104 009D 0000 内容 番地 00FF 0101 0102 0103 0105 0093 0108 0094 010E 009A 010C 009B 0102 内容 番地 0106 0107 0109 010A 010B 010D 0095 010A 0096 0112 0098 0114 0099 0000 内容 番地 010E 010F 0110 0111 0113 0115 ROOT 挿入

問題1 0100 0091 0106 009C 0104 009D 0000 内容 番地 00FF 0101 0102 0103 0105 番地 内容 0095 010A 0096 0112 0098 0114 0099 0000 内容 番地 010E 010F 0110 0111 0113 0115 0106 0093 ROOT 0107 0108 0108 0094 0109 010E 010A 009A 010B 010C 0102 に変える 010C 009B 010D 0102

問題2 0110 に変える 0100 0091 0106 009C 0104 009D 0000 内容 番地 00FF 0101 0102 0103 0105 番地 内容 0095 010A 0096 0112 0098 0114 0099 0000 内容 番地 010E 010F 0110 0111 0113 0115 0106 0093 ROOT 0107 0108 0108 0094 0109 010E 010A 009A 010B 010C 010C 009B 010D 0102 010A に変える

図を簡略化すると 0110 p(010E番地) ROOT 0091 0093 0094 0095 p->next(010A番地) に変える p(010E番地) ROOT 0091 0093 0094 0095 p->next(010A番地) q(010A番地) 009A 009B 009C 009D r(0110番地) 0096 0098 0099 010A に変える (0000番地)