データ構造と アルゴリズム第4回 知能情報学メジャー 和田俊和

第２章　基本的なデータ構造 2.1 配列 2.2 リンク配置 2.3 連結リスト 2.4 スタック 2.5 キュー 2.6 木構造

2.4スタック 線形構造の片方だけから追加(push)と取り出し (pop)が出来るデータ構造．（データ抽象化） コンピュータの基本ソフトウエア（OS）や， ミドルウエア（コンパイラなどの言語処理系） で多用される．

2.4.1スタックの基本操作 線形構造の片方だけから追加(push)と取り出し (pop)が出来るデータ構造． ⇒Last In First Out (LIFO)とも呼ばれる

2.4.2スタックの実装 配列で表した場合: topは次にpushする場所．top>n-1で満杯の状態 を表している．

2.4.2スタックの実装 pushとpop

twada$ ./a.out akasakA twada$ C プログラムの例 #include <stdio.h> #include <stdlib.h> #define Num 10 char Stack[Num]; int top=0; void push(char c) { if (top>Num-1) { perror("Stack overflow\n"); exit(1); } Stack[top++]=c; char pop() if (top==0) { perror("Stack underflow\n"); return Stack[--top]; int main() {    char *str="Akasaka";    while(*str) { push(*str); str++;    }    while(top) printf("%c",pop());    printf("\n"); } twada$ ./a.out akasakA twada$

2.5キュー 配列の片方から追加(enqueue)し，反対側から 取り出し(dequeue)が出来るデータ構造． プリンタのバッファなど速度緩衝用メモリや， 木やグラフな どの横型探索に 使われる．

2.5.1キューの基本操作 最初にenqueueしたデータが最初に取り出され るので，First In First Out (FIFO)とも呼ばれる．

2.5.2キューの実装 配列を用いた実装 rearは次にenqueueする場所，frontは次に dequeueする場所．

2.5.2キューの実装 rear>n-1でOverflow front==rearでUnderflow

twada$ ./a.out Akasaka twada$ C プログラムの例 #include <stdio.h> #include <stdlib.h> #define Num 10 char Queue[Num]; int front=0; int rear=0; void enqueue(char c) { if (rear>Num-1) { perror("Queue overflow\n"); exit(1); } Queue[rear++]=c; char dequeue() if (front==rear) { perror("Queue underflow\n"); return Queue[front++]; int main() {    char *str="Akasaka";    while(*str) { enqueue(*str); str++;    }    while(front!=rear) printf("%c",dequeue());    printf("\n"); } twada$ ./a.out Akasaka twada$

2.5.3リングバッファ(改良されたキュー) キューではenqueしてもdequeueしてもfrontも rearも増加する一方． キューを環状ににしたのがリングバッファ

スタック／キューは何のために用いるか 系統的な記憶と想起のメカニズム スタック（ＬＩＦＯ） キュー（ＦＩＦＯ） 環境の保存と参照ー＞再帰呼び出し 木・グラフの縦型探索 キュー（ＦＩＦＯ） バッファ（緩衝用）メモリ、装置間の速度差の吸収 木・グラフの横型探索

スタックの利用の例：１ 迷路の探索：

探索木

迷路の探索アルゴリズム

list にスタックを用いた場合

木の縦型探索とスタック

再帰的構造 0, i=0 f(i)= 1, i=1 f(i-1)+f(i-2), i≧2 Fibonacci 数 int Fib(int i) { switch(i){ case 0: return(0);break; case 1: return(1);break; default: return(Fib(i-1)+Fib(i-2));} }

再帰的構造 Fib(3)→Fib(2)+Fib(1) →(Fib(1)+Fib(0))+1 →(1+0)+1 int Fib(int i) { switch(i){ case 0: return(0);break; case 1: return(1);break; default: return(Fib(i-1)+Fib(i-2));} } Fib(3)→Fib(2)+Fib(1) →(Fib(1)+Fib(0))+1 →(1+0)+1

再帰的構造 同じ変数名であっても、関数呼び出しの度に、別の記憶領域が確保される（スタックを利用している。） 変数の内容は、他の関数呼び出しによって破壊されることはない。

演習問題 設問３ 5,4,8がこの順にpopされ，底から2,7,6 がスタックに残る． 設問４　5,2がこの順にdequeueされ，7,3が queueの中身（次にdequeueすると3が取り出さ れる．）

演習問題 設問５（レポートの提出） if ((front-rear+n)%n==1) rear=(rear+1)%n; front=(front+1)%n;