4장

Transcription

1 CHAP 5: 스택

2 스택이란? 스택 (stack): 쌓아놓은더미

3 스택의특징 후입선출 (LIFO:Last-In First-Out): 가장최근에들어온데이터가가장먼저나감. D C B C B C B C B A A A A

4 스택의구조 요소 (element) C 스택상단 (top) B A 스택하단 (bottom)

5 스택추상데이터타입 (ADT) 객체 : n개의 element형의요소들의선형리스트 연산 : create() ::= 스택을생성한다. is_empty(s) ::= 스택이비어있는지를검사한다. is_full(s) ::= 스택이가득찼는가를검사한다. push(s, e) ::= 스택의맨위에요소 e를추가한다. pop(s) ::= 스택의맨위에있는요소를삭제한다. peek(s) ::= 스택의맨위에있는요소를삭제하지않고반환한다.

6 스택의연산 삽입 (push), 삭제 (pop) push(a) push(b) push(c) C pop() B B B A A A A 초기상태

7 스택의연산 is_empty(s): 스택이공백상태인지검사 is_full(s): 스택이포화상태인지검사 create(): 스택을생성 peek(s): 요소를스택에서삭제하지않고보기만하는연산 ( 비교 ) pop 연산- 요소를스택에서삭제하면서가져온다.

