데이터구조 (Chapter 3: Stacks and Queues) 2011 년봄학기 숙명여자대학교이과대학멀티미디어과학과박영호

Transcription

1 데이터구조 (Chapter 3: Stacks and Queues) 2011 년봄학기 숙명여자대학교이과대학멀티미디어과학과박영호

2 Index Chapter 01: Basic Concepts Chapter 02: Arrays and Structures Chapter 03: Stacks and Queues Chapter 04: Lists Chapter 05: Trees Chapter 06: Graphs Chapter 07: Sorting Chapter 08: Hashing Chapter 09: Heap Structures Chapter 10: Search Structures Special Lecture : Index Structures for Multimedia Young-Ho Park Sook Myung Women's Univ. 2

3 Chapter 3 -Stacks and Queues- 3.1 The Stack Abstract Data Type 3.2 The Queue Abstract Data Type 3.3 예제 : 미로문제 ( 생략 ) 3.4 Evaluation of Expressions 3.5 Multiple Stack

4 3.1 The Stack Abstract Data Type Stack: 삽입과삭제가한쪽끝 (top) 에서만일어나는순서가있는리스트 (ordered list) à LIFO (Last In First Out) 구조 예제 : Stack 에 A, B, C, D, E 순서로삽입하고, 한원소를삭제하는과정 B A A top top C B A top D C B A top E D C B A top D C B A top top Young-Ho Park Sook Myung Women's Univ. 4

5 Example: System Stack System Stack이란 program의 function calls의처리에사용되는 stack을말함 Function call 마다 stack frame (activation record) 을생성하여이것을 stack에삽입함 Function의수행이끝나면해당 stack frame을 system stack에서삭제함 a) 프로그램구조 A main() { call Sook(); } b) 이때, System Stack 의모습 main(): Sook() 부르기전 B procedure Sook() { return(); } Sook() 부른후스택 이전 frame pointer Return Address fp 이전 frame pointer Return Address fp 지역변수들 이전 frame pointer Return Address fp: 현재스택 frame pointer (stack top) Return Address: 함수수행후되돌아갈주소 이전 frame pointer: 부르고있는함수의 stack 프레임을가리키는포인터 Young-Ho Park Sook Myung Women's Univ. 5

6 Structure Stack is Stack ADT objects: a finite ordered list with zero or more elements functions: for all stack Stack, item element, max_stack_size positive integer Stack CreateS (max_stack_size) ::= max_stack_size 만큼을담을수있는빈스택을만들어라. Boolean IsFullS (stack, max_stack_size) ::= if ( 스택안의요소수 == max_stack_size) TRUE를반환한다. else FALSE를반환한다. Stack AddS (stack, item) ::= if (IsFullS (stack)) stack_full else 스택의 top에 item을삽입하고, 그스택을반환한다. Boolean IsEmpty (stack) ::= if ( 스택내의요소수 == 0) TRUE를반환한다. else FALSE를반환한다. Element DeleteS (stack) ::= if (IsEmpty(stack)) stack_empty else 스택 top에있는 item을지우고, 그스택을반환한다. End Stack; Young-Ho Park Sook Myung Women's Univ. 6

7 Stack ADT 에속한연산자들 Stack CreateS (max_stack_size) ::= #define MAX_STACK_SIZE 100 /* maximum stack size */ typedef struct { int key; /* 이부분에다른 field 들이올수있다. */ } element; element stack [MAX_STACK_SIZE]; int top = -1; Boolean IsEmptyS (Stack) ::= top < 0; Boolean IsFullS (Stack) ::= top > MAX_STACK_SIZE-1; Void AddS (int *top, element item) { /* 스택에 item 하나를추가 (push) 한다. */ if (*top > MAX_STACK_SIZE-1) { stack_full(); return; } stack [++*top] = item; } Young-Ho Park Sook Myung Women's Univ. 7

8 Stack ADT 에속한연산자들 ( 계속 ) element DeleteS (int *top) { /* 스택 top에있는요소 (element) 를반환한다. */ if (*top == -1) return stack_empty(); /* Error key를반환한다. */ return stack [(*top)--]; } Young-Ho Park Sook Myung Women's Univ. 8

9 3.2 The Queue Abstract Data Type Queue: 삽입이한쪽끝 (rear) 에서일어나고, 삭제가다른쪽끝 (front) 에서만일어나는 ordered list à FIFO (First In First Out) 구조 예제 ) Queue 에 A, B, C, D 순서로 insert 한후에한원소를 delete 하는과정 null rear front A rear front B A rear front C B A rear front D C B A rear front D C B rear front Young-Ho Park Sook Myung Women's Univ. 9

