슬라이드 1

Transcription

1 CHAP 5 : 스택 yicho@gachon.ac.kr 1

2 5.1 스택추상데이터타입 스택 (stack) 이란?: 쌓아놓은더미 2

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

4 스택의구조 요소 (element) 스택에저장되는것 C 스택상단 (top) : 스택에서입출력이이루어지는부분 B A 스택하단 (bottom) : 스택의반대쪽바닥부분 공백스택 (empty stack) : 스택에요소가하나도없을때의스택을말함 4

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

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

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

8 스택의용도 입력과역순의출력이필요한경우 에디터에서되돌리기 (undo) 기능 함수호출에서복귀주소기억 int main() { int i=3; sub1(i);... 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 sub2 PC=200 b=5 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 시스템스택 시스템스택 시스템스택 시스템스택 시스템스택 8

9 5.2 배열로구현한스택 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 배열인덱스가 0 부터시작하기때문에 MAX_STACK_SIZE-1 을비교해야함 top 공백상태 top -1 포화상태

11 push 연산 스택에새로운요소를삽입하기전에스택이가득차지않았나를검사하는연산 push(s, x) if is_full(s) then error "overflow" else top top+1 stack[top] x top top 11

12 pop 연산 스택에서하나의요소를제거하는연산으로, top 이가리키는요소를거내서외부로건네주는연산 pop(s, x) if is_empty(s) then error "underflow" else e stack[top] top top-1 return e top top 12

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)); 관련데이터를구조체로묶어서함수의파라미터로전달 13

14 14 // 삽입함수 void push(stacktype *s, element item) { if( is_full(s) ) { fprintf(stderr," 스택포화에러 \n"); return; else s->stack[++(s->top)] = item; // 삭제함수 element pop(stacktype *s) { if( is_empty(s) ) { fprintf(stderr, " 스택공백에러 \n"); exit(1); else return s->stack[(s->top)--]; // 피크함수 element peek(stacktype *s) { if( is_empty(s) ) { fprintf(stderr, " 스택공백에러 \n"); exit(1); else return s->stack[s->top];

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

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

17 연결된스택에서 push 연산 top C B A NULL temp (2) D (1) 17 // 삽입함수 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;

18 연결된스택에서 pop 연산 top C B A NULL temp 18 // 삭제함수 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;

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

20 스택을이용한괄호검사 if( ( i==0 ) && (j==0 ) 비교 ( ( 비교 오류 ( ( ( ( ( ( ( ( { A [ (i+1 ) ]=0; 비교 비교 ( [ { 비교성공 { [ { ( [ [ { { { 20

21 알고리즘 알고리즘의개요 문자열에있는괄호를차례대로조사하면서왼쪽괄호를만나면스택에삽입하고, 오른쪽괄호를만나면스택에서 top 괄호를삭제한후오른쪽괄호와짝이맞는지를검사한다. 이때, 스택이비어있으면조건 1 또는조건 2 등을위배하게되고괄호의짝이맞지않으면조건 3 등에위배된다. 마지막괄호까지를조사한후에도스택에괄호가남아있으면조건 1 에위배되므로 0( 거짓 ) 을반환하고, 그렇지않으면 1( 참 ) 을반환한다. 21

22 괄호검사알고리즘 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 오류 왼쪽괄호이면스택에삽입 오른쪽괄호이면스택에서삭제비교 22

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

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

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

26 후위표기식계산알고리즘 스택 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) final_result pop(s); 26

27 // 후위표기수식계산함수 eval(char exp[]) { int op1, op2, value, i=0; int len = strlen(exp); char ch; StackType s; 27 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);

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

29 ( a + b ) * c ( 29

30 ( a + b ) * c a ( 30

31 ( a + b ) * c + a ( 31

32 ( a + b ) * c + a b ( 32

33 33 ( a + b ) * c a b +

34 ( a + b ) * c a b + * 34

35 ( a + b ) * c a b + c * 35

36 36 ( a + b ) * c a b + c *

37 infix_to_postfix(exp) 37 스택 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 를출력

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

39 39

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