8 스택의용도 입력과역순의출력이필요한경우 에디터에서되돌리기 (undo) 기능 함수호출에서복귀주소기억 1 20 int main() { int i=3; sub1(i);... sub2 PC=200 b= int sub1(int a) { int j=5; sub2(j);... void sub2(int b) {... main PC=1 시스템스택 sub1 PC=100 a=3 main PC=20 i=3 시스템스택 sub1 PC=150 a=3 j=5 main PC=20 i=3 시스템스택 sub1 PC=151 a=3 j=5 main PC=20 i=3 시스템스택 main PC=21 i=3 시스템스택

9 배열을이용한스택의구현 1 차원배열 stack[ ] 스택에서가장최근에입력되었던자료를가리키는 top 변수 가장먼저들어온요소는 stack[0] 에, 가장최근에들어온요소는 stack[top] 에저장 스택이공백상태이면 top 은 top top 공백상태 top -1-1 포화상태

10 is_empty, is_full 연산의구현 is_empty(s) is_full(s) if top = -1 then return TRUE else return FALSE if top =(MAX_STACK_SIZE-1) then return TRUE else return FALSE top 공백상태 top -1 포화상태

11 push 연산 push(s, x) if is_full(s) then error "overflow" else top top+1 stack[top] x top top

12 pop 연산 pop(s, x) if is_empty(s) then error "underflow" else e stack[top] top top-1 return e top top

13 C 언어구현 typedef int element; typedef struct { element stack[max_stack_size]; int top; StackType; 배열의요소는 element 타입으로선언 // 스택초기화함수 void init(stacktype *s) { s->top = -1; // 공백상태검출함수 int is_empty(stacktype *s) { return (s->top == -1); // 포화상태검출함수 int is_full(stacktype *s) { return (s->top == (MAX_STACK_SIZE-1)); 관련데이터를구조체로묶어서함수의파라미터로전달

14 구현 // 삽입함수 void push(stacktype *s, element item) { if( is_full(s) ) { fprintf(stderr," 스택포화에러 \n"); return; else s->stack[++(s->top)] = item;

15 구현 // 삭제함수 element pop(stacktype *s) { if( is_empty(s) ) { fprintf(stderr, " 스택공백에러 \n"); exit(1); else return s->stack[(s->top)--];

16 구현 // 피크함수 element peek(stacktype *s) { if( is_empty(s) ) { fprintf(stderr, " 스택공백에러 \n"); exit(1); else return s->stack[s->top];

17 정리 - 스택 (stack) 특징 LIFO 구조 용도 입력과출력이역순인경우 구현 1. 1 차원배열 2. 연결리스트

18 연결된스택 (linked stack) 연결된스택 (linked stack): 연결리스트를이용한스택구현 장점 : 크기가제한되지않음 단점 : 구현이복잡하고삽입이나삭제시간이오래걸린다. 9 top 7 3 NULL

19 연결된스택자료구조 typedef int element; typedef struct StackNode { element item; struct StackNode *link; StackeNode; 요소의타입 노드의타입 typedef struct { StackNode *top; LinkedStackType; 연결된스택의관련데이터 9 top 7 3 NULL

20 연결된스택에서 push 연산 top C B A NULL temp (2) D (1) // 삽입함수 void push(linkedstacktype *s, element item) { StackNode *temp=(stacknode *)malloc(sizeof(stacknode)); if( temp == NULL ){ fprintf(stderr, " 메모리할당에러 \n"); return; else{ temp->item = item; temp->link = s->top; s->top = temp;

21 연결된스택에서 pop 연산 top C B A NULL temp // 삭제함수 element pop(linkedstacktype *s) { if( is_empty(s) ) { fprintf(stderr, " 스택이비어있음 \n"); exit(1); else{ StackNode *temp=s->top; int item = temp->item; s->top = s->top->link; free(temp); return item;

22 #include <stdio.h> #include <malloc.h> typedef int element; typedef struct StackNode{ element item; struct StackNode *link; StackNode ; typedef struct { StackNode *top; LinkedStackType ; void init(linkedstacktype *s) { s->top = NULL; int isempty(linkedstacktype *s) { return (s->top == NULL); int isfull(linkedstacktype *s) { return 0; void push(linkedstacktype *s, element item) { StackNode *temp=(stacknode *)malloc(sizeof(stacknode)); if(temp==null) printf("memory Error \n"); temp->item=item; temp->link=s->top; s->top=temp; (1) (2) element pop(linkedstacktype *s) { //StackNode *temp; if( isempty(s) ) printf("stack is empty\n"); else{ StackNode *temp=s->top; element item = temp->item; s->top = temp->link; //s->top = s->top->link; free(temp); return item;

23 element peek(linkedstacktype *s) { if( isempty(s) ) printf("stack is empty \n"); else return s->top->item; int main() { LinkedStackType s; init(&s); push(&s, 1); push(&s, 2); push(&s, 3); printf("the top item is %d \n", peek(&s)); printf("%d\n", pop(&s)); printf("%d\n", pop(&s)); printf("%d\n", pop(&s)); printf("%d\n", isempty(&s)); return 0;

24 연결된스택구조 연결리스트로구현된스택의장점? 연결리스트로구현된스택에서 top 의의미는?

25

26 스택의응용 (1): 괄호검사 괄호의종류 : 대괄호 ( [, ] ), 중괄호 ( {, ), 소괄호 ( (, ) ) 조건 1. 왼쪽괄호의개수와오른쪽괄호의개수가같아야한다. 2. 같은괄호에서왼쪽괄호는오른쪽괄호보다먼저나와야한다. 3. 괄호사이에는포함관계만존재한다.( 서로다른타입의왼쪽괄호와오른쪽괄호쌍은서로교차하면안된다 ) 잘못된괄호사용의예 (a(b) a(b)c) a{b(c[d]ef)

27 스택의응용 (1): 괄호검사 if( ( i==0 ) && ( j==0 ) 비교 ( ( 비교 ( ( ( ( ( ( ( ( 오류 { A [ (i+1 ) ]=0; 비교 비교 ( [ { 비교 { [ { ( [ [ { { { 성공

28 스택의응용 (1): 괄호검사알고리 알고리즘의개요 즘 문자열에있는괄호를차례대로조사하면서왼쪽괄호를만나면스택에삽입하고, 오른쪽괄호를만나면스택에서괄호를삭제한후오른쪽괄호와짝이맞는지를검사한다. 이때, 스택이비어짝이맞지않으면실패 ( 에러 ) 마지막괄호까지를조사한후에스택에괄호가남아있으면 0( 실패, 에러 ) 이고, 남아있지않으면 1( 참, 성공 ) 을반환한다.

29 스택의응용 (1): 괄호검사알고리 check_matching(expr) 즘 while ( 입력 expr 의끝이아니면 ) ch expr 의다음글자 switch(ch) case '(': case '[': case '{': ch 를스택에삽입 break case ')': case ']': case ']': if ( 스택이비어있으면 ) then 오류 else 스택에서 open_ch 를꺼낸다 if (ch 와 open_ch 가같은짝이아니면 ) then 오류보고 break if( 스택이비어있지않으면 ) then 오류 왼쪽괄호이면스택에삽입 오른쪽괄호이면스택에서삭제비교

30 스택의응용 (2): 수식의계산 수식의표기방법 : 전위 (prefix), 중위 (infix), 후위 (postfix) compiler 중위표기법전위표기법후위표기법 인간 2+3*4 +2*34 234*+ a*b+5 +5*ab ab*5+ (1+2) 컴퓨터에서의수식계산순서 중위표기식 후위표기식 계산 ( 후위표기식의계산 ) 모두스택을사용 (1) 후위표기식 2+3*4 234*+ 14 (2) 후위표기식의계산 * 먼저후위표기식의계산법을알아보자

31 스택의응용 (2): 수식의계산 수식의표현예 예 ) x = a / b - c + d * e - a * c x = ((((a / b) - c) + (d * e)) - (a * c)) 후위표기 : x = a b / c - d e * +a c * - - 괄호사용안함 - 연산자의우선순위없음 (L R 순서의계산 )

32 후위표기식의계산 수식을왼쪽에서오른쪽으로스캔 피연산자이면스택에저장 연산자이면필요한수만큼의피연산자를스택에서꺼내연산실행 연산의결과를다시스택에저장 ( 예 ) 82/3-32*+ 토큰 8 8 스택 [0] [1] [2] [3] [4] [5] [6] / *

33 8 2 / / / 피연산자 -> 삽입피연산자 -> 삽입연산자 -> 8/2=4 삽입 8 2 / / / 피연산자 -> 삽입연산자 -> 4-1=1 삽입종료 -> 전체연산결과 =1

34 후위표기식계산알고리즘 스택 s를생성하고초기화한다. for 항목 in 후위표기식 do if ( 항목이피연산자이면 ) push(s, item) if ( 항목이연산자 op이면 ) then second pop(s) first pop(s) 의하나 result first op second // op 는 +-*/ 중 push(s, result)

35 // 후위표기수식계산함수 eval(char exp[]) { int op1, op2, value, i=0; int len = strlen(exp); char ch; StackType s; init(&s); for( i=0; i<len; i++){ ch = exp[i]; if( ch!= '+' && ch!= '-' && ch!= '*' && ch!= '/' ){ value = ch - '0'; // 입력이피연산자이면 push(&s, value); else{ // 연산자이면피연산자를스택에서제거 op2 = pop(&s); op1 = pop(&s); switch(ch){ // 연산을수행하고스택에저장 case '+': push(&s,op1+op2); break; case '-': push(&s,op1-op2); break; case '*': push(&s,op1*op2); break; case '/': push(&s,op1/op2); break; return pop(&s);

36 중위표기식 후위표기식 Infix ( 중위표기 ) postfix ( 후위표기 ) 2+3* *+ a*b+5 ab*5+ (1+2)* * a*b/c ab*c/ ((a/(b-c+d))*(e-a)*c abc-d+/ea-*c* a/b-c+d*e-a*c ab/c-de*+ac*-

37 중위표기식 후위표기식 중위표기와후위표기 중위표기법과후위표기법의공통점은피연산자의순서는동일 연산자들의순서만다름 ( 우선순위순서 ) 연산자만스택에저장했다가출력하면된다. Ex) 2+3*4 234*+ 알고리즘 외쪽부터스캔하며피연산자를만나면그대로출력 연산자를만나면스택에저장하는데이때스택에있는연산자보다우선순위가낮은연산자를만나면스택의연산자출력 왼쪽괄호는우선순위가가장낮은연산자로취급 오른쪽괄호가나오면스택에서왼쪽괄호위에쌓여있는모든연산자를출력

38 Evaluation of Expressions 연산자우선순위정리 (in C language) token precedence associativity () [] ->. 17 left-to-right left-to-right -- ++! ~ - + & * sizeof 15 right-to-left (type) 14 right-to-left * / % 13 left-to-right left-to-right << >> 11 left-to-right > >= < <= 10 left-to-right ==!= 9 left-to-right & 8 left-to-right ^ 7 left-to-right 6 left-to-right && 5 left-to-right 4 left-to-right?: 3 right-to-left = += -= /= *= %= <<= >>= &= ^= = 2 right-to-left, 1 left-to-right

39 중위표기식 -> 후위표기식 ( a + b ) * c (

40 중위표기식 -> 후위표기식 ( a + b ) * c a (

41 중위표기식 -> 후위표기식 ( a + b ) * c + a (

42 중위표기식 -> 후위표기식 ( a + b ) * c + a b (

43 중위표기식 -> 후위표기식 ( a + b ) * c a b +

44 중위표기식 -> 후위표기식 ( a + b ) * c a b + *

45 중위표기식 -> 후위표기식 ( a + b ) * c a b + c *

46 중위표기식 -> 후위표기식 ( a + b ) * c a b + c *

47 infix_to_postfix(exp) 스택 s 를생성하고초기화 while (exp 에처리할문자가남아있으면 ) ch 다음에처리할문자 switch (ch) case 연산자 : while ( peek(s) 의우선순위 ch 의우선순위 ) do e pop(s) e 를출력 push(s, ch); break; case 왼쪽괄호 : push(s, ch); break; case 오른쪽괄호 : e pop(s); while( e 왼쪽괄호 ) do e 를출력 e pop(s) break; case 피연산자 : ch 를출력 break; while( not is_empty(s) ) do e pop(s) e 를출력

48 Mazing Problem 미로탐색 어디로갈까?

49 미로탐색문제 체계적인방법필요 현재의위치에서가능한방향을스택에저장해놓았다가막다른길을만나면스택에서다음탐색위치를꺼낸다 입구 출구 m x

50 미로탐색문제 미로표현 - 2 차원배열 - element 0 : open path( 길이열려있음 ) - element 1 : barriers( 장벽 ) entrance exit

51

52 미로탐색알고리즘 스택 s 과출구의위치 x, 현재생쥐의위치를초기화 while( 현재의위치가출구가아니면 ) do 성공 ; 현재위치를방문한것으로표기 if( 현재위치의위, 아래, 왼쪽, 오른쪽위치가아직방문되지않았고갈수있으면 ) then 그위치들을스택에 push if( is_empty(s) ) then 실패 else 스택에서하나의위치를꺼내어현재위치로만든다 ;

53 스택복습 스택의특징? 스택의용도? 스택의구현방법비교? 스택의이용 스택예제 괄호검사 수식의계산 미로탐색

54 스택연습 Quiz. 스택을이용하여다음중위수식을후위수식으로변경하고수식값을계산하는과정을그려보시오. 5*(10+2)%2 18. 후위표기식계산프로그램에서다음과같은수식이주어졌을때알고리즘을추적하여스택이내용을그려보시오. a=1, b=2, c=3, d=4, e=5 ab*ca-/de*+

55 스택연습 연결리스트스택에서저장된요소수를반환하는 size 연산 int size(linkedstacktype *s) { StackNode *temp=s->top; int count=0; while(temp!= NULL ) { count++; temp = temp->link; return(count); * 연습코드에연산을첨가하고테스트해보시오.

56 숙제 문자 (char) 를데이터타입으로하는스택 S 가주어져있을때스택내부의문자를순서대로출력하는함수를작성하고테스트해라. 이함수는스택에정의된 push, pop, 등의함수를사용해야하며재귀호출을사용해야한다 G top DOG 출력 1 O 0 D

57 숙제옵션 Chapter 5 project (in Book CD) 1 번, 2 번풀기