アルゴリズムとデータ構造 第4回 配列によるスタックとキュー
本日の講義内容 配列とスタック 動的なメモリー確保によるスタック キュー
配列とスタック 整数のスタックを配列で作る。 #define SMAX 1000 int stackbase[SMAX]; int *stack=stackbase; ここでは、大きさ１０００のスタックを用意 して、データの挿入位置を示すポインタとして stackを定義した。
PUSH void push(int x){ if(stack>=stackbase+SMAX) stackerr(“Overflow”); *stack++=x; return ; }
POP int pop(void){ if(stack<=stackbase) stackerr(“Underflow”); return *--stack; } stackを-1してから、その中身を取り出している。
スタックの表示 void print_stack(void){ int *p=stack; int n=0; while(p>stackbase) printf("%d: %d\n",n++,*--p)； }
動的なスタックの確保 int *stackbase; int *stack=stackbase; int stack_size; void init_stack(void){ stackbase= (int *)malloc(SMAX*sizeof(int)); stack=stackbase; stack_size=SMAX; }
スタックの拡張 void extend_stack(void){ int *p,new; new=stack_size*2; p=realloc(stackbase,new*sizeof(int)); if(p==NULL) exit(999); stack=p+(stack-stackbase); // need () because p+n is allowed stackbase=p; stack_size=new; }
キュー(queue) スタックはLIFO(Last In First Out) キューはFIFO(First In First Out) 線形リストまたは配列で実現できる。
キューの配列による実現 ring buffer として考える。つまり、配列を １つの円循環とみなす。 int que[SMAX]; int *first=que,*next=que,*bound=que+SMAX; int total=0;
データの挿入(enque) void enque(int x){ if(total>=SMAX){ que_err("Overflow"); exit(999); } if(next>=bound) next=que; *next++=x; total++;
データの取り出し(deque) int deque(void){ if(total==0){ que_err("Underflow"); return -1; } if(first>=bound) first=que; total--; return *first++;