PowerPoint Presentation

Transcription

1 スタックと待ち行列 Algorithms and Data Structures on C

2 この回の要点 スタック スタックの構造 最後に入れたものが 最初に取り出される (LIFO) 日常に良くある ちょっと置いといて の概念 C 言語の配列による実装 スタックオーバーフロー スタックアンダーフロー 逆ポーランド記法電卓 待ち行列 待ち行列の構造 最初に入れたものが 最初に取り出される (FIFO) 日常に良くある 行列 の概念 C 言語の配列による実装 リングバッファの利用

3 スタック ( 棚 ) データの挿入と削除が リストの先頭だけ 生協のトレイ 生協の人は 置き場の一番上に新しいトレイを置く 使う人は 置き場の一番上のトレイを取る LIFO(Last In First Out) 置く 取る 生協の人 使う人 置き場 スタック

4 身近なスタック 日常生活の中にもスタックがある とりあえず置いといて の概念 本を読む辞書を引く来客対応電話に出る 心の中のスタック 積む 積む 積む 取る 取る 取る 来客 本 辞書本 辞書本 辞書本 本

5 スタックの構造 箱が上に積み上がっていく構造 最初の要素 スタックの底 (bottom) 最後の要素 スタックの頂上 (top) データの挿入 スタックに積む (push) データの削除 スタックから取り出す (pop) Push Pop Top Bottom

