PowerPoint 프레젠테이션

Transcription

1 제 3 장. 스택과큐 순서리스트의특별한경우순서리스트 : A=a 0, a 1,, a n-1, n 0 스택 (stack) 톱 (top) 이라고하는한쪽끝에서모든삽입 (push) 과삭제 (pop) 가일어나는순서리스트 스택 S=(a 0,...,a n-1 ): a 0 는 bottom, a n-1 은 top의원소 a i 는원소 a i-1 (0<i<n) 의위에있음 후입선출 (LIFO, Last-In-First-Out) 리스트

2 스택 (Stack) 원소 A,B,C,D,E 를삽입하고한원소를삭제하는예 E top D top D D C top C C C B top B B B B A top A A A A A top add add add add del

3 [ 스택추상데이타타입 ] structure Stack objects: 0 개이상의원소를가진유한순서리스트 functions: 모든 stack Stack, item element, max_stack_size positive integer Stack CreateS(max_stack_size) ::= 최대크기가 max_stack_size 인공백스택을생성 Boolean IsFull(stack, max_stack_size) ::= if (stack 의원소수 == max_stack_size) return TRUE else return FALSE Stack Add(stack, item) ::= if (IsFull(stack)) stack_full else stack 의톱에 item 을삽입하고 return Boolean IsEmpty(stack) ::= if (stack == CreateS(max_stack_size)) return TRUE else return FALSE Element Delete(stack) ::= if (IsEmpty(stack)) stack_empty else 스택톱의 item 을제거해서반환

4 스택추상데이터타입의구현 일차원배열 stack[max_stack_size] 사용 i번째원소는 stack[i-1] 에저장 top은스택의최상위원소를가리킴 ( 초기 : top = -1) Stack CreateS(max_stack_size) ::= #define MAX_STACK_SIZE 100 /* 최대스택크기 */ typedef struct { int key; /* 다른필드 */ element; element stack[max_stack_size]; int top = -1; Boolean IsEmpty(Stack) ::= top < 0; Boolean IsFull(Stack) ::= top >= MAX_STACK_SIZE-1;