10 Queue as an Abstract Data Type struct Queue is objects: a finite ordered list with zero or more elements functions: for all queue Queue, item element, max_queue_size positive integer Queue CreateQ (max_queue_size) ::= 주어진크기를가지는빈 queue를만든다. Boolean IsFullQ (queue, max_queue_size)::= if (queue안에있는 element 개수 == max_queue_size) TRUE 반환 else FALSE 반환 Queue AddQ (queue, item) ::= if (IsFullQ(queue)) queue_full else queue 의 rear 에 item 삽입과그 queue 반환 Boolean IsEmptyQ (queue) ::= if (queue 안에있는 element 개수 == 0) TRUE 반환 else FALSE 반환 /* 이부분, 책이틀렸음 */ Element DeleteQ (queue) ::= if (IsEmptyQ(queue)) stack_empty 반환 else queue 의앞에있는 item 을삭제하고, 반환한다. Young-Ho Park Sook Myung Women's Univ. 10

11 Queue 상에주어지는연산들 Queue CreateQ (max_queue_size) ::= #define MAX_QUEUE_SIZE 100; type struct { int key; /* 여기에다른 field 들이온다 */ } 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 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의앞에서 element를삭제 */ if (*front == rear) return queue_empty(); /* error key( 숫자 ) 를반환한다. */ return queue [++*front]; } Young-Ho Park Sook Myung Women's Univ. 11

12 예제 : Queue 를사용한 job scheduling 운영체제에서 first-in-first-out (no priority) 방식의 job 처리에 queue 사용 1 차원 array 를 queue 로사용하는경우 Sequential queue ( 최대크기 4) 를사용하여 job의삽입과삭제를관리 Queue에서대기중인 job의수가 5개이상이면 queue full Queue full 이일어나면 front 쪽으로 shift 해야함 front rear Comments Q[0] Q[1] Q[2] Q[3] -1-1 queue is empty -1 0 J1 (job1) is added J1-1 1 J2 (job2) is added J1 J2-1 2 J3 (job3) is added J1 J2 J3 0 2 J1 (job1) is deleted J2 J3 1 2 J2 (job2) is deleted J3 Young-Ho Park Sook Myung Women's Univ. 12

13 Circular Queue 를사용한 job scheduling Circular Queue를써서 1차원 array 방식의단점 (Queue Full) 를해결함 AddQ, DeleteQ가 circular를다룰수있도록변경되어야함 초기치 : front=rear=0 front는첫원소보다반시계방향으로하나앞을지시한다. Rear는시계방향으로삽입한마지막원소를지시한다. Full 조건 : front == (rear+1) mod n ( 이때, n은 queue의크기 ) Empty 조건 : front == rear ( 주의 : full과 empty 구분위해한개는 empty로유지함 ) EMPTY 운영중 FULL FULL [2] [3] [2] [3] [2] [3] [2] [3] J2 J3 J2 J3 J8 J9 [1] [4] [0] [5] [1] J1 [4] [1] J1 J4 [4] J5 [0] [5] [0] [5] [1] J7 [4] J6 J5 [0] [5] Front=0 Front=0 Front=0 Front=4 Rear=0 Rear=3 Rear=5 Rear=3 Young-Ho Park Sook Myung Women's Univ. 13

14 Circular Queue 를위한 AddQ, DeleteQ Void AddQ ( int front, int * rear, element item) { /* queue에한개의 item을넣는다 */ *rear = (*rear+1) % MAX_QUEUE_SIZE; Void DeleteQ (int * front, int rear) { element item; /* queue에서 front element를지우고, item 변수에그 element를넣는다 */ if (front == *rear) { queue_full (rear); /* rear 를 reset 하고, error 를프린트 */ } queue[*rear] = item; } } if (*front==rear) return queue_empty(); /* 이함수는 error key를반환한다. */ *front = (*front+1) % MAX_QUEUE_SIZE; return queue[*front]; Young-Ho Park Sook Myung Women's Univ. 14

15 3.4 Evaluation of Expressions 3.5 Multiple Stack

16 3.4 Evaluation of Expressions Precedence Rule: Expression 에서계산순서를결정하는규칙 Precedence 와 associativity 로구성되는 precedence hierarchy 로표현됨 C 언어의 precedence hierarchy: (see text book, p.137) Expression 의표현방법 예제 ) Infix: 사람이 ( 혹은고급언어 ) 사용하기에편리한표현법 (e.g.: a+b) Postfix: 컴퓨터가계산하는데편리한표현법 (e.g.: ab+) 으로써괄호와 precedence rule 을알필요없이 stack 을사용해서쉽게계산가능 Prefix: 컴퓨터가계산하는데편리한표현법 (e.g.:+ab) infix postfix 2+3*4 234*+ a*b+5 ab*5+ (1+2)*7 12+7* a*b/c (a/(b-c+d))*(e-a)*c a/b-c+d*e-a*c ab*c/ abc-d+/ea-*c* ab/c-de*+ac*- Young-Ho Park Sook Myung Women's Univ. 16

