アルゴリズムとデータ構造 第4回　配列によるスタックとキュー.

Presentation on theme: "アルゴリズムとデータ構造 第4回　配列によるスタックとキュー."— Presentation transcript:

1 アルゴリズムとデータ構造 第4回　配列によるスタックとキュー

2 本日の講義内容 配列とスタック 動的なメモリー確保によるスタック キュー

3 配列とスタック 整数のスタックを配列で作る。 #define SMAX 1000 int stackbase[SMAX];
int *stack=stackbase; 　ここでは、大きさ１０００のスタックを用意 して、データの挿入位置を示すポインタとして stackを定義した。

4 PUSH void push(int x){ if(stack>=stackbase+SMAX)
stackerr(“Overflow”); *stack++=x; return ; }

5 POP int pop(void){ if(stack<=stackbase) stackerr(“Underflow”);
return *--stack; } stackを-1してから、その中身を取り出している。

6 スタックの表示 void print_stack(void){ int *p=stack; int n=0;
while(p>stackbase) printf("%d: %d\n",n++,*--p)； }

7 動的なスタックの確保 int *stackbase; int *stack=stackbase; int stack_size;
void init_stack(void){ stackbase= (int *)malloc(SMAX*sizeof(int)); stack=stackbase; stack_size=SMAX; }

8 スタックの拡張 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; }

9 キュー(queue) スタックはLIFO(Last In First Out) キューはFIFO(First In First Out)
線形リストまたは配列で実現できる。

10 キューの配列による実現 ring buffer として考える。つまり、配列を １つの円循環とみなす。 int que[SMAX];
int *first=que,*next=que,*bound=que+SMAX; int total=0;

11 データの挿入(enque) void enque(int x){ if(total>=SMAX){
que_err("Overflow"); exit(999); } if(next>=bound) next=que; *next++=x; total++;

12 データの取り出し(deque) int deque(void){ if(total==0){ que_err("Underflow");
return -1; } if(first>=bound) first=que; total--; return *first++;