5 스택에대한접근은최상위원소에대한포인터를통해 void add(int *top, element item) { /* 전역 stack에 item을삽입 */ if (*top >= MAX_STACK_SIZE-1) { stack_full(); // 포화상태일때처리 return; stack[++*top] = item; element delete(int *top) { /* stack의최상위원소를반환 */ if (*top == -1) return stack_empty(); /* 오류 key를반환 */ return stack[(*top)--];

6 큐 (queue) 한쪽끝 (rear) 에서삽입이일어나고그반대쪽끝 (front) 에서삭제가일어나는순서리스트 큐 Q=(a 0,a 1,...,a n-1 ): a 0 는앞 (front) 원소 a n-1 은뒤 (rear) 원소 a i 는 a i-1 (1 i<n) 의뒤에있다고함 선입선출 (FIFO, First-In-First-Out) 리스트 그림 3.4 큐에서의삽입과삭제

7 [ 큐추상데이타타입 ] structure Queue objects: 0 개이상의원소를가진유한순서리스트 functions: 모든 queue Queue, item element, max_queue_size positive integer Queue CreateQ(max_queue_size) ::= 최대크기가 max_queue_size 인공백큐를생성 Boolean IsFullQ(queue, max_queue_size ) ::= if (queue 의원소수 == max_queue_size) return TRUE else return FALSE Queue AddQ(queue, item) ::= if (IsFull(queue)) queue_full else queue 의뒤에 item 을삽입하고이 queue 를반환 Boolean IsEmptyQ(queue) ::= if (queue == CreateQ(max_queue_size)) return TRUE else return FALSE Element DeleteQ(queue) ::= if (IsEmpty(queue)) return else queue 의앞에있는 item 을제거해서반환

8 큐의구현 : 1 차원배열이용 변수 front 는큐에서첫원소의위치보다하나작은위치 변수 rear 는큐에서마지막원소의위치 Queue CreateQ(max_queue_size) ::= #define MAX_QUEUE_SIZE 100 /* 큐의최대크기 */ typedef struct { int key; /* 다른필드 */ element; element queue[max_queue_size]; int rear = -1; int front = -1; Boolean IsEmptyQ(queue) ::= front == rear Boolean IsFullQ(queue) ::= rear == MAX_QUEUE_SIZE-1

9 void addq(int *rear, element item) { /* queue에 item을삽입 */ if (*rear == MAX_QUEUE_SIZE-1) { queue_full(); return; queue[++*rear] = item; element deleteq(int *front, int rear) { /* queue의앞에서원소를삭제 */ if (*front == rear) return queue_empty(); /* 에러 key를반환 */ return queue[++*front];

10 큐의순차적표현의문제점예 예제 3.2 [ 작업스케쥴링 ]: 운영체제의작업큐 (job queue) 작업들이큐에들어가고나옴에따라큐는점차오른쪽으로이동 결국 rear 값이 MaxSize-1과같아져서큐가포화상태가됨 fro nt rear Q (1) [1] [2] [3] [4] [5] [6] queue em pty J1 J1 J2 J1 J2 J3 J2 J3 J2 J3 J4 J3 J4 com m ents initial job 1 joins Q job 2 joins Q job 3 joins Q job 1 leaves Q job 4 joins Q job 2 joins Q

11 순차적큐의문제해결 : 원형큐 배열 queue[maxsize] 를원형으로취급 rear == MaxSize-1 이면 q[0] 가빈경우 q[0] 에삽입 MaxSize 를최대원소로사용하면원형큐는포화와공백모두 front == rear 가됨 이를구분하기위해포화상태는원소수가 MaxSize-1 일경우로함 front == rear 는공백상태로만사용 초기 : front == rear == 0

12 공백큐 [2] [3] [2] [3] J2 J3 [1] [4] [1] J1 [4] [0] [5] front = 0 rear = 0 [0] [5] front = 0 rear = 3 포화큐 포화큐 [2] [3] [2] [3] J2 J3 J8 J9 [1] J1 J4 [4] [1] J7 [4] J5 J6 J5 [0] [5] front = 0 rear = 5 [0] [5] front = 4 rear = 3

13 void addq(int *front, int *rear, element item) { /* queue 에 item 을삽입 */ *rear = (*rear+1) % MAX_QUEUE_SIZE; if (front == *rear) queue_full(rear); /* rear 를리세트시키고에러를프린트 */ return; queue[*rear] = item; void deleteq(int *front, int rear) { element item; /* queue 의 front 원소를삭제하여그것을 item 에놓음 */ if (*front == rear) return queue_empty(); /* queue_empty 는에러키를반환 */ *front = (*front+1) % MAX_QUEUE_SIZE; return queue[*front];

14 미로문제 스택을응용할수있는예 미로는 1 i m, 1 j p 인이차원배열 maze[m][p] 로표현 1 : 막힌통로, 0 : 열린통로 maze[1][1] 에서출발 maze[m][p] 에출구 입구 이동은 0 이있는사각형만 다음장그림 경계조건을매번검사하지않고미로주위를 1 로만듦, maze[m+2][p+2] 를사용, 첨자 i=0, m+1, j=0, p+1 일때는모두 출구

15 미로에서가능한이동 현재의위치 x : maze[i][j] 에서가능한이동 NW N NE [i-1][j-1] [i-1][j] [i-1][j+1] W [i][j-1] X [i][j+1] E [i] [j] [i+1][j-1] [i+1][j] [i+1][j+1] SW S SE 경계위치에서는 8 방향이아님 I = 1 or m, j=1 or m 3 방향, 5 방향만가능한경우

16 이동할수있는방향들을정의 typedef struct { short int vert; short int horiz; offsets; offsets move[8]; /* 여덟방향이동에대한배열 */ N am e D ir m ove[dir].vert m ove[dir].horiz N NE E SE S SW W NW 다음이동위치 : maze[next_row][next_col] next_row = row + move[dir].vert; next_col = col + move[dir].horiz;

17 경로의탐색 현위치저장후방향선택 : N에서시계방향 잘못된경로의선택시는 backtracking후다른방향시도 시도한경로의재시도방지 mark[m+2][n+2] : 초기치 0 mark[row][col] = 1 /* 한번방문한경우 */ - 경로유지위한스택사용 #define MAX_STACK_SIZE 100 /* 스택의최대크기 */ typedef struct { short int row; short int col; short int dir; element; element stack[max_stack_size]; MAX_STACK_SIZE 는스택에저장되는최대원소수. 미로의각위치는기껏해야한번만방문되므로 mp

18 initialize a stack to the maze's entrance coordinates and direction to north; while (stack is not empty) { /* 스택의톱에있는위치로이동 */ <rol, col, dir> = delete from top of stack; while (there are more moves from current position) <next_row, next_col> = coordinate of next move; dir = direction of move; if ((next_row == EXIT_ROW) && (next_col == EXIT_COL)) success ; if(maze[next_row][next_col]==0)&&mark[next_row][next_col]==0) { /* 가능하지만아직이동해보지않은이동방향 */ mark[next_row][next_col] = 1; /* 현재의위치와방향을저장 */ add <row, col, dir> to the top of the stack; row = next_row; col = next_col; dir = north; printf("no path found");

19 void path(void) // 프로그램 3.8 미로탐색함수 {/* 미로를통과하는경로가있으면그경로를출력한다. */ int i, row, col, next_row, next_col, dir, found=false; element position; mark[1][1]=1; top=0; stack[0].row=1; stack[0].col=1; stack[0].dir=1; while (top>-1 &&!found) { position = delete(&top); row = position.row; col = position.col; dir = position.dir; while (dir<8 &&!found) { next_row = row + move[dir].vert; /* dir 방향으로이동 */ next_col = col + move[dir].horiz; if (next_row==exit_row && next_col==exit_col) found = TRUE; else if (!maze[next_row][next_col] &&!mark[next_row][next_col]) { mark[next_row][next_col]) = 1; position.row = row; position.col = col; position.dir = ++dir; add(&top, position); row = next.row; col = next.col; dir = 0; else ++dir;

20 if (found) { printf("the path is:"); printf("row col"); for (i=0; i<=top; i++) printf("%2d%5d", stack[i].row, stack[i].col"); printf("%2d%5d", row, col); printf("%2d%5d", EXIT_ROW, EXIT_COL); else printf("the maze does not have a path"); path 알고리즘의분석 while 문은스택의크기에종속적이고최대 mp while 안의 while 은최대 8 번즉 O(1) 따라서 O(mp)

21 수식의계산 토큰 우선순위 결합성 () [] -> 17 LR L R & * unary - 15 R L * / % 13 L R L R > >= < <= 10 L R ==!= 9 L R && 5 L R 4 L R

22 수식의표현 - 중위표기 (infix notation) : a * b / c - 후위표기 (postfix notation) : a b * c / 예 ) x = a / b - c + d * e - a * c x = ((((a / b) - c) + (d * e)) - (a * c)) 후위표기 : x = a b / c - d e * a c * - + 괄호사용않함 왼쪽에서오른쪽으로계산 연산자의우선순위없음

23 후위표기식의연산 : 6 2 / * + 토큰 스택 Top [0] [1] [2] / 6/ / / / / * 6/2-3 4* /2-3+4*2 0

24 스택과수식의표현방법 #define MAX_STACK_SIZE 100 /* 스택의최대크기 */ #define MAX_EXPR_SIZE 100 /* 수식의최대크기 */ typedef enum {lparen, rparen, plus, minus, times, divide, mod, eos, operand precedence; int stack[max_stack_size]; /* 전역배열 */ char expr[max_expr_size]; /* 입력스트링 */ int eval(void) { /* 전역변수로되어있는후위표기식 expr 을연산한다. \0 은수식의끝을나타낸다. stack 과 top 은전역변수이다. 함수 get_token 은토큰의타입과문자심벌을반환한다. 피연산자는한문자로된숫자임을가정 */ precedence token; char symbol; int op1,op2; int n = 0; /* 수식스트링을위한카운터 */ int top = -1; token = get_token(&symbol, &n);

25 while (token!= eos) { if (token == operand) add(&top, symbol-'0'); / * 스택삽입 */ else { /* 두피연산자를삭제하여연산을수행후, 결과를스택에삽입 */ op2 = delete(&top); /* 스택삭제 */ op1 = delete(&top); switch(token) { case plus: add(&top, op1+op2); break; case minus: add(&top, op1-op2); break; case times: add(&top, op1*op2); break; case divide: add(&top, op1/op2); break; case mod: add(&top, op1%op2); token = get_token(&symbol, &n); return delete(&top); /* 결과를반환 */

26 precedence get_token (char *symbol, int * n) { /* 다음토큰을취한다. symbol 은문자표현이며, token 은그것의열거된값으로표현되고, 명칭으로반환된다. */ *symbol = expr[(*n)++]; switch (*symbol) { case '(' : return lparen; case ')' : return rparen; case '+' : return plus; case '-' : return minus; case '/' : return divide; case '*' : return times; case '%' : return mod; case NULL : return eos; default : return operand;

27 중위표기에서후위표기로의변환 왼쪽에서오른쪽으로조사해가면서후위식을생성 피연산자는바로출력수식에전달 연산자의출력순서는우선순위에의해좌우, 정확한위치를알때까지연산자를스택에저장 예제 3.3 중위표기식 a+b*c를후위표기식으로변환 토큰 스택 Top Output [0] [1] [2] a -1 a a b + 0 ab * + * 1 ab c + * 1 abc eos -1 abc*+

28 예제 3.4 중위표기식 a*(b+c)*d 를후위표기식으로변환 토큰 스택 Top Output [0] [1] [2] a -1 a * * 0 a ( * ( 1 a b * ( 1 ab + * ( + 2 ab c * ( + 2 abc ) * 0 abc+ * * 0 abc+* d * 0 abc+*d eos -1 abc+*d*

29 연산자의스택킹과언스택킹 왼쪽괄호는스택속에있을때는낮은우선순위, 그외의경우에는높은우선순위 왼쪽괄호는스택에쌓이고, 대응하는오른쪽괄호가나올때에만스택에서삭제 isp(in-stack precedence) 와 icp(incoming precedence) 정의하여스택속의연산자 isp 가새로운연산자의 icp 보다크거나같을때만스택에서삭제 precedence stack[max_stack_size]; /* isp와 icp 배열 -- 인덱스는연산자 lparen, rparen, plus, minus, times, divide, mod, eos의우선순위값 */ static int isp[] = { 0, 19, 12, 12, 13, 13, 13, 0 ; static int icp[] = {20, 19, 12, 12, 13, 13, 13, 0 ; 예 ) isp[plus] = isp[2] = 12, 오른쪽괄호 19, 왼쪽괄호 0, 20, eos 는 0 n : 수식의토큰수일때, θ(n)

30 void postfix(void) { /* 수식을후위표기식으로출력한다. 수식문자열, 스택, top 은전역적이다. */ char symbol; precedence token; int n = 0; int top = 0; /* eos 를스택에놓는다. */ stack[0] = eos;

31 for (token=get_token(&symbol,&n); token!=eos; token=get_token(&symbol,&n)) { if (token == operand) printf("%c", symbol); else if (token == rparen) { while (stack[top]!= lparen) /* 왼쪽괄호가나올때까지 */ print_token(delete(&top)); /* 토큰들을제거해서출력시킴 */ delete(&top); /* 좌괄호를버린다 */ else { //symbol의 isp가 token의 icp보다크거나같으면 symbol을제거하고출력 while (isp[stack[top]] >= icp[token]) print_token(delete(&top)); add(&top, token); // end of for-loop while ((token=delete(&top))!= eos) print_token(token); printf( \n");