17 Infix 형태의 expression 을 postfix 로변환하는방법 #1 Step1) Expression 을 precedence rule 에따라괄호를첨가한다. Step2) 모든연산자를대응하는오른쪽괄호위치에옮긴다. Step3) 모든괄호를없앤다. 예제 ) a/b-c+d*e-a*c à (((a/b)-c)+(d*e))-(a*c)) à ab/c-de*+ac*- 이방법의단점 Expression 을두번 scan 해야한다. 즉, 괄호첨가을위해 1 번 scan 하고, 연산자이동을위해서또 1 번 scan 해야한다. Young-Ho Park Sook Myung Women's Univ. 17

18 Infix 형태의 expression 을 postfix 로변환하는방법 #2 연산자들을보관하는 Stack 을사용하여연산자의수행순서를조정하는방식으로수행시간이 Θ(n), ( 이때, n 은입력토큰수 ) 이되게한다. 우선순위가높은연산자를먼저출력하도록 연산자 Stack 에 push 해서역순으로출력한다. 1) top = -1; Stack[top] = eos; /* eos: end of stack, 즉초기화 */ 2) 모든 input token, op1 에대하여 1) op1 == operand 이면, à output(op1); /* op1 을출력한다. */ 2) op1 == ) 이면, à ( 이나올때까지연속해서 output( pop(stack) ); /* ( 는제거 */ 3) 1) 과 2) 가아니면, à while ( icp (op1) <= isp ( Stack[top] ) ) output ( pop(stack) ); /* 유입되는 op1 의우선순위가현재, stack top 에있는요소의우선순위보다낮은경우에는, 계속해서 연산자스택 top 에있는요소를 pop 해서출력한다. 즉, 들어오는것보다높은연산자가있으면모두 pop 된다 */ Push (Stack, op1); ( 이때, icp : incoming precedence, isp : in-stack precedence) Young-Ho Park Sook Myung Women's Univ. 18

19 Postfix 로변환하는방법 #2 계속 우선순위테이블 (priority table) icp : incoming precedence ( 연산할때만난토큰의우선순위 ) isp : in-stack precedence ( 연산자 Stack 안에서새롭게부여된우선순위 ) op1 을 연산자 stack 에 push 한다 의의미 à 연산자 stack[top] 에있는연산자보다, op1 을먼저계산하겠다! 테이블표현 ( 숫자가높을수록우선순위가높다, stack top 보다크면, push 한다 ) 수식에서연산자 (op1) 이 icp 를가진다고하면, 기존 stack top 의연산자와우선순위를비교한다. 이때, stack top 연산자보다우선순위가크면, stack 에 push 된다. 연산자가 stack 에 Push 된후, ( 의경우, 우선순위가낮아진다. 이것은 ) 이올때까지모든연산자를다받아들이겠다는의미이다. op1 ( i c p ( 비교될때우선순위 ) 20 ( 무조건 push 하겠다 ) i s p ( 스택내우선순위 ) 0 ( 변신, ) 올때를기다리겠다 ) ) *, /, % 이항 +, - eos 19 (dummy 역할을한다 ) 19 (dummy 역할을한다 ) ( 현스택모두를 pop함 ) 0 ( 어떤첫연산자도받아들임 ) Young-Ho Park Sook Myung Women's Univ. 19

20 예제 1: 단순표현 : a+b*c Token 연산자 Stack{isp} {icp} [-1] [0] [1] a + {12} b * {13} c eos{0} eos{0} eos eos eos eos eos + {12} + {12} + * {13} + * {13} top 출력설명 a a ab ab abc abc*+ all pop Young-Ho Park Sook Myung Women's Univ. 20