6 スタックの利用 機械語の Push Pop 命令 スタックポインタ (SP) の示すアドレスにデータを保存 読み出し サブルーチンコールの戻り値の自動保存 復元 C の関数や Java のメソッド呼び出し 引数をスタックに積んで渡す Push (FF) スタック int add(int a,int b){ return a+b; SP SP SP FF 3A 24 Pop (3A) 4 3 int main(){ int ans=add(3,4);

7 配列によるスタックの実現 最大サイズは固定 (=M) stack[0] がスタックの底 (bottom) stack[m-1] がスタックの最大 stack[sp-1] がスタックの頂上 (top) sp : スタックポインタ 最初は sp=0 Push するたびに sp=sp+1( 但し sp=m 以外 ) Pop するたびに sp=sp-1( 但し sp=0 以外 ) stack[] sp sp は常に空の箱を指す # # # # # # # # # # # M-1

8 SimpleStack.cc /*** 簡単なスタック ***/ #include <stdio.h> #include <stdlib.h> // スタック用変数 const int size=100; int stack[size]; int sp=0; // スタックサイズ // スタック // スタックポインタ // プッシュ void push(int n){ if(sp==size){ fprintf(stderr,"error: stack overflow. n"); exit(1); stack[sp++]=n; 代入してから sp を増やす

9 SimpleStack.cc // ポップ int pop(){ if(sp==0){ fprintf(stderr,"error: stack underflow. n"); exit(1); return stack[--sp]; // 表示 void print(){ printf("%d:",sp); for(int i=0;i<sp;i++) printf("%d ",stack[i]); printf(" n"); sp を減らしてから取り出す

10 SimpleStack.cc // メイン int main(void){ print(); push(1); push(2); push(3); push(4); push(5); print(); pop(); pop(); print(); push(6); push(7); push(8); print(); pop(); pop(); pop(); pop(); pop(); print(); pop(); pop(); print();

11 簡単なスタックの例 ( 結果 ) $./SimpleStack 0: 5: : : :1 Error: stack underflow. $ 1 つしか要素が入っていないスタックから 2 つの要素を取り出そうとした

12 ヘッダファイルを使った実装 スタックだけを実装する 他のソースコードから利用可能にする 2 つのファイルに分ける StackInt.h 整数スタック型の宣言 関数のプロトタイプ宣言 StackInt.cc 関数の実装 利点 スタックを使いたいとき その都度実装する必要がない オブジェクト指向的な利用法

13 StackInt.h #ifndef StackInt h #define StackInt h /*** *** 整数スタック ***/ #include <stdio.h> #include <stdlib.h> // 整数スタック型の宣言 typedef struct { int *stack; // スタック int sp; // スタックポインタ int size; // スタックサイズ (= 最大要素数 ) StackInt; 続く

14 StackInt.h 第 1 引数にスタックサイズを指定する // プロトタイプ宣言 StackInt *makestackint(int s); void free(stackint *si); void push(stackint *si,int n); int pop(stackint *si); int peek(stackint *si); int getsize(stackint *si); void print(stackint *si); #endif // StackInt h // スタックの生成 // スタックの解放 // プッシュ // ポップ // ピーク // 要素数 // 内部の表示 第 1 引数に必ず StackInt* を指定する ( どのスタックを操作するかを指定 )

15 StackInt.cc /*** StackInt の実装 ***/ #include "StackInt.h" // スタックの生成 StackInt *makestackint(int s){ StackInt *si=(stackint*)malloc(sizeof(stackint)); si->size=s; si->stack=(int*)malloc(si->size*sizeof(int)); si->sp=0; return si; // スタックの解放 void free(stackint *si){ free(si->stack); free((void*)si); StackInt* si StackInt stack sp size si->size スタック実体 続く

16 StackInt.cc // プッシュ void push(stackint *si,int n){ if(si->sp==si->size){ fprintf(stderr,"error: stack overflow. n"); exit(1); si->stack[si->sp++]=n; // ポップ int pop(stackint *si){ if(si->sp==0){ fprintf(stderr,"error: stack underflow. n"); exit(1); return si->stack[--si->sp]; 続く

17 StackInt.cc // ピーク int peek(stackint *si){ if(si->sp==0){ fprintf(stderr,"error: stack underflow. n"); exit(1); return si->stack[si->sp-1]; // 現在の要素数 int getsize(stackint *si){ return si->sp; 続く

18 StackInt.cc // 内部の表示 void print(stackint *si){ printf("%d:",si->sp); for(int i=0;i<si->sp;i++) printf("%d ",si->stack[i]); printf(" n");

19 利用法 整数スタックを使用したいソースコード #include StackInt.h StackInt 型とプロトタイプ関数が使用可能 リンク StackInt.o をリンクする Cygwin の bash での Makefile CC = g++ all:stacktest SimpleStack StackTest:StackTest.o StackInt.o StackTest.o:StackTest.cc StackInt.h StackInt.o:StackInt.cc StackInt.h SimpleStack:SimpleStack.cc

20 StackTest.cc /*** 配列によるスタックの実装例 ***/ #include "StackInt.h" ヘッダの読み込み // メイン int main(int argc,char **argv){ StackInt *si=makestackint(100); print(si); push(si,1); push(si,2); push(si,3); push(si,4); push(si,5); print(si); pop(si); pop(si); print(si); push(si,6); push(si,7); push(si,8); print(si); pop(si); pop(si); pop(si); pop(si); pop(si); print(si); pop(si); pop(si); print(si); free(si); StackInt の破棄 StackInt の生成 第 1 引数に必ず StackInt* を指定する

21 逆ポーランド記法 (RPN) Reverse Polish Notation 演算子を操作対象の後に書く記法 後置記法 (Postfix Notation) 括弧 ( ) が不要 デミリタ ( 区切り文字 ) が必要 計算機で演算を行う場合に便利 スタックを利用すると簡単 (1+2)*(4+6) * (1+2)*(3+4*(2-3)) * + * 通常記法 逆ポーランド記法

22 スタックによる逆ポーランド電卓 入力トークンを 1 つずつ読み 数字ならスタックに積む 演算子なら スタックから 2 つ取り出して計算して その結果をスタックに積む (1+2)*(4+6)=? * *

23 NRPCalc.cc /*** *** 逆ポーランド記法電卓 ***/ #include "StackFloat.h" float を要素とするスタック (StackInt を参考に ) // メイン int main(int argc,char **argv){ // 起動メッセージ printf("*** Reverse Polish Notation Calculator *** n"); // スタックを準備する StackFloat *sf=makestackfloat(100); 続く

24 NRPCalc.cc // 入力待ちループ int end_flag=0; double n1,n2; char buf[100]; while(!end_flag){ if(scanf("%s",buf)!=1) break; switch(buf[0]){ case '+': n2=pop(sf); n1=pop(sf); push(sf,n1+n2); break; case '-': n2=pop(sf); n1=pop(sf); push(sf,n1-n2); break; case '*': n2=pop(sf); n1=pop(sf); push(sf,n1*n2); break; case '/': n2=pop(sf); n1=pop(sf); push(sf,n1/n2); break; case '=': printf("%f n",peek(sf)); break; case 'p': print(sf); break; case 'q': end_flag=1; break; default : push(sf,atof(buf)); // スタックを開放する free(sf);

25 逆ポーランド電卓の実行結果 $./RPNCalc 1+2=? = 3.0 4と5と6を追加 リスト p 4: (5+6)*4 リスト + * p 2: * + (0-1)*44+3 リスト p 1: ? + 1つしか要素が入っ Error: stack underflow ていないスタックか $ ら2つの要素を取り出そうとした

26 待ち行列 (Queue) 挿入が一方の端 削除がもう一方の端 生協のレジの行列 客は行列の最後尾に並ぶ レジが終わると 行列の先頭の客が抜ける FIFO(First In First Out) レジ 待ち行列

27 待ち行列の構造 パイプに詰め込まれた積み木の構造 詰め込むの端 末尾 (rear) 取り出す端 先頭 (front) 要素の追加 待ち行列に入れる (enqueue) 要素の削除 待ち行列から取り出す (dequeue) dequeue enqueue front rear

28 待ち行列の利用 マルチタスク処理 複数のタスクを 1 つの CPU で処理するには それぞれのタスクを待ち行列に入れて CPU が 1 つずつそれを取り出して処理する 印刷処理 1 つのプリンタで複数の印刷物を印刷する場合は 各印刷データは印刷キューに入れられ プリンタが 1 つずつ順番に取り出して印刷する

29 配列による待ち行列の実現 先頭 front こちらへ移動していく 末尾 rear 先頭が抜けるたびに移動 無限に長い配列? 末尾に来るたびに移動 待ち行列 長さ = 待っている要素数

30 リングバッファによる待ち行列の実現 無限に長い配列は現実には不可能 リングバッファを使用する 有限長の配列の先頭と末尾をつないだもの 配列 q[] で q[m-1] の次に q[0] があると考える 具体的には 配列サイズ M の剰余をインデックスとする q[m-1] q[0] q[m-2] リングバッファ q[1] 待ち行列 q[2] front q[3] rear

31 リングバッファの利用法 初期状態 :front=1,rear=0 取り出し : front の位置の要素を取り出してから front を移動 front++ q[(front++)%m] にアクセス 詰め込み : rear を移動してから rear 次の位置に入れる ++rear q[(++rear)%m] にアクセス %M を行うことで リングバッファになる q[] M-1 q[front%m] q[rear%m] %M

32 リングバッファの注意 front=rear+1 の状態は空? フル? 待ち行列の長さを保持することによって判断できる 追加 削除時の制限 M-1 length=0 front=rear+1 front 取り出せない! rear M-1 length=m front=rear+1 詰め込めない!

33 QInt.h #ifndef QInt h #define QInt h /*** *** 整数用キュー ***/ #include <stdio.h> #include <stdlib.h> // 整数キュー型の宣言 typedef struct { int *q; int size; int front,rear; int length; QInt; // キュー // キューサイズ // キューポインタ // キューに実際に入っているデータ数 続く

34 QInt.h // プロトタイプ宣言 QInt *makeqint(int s); // 整数キューの生成 void free(qint *qi); // キューの破棄 void enq(qint *qi,int n); // エンキュー int deq(qint *qi); // デキュー int peek(qint *qi); // ピーク int getsize(qint *qi); // 要素数 void print(qint *qi); // 内部の表示 #endif // QInt h

35 QInt.cc /*** *** QInt の実装 ***/ #include "QInt.h" // 整数キューの生成 QInt *makeqint(int s){ QInt *qi=(qint*)malloc(sizeof(qint)); qi->size=s; qi->q=(int*)malloc(qi->size*sizeof(int)); qi->front=1; qi->rear=0; qi->length=0; return qi; 続く

36 QInt.cc // エンキュー void enq(qint *qi,int n){ if(qi->length==qi->size){ fprintf(stderr,"error:... n"); exit(1); num=0 rear front enqueue num=1 // デキュー int deq(qint *qi){ if(qi->length==0){ fprintf(stderr,"error:... n"); exit(1); 続く ここに enqueue 処理を書く ここに dequeue 処理を書く num=2 num=3 num=2 enqueue enqueue dequeue

37 QInt.cc // ピーク int peek(qint *qi){ if(qi->length==0){ fprintf(stderr,"error: queue underflow. n"); exit(1); return qi->q[qi->front%qi->size]; // 要素数 int getsize(qint *qi){ return qi->length; 続く

38 QInt.cc // 内部の表示 void print(qint *qi){ printf("%d:",qi->length); for(int i=0;i<qi->length;i++) printf("%d ",qi->q[(qi->front+i)%qi->size]); printf(" n"); // キューの解放 void free(qint *qi){ free(qi->q); free((void*)qi);

39 QTest.cc /*** キューのテスト ***/ #include "QInt.h" int main(int argc,char **argv){ QInt *qi=makeqint(100); print(qi); enq(qi,1); enq(qi,2); enq(qi,3); enq(qi,4); print(qi); deq(qi); deq(qi); print(qi); enq(qi,5); enq(qi,6); print(qi); deq(qi); deq(qi); deq(qi); print(qi); deq(qi); deq(qi); print(qi); free(qi);

40 簡単な待ち行列の例 ( 結果 ) $./QTest 0: 4: : 3 4 4: : 6 Error: queue underflow $ 1 つしか要素が入っていない待ち行列から 2 つの要素を取り出そうとした

41 課題 QInt.cc の enq() と deq() の不足しているコードを示せ QInt を用いて 10 個の整数をキューに入れ それを取り出して表示するプログラム QTest2.cc を作成せよ 実行結果を示せ 作成方法 : ソースコードを入力し 不足部分を補い コンパイル 実行し その結果を示すこと レポートはワードで作成すること レポートの最初に学籍番号と氏名を明記すること ワードのファイル名は scxxxxxx-al docx とすること 完成したソースファイルを ワード文書中に貼り付けて示せ 提出方法 : メールで メールの本文中にも学籍番号を氏名を明記すること 提出先 :fuchida@ibe.kagoshima-u.ac.jp メールタイトル : アルゴリズム課題 厳守! 期限 :2017 年 11 月 5 日 ( 日 ) 24:00

42 スタックと待ち行列 終了