21 예제 2: 괄호가있는표현 : a*(b+c)*d Token 연산자 Stack{isp} top 출력설명 {icp} [-1] [0] [1] [2] a eos{0} -1 a * {13} eos * {13} 0 a ( {20} eos * ( {0} 1 a b eos * ( 1 ab + {12} eos * ( + {12} 2 ab c eos * ( + 2 abc ) eos * {13} 0 abc+ ( 까지 pop * {13} eos * 0 abc+* pop 후 push d eos * {13} 0 abc+*d eos {0} -1 abc+*d* Young-Ho Park Sook Myung Women's Univ. 21

22 Stack 을사용한 postfix 표현의계산방법 postfix 로표현된식이있다. 이제, 이것을계산해보자! postfix 표현식의예 : 6 2 / * + Operator (/, -, *, +) 가나올때까지 stack 에 TOKEN (6, 2, 3 ) 을 push 한다. Operator 가나오면, stack[top] 과 stack[top-1] 을 pop 하여계산해서 stack[top] 에 push 한다. ( 단항연산자의경우는 stack[top] 만 pop 한다.) 처리예 : 6 2 / * + 의계산 ß 원식은 (((6/2)-3+(4*2)) 이었음. token 6 2 / * + stack [0] [1] [2] /2 6/2 3 6/2-3 6/ / /2-3 4*2 6/2-3+4*2 top Young-Ho Park Sook Myung Women's Univ. 22

23 Let us recall~ ^^* We learned in Chapter 3 -Stacks and Queues- - The Stack Concepts and ADT - The Queue Concepts and ADT - Evaluation Techniques of Expressions using Stacks -Multiple Stack - Now, we focus on 2 or more stacks in 1 array, Can you imagine? - Here, we present a problem and the solution.

24 Array S: 3.5 Multiple Stack 하나의 1차원 array S에 2개혹은 n개의 stack을구현함.( 이때, n >= 3) 2개의 stack S1, S2을구현한경우 S1 S2 여기서무엇이문제? bottom1 top1 top2 bottom2 n 개의 stack 을구현한경우 ( 이때, S 의 element 수는 m 개 ) S 를 n 개의 segment 들로나누어서 à n 개의 stack 으로사용 ( 활용 ) 함 Array S: 이때, 변경되는부분 : Stack 의 full 과 empty 를검사하는알고리즘이변경되므로, stack 에 element 를 add, delete 하는알고리즘이변경되어야함 처음에대략같은 segment (m/n) 들로나뉘어지고, 현재모든 stack 들은비어있는모습이다 m/n 2 m/n 1 st stack 2 nd stack n th stack m-1 boundary[0] top[0] boundary[1] top[1] boundary[2] top[2] boundary[n] Young-Ho Park Sook Myung Women's Univ. 24

25 수정된 add/delete algorithm void AddS (int i, element item) { /* add an item to the i th stack */ if (top[i] == boundary[i+1]) /* stack full? */ return stack_full (i); memory [++top[i]] = item; } void DeleteS (int i) { /* remove top element from the i th stack */ if (top[i] == boundary[i]) /* stack empty? */ return stack_empty (i); return memory [top[i]--]; } Young-Ho Park Sook Myung Women's Univ. 25

26 기존방법의문제점및해결방안 Stack full ckeck 에서 t[i] = b[i+1] 이면, stack i 는 full 이나, 전체적으로는빈곳이많게된다. ( 빈곳색은찬곳색은 ) S: b[0] t[0] b[1] t[1] b[i] t[i] t[i+1] b[i+1] b[i+2] b[j] t[j] b[j+1] b[n] < 전체적으로빈곳이많아도 stack i 가 full 나서 stack i+1 과붙어지는문제가발생한경우를보임 > 빈곳을없애는방법 : stack_full(i) 을다음과같이설계하면된다. 1. Stack i 의오른쪽에서빈공간을찾아서 shift 한다. stack j 와 j+1 사이에빈공간을가지는, 즉, t(j) < b(j+1) 되는최소의 j (i<j<=n) 를찾는다. 만약그러한 j 가오른쪽에있다면, i 이후의 stack i+1, i+2,, j 를오른쪽으로한자리씩옮겨서 stack i 와 i+1 사이에공간을만든다. 2. (1) 단계에서만족하는 j 가없으면, stack i 의왼쪽에서빈공간을찾아 shift j 가 1 <= j < i 인 j 에대하여 stack j 와 stack j+1 사이에빈공간이있는, 즉 t(j) < b(j+1) 인최대 j 를찾는다. 그러한 j 가왼쪽에있으면, j 이후의 stack j+1, j+2,, i 를왼쪽으로한자리씩옮겨와 stack i 와 i+1 사이에빈공간을만든다. 3. (1), (2) 단계를만족하는 j 가없으면모든공간은 Full 이된것이다. Young-Ho Park Sook Myung Women's Univ. 26

27 Thanks! Students! Let s finish Stack & Queue However, ᅲ Stack & Queue is strict & fixed structures We expect more interesting data structures with flexibility. Please be wait for the wonderful thing ^ ^*