Microsoft PowerPoint - 07-chap05-Stack.ppt

Transcription

1 / 스택이란? 스택 stack): 쌓아놓은더미 hapter 5 스택 Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 스택의개념이해 스택의동작원리이해 배열과연결리스트를이용한스택구현 스택응용프로그램 스택의특징 후입선출 LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감. 선입후출 FILO: First-In Last-Out) D

2 / 스택의구조 스택의연산 삽입 push), 삭제 pop) 요소 element) 스택상단 ) push) push) push) pop) 스택하단 bottom) 초기상태 6 스택추상데이터타입 DT) 스택의연산 cnt.) 객체 : n개의 element형의요소들의선형리스트 연산 : create) ::= 스택을생성한다. is_emptys) ::= 스택이비어있는지를검사한다. is_emptys): 스택이공백상태인지검사 is_fulls): 스택이포화상태인지검사 create): 스택을생성 peeks): 요소를스택에서삭제하지않고보기만하는연산 참고 )pop 연산은요소를스택에서완전히삭제하면서가져온다. is_fulls) ::= 스택이가득찼는가를검사한다. pushs, e) ::= 스택의맨위에요소 e 를추가한다. pops) ::= 스택의맨위에있는요소를삭제한다. peeks) ::= 스택의맨위에있는요소를삭제하지않고반환한다. 5 7

3 스택의용도 is_empty, is_full 연산의구현 입력과역순의출력이필요한경우 에디터에서되돌리기 undo) 기능 is_emptys) is_fulls) 함수호출에서복귀주소기억 int main) int i=; subi);... 함수호출에서의스택 if = - then return TRUE else return FLSE if = MX_STK_SIZE-) then return TRUE else return FLSE 5 int subint a) int j=5; subj);... sub P= a= sub P= b=5 sub P=5 a= j=5 sub P=5 a= j=5 void subint b)... main P= 시스템스택 main P= i= 시스템스택 main P= i= 시스템스택 main P= i= 시스템스택 main P= i= 시스템스택 - - 공백상태 포화상태 8 배열을이용한스택의구현 push 연산 차원배열 stack[ ] 스택에서가장최근에입력되었던자료를가리키는 변수 가장먼저들어온요소는 stack[] 에, 가장최근에들어온요소는 stack[] 에저장 스택이공백상태이면 은 - pushs, x) if is_fulls) then error "overflow" else + stack[] x 공백상태 포화상태 9 /

4 / pop 연산 연결된스택 pops, x) if is_emptys) then error "underflow" else e stack[] - return e 연결된스택 linked stack) 연결리스트를이용하여구현한스택 장점 크기가제한되지않음 단점 구현이복잡하고삽입이나삭제시간이오래걸린다 NULL 언어구현 배열의요소는 element 타입으로선언 연결된스택정의 typedef int element; typedef struct element stack[mx_stk_size]; int ; StackType; 관련데이터를구조체로묶어서함수의파라미터로전달 // 스택초기화함수 void initstacktype *s) s-> = -; // 공백상태검출함수 int is_emptystacktype *s) return s-> == -); // 포화상태검출함수 int is_fullstacktype *s) return s-> == MX_STK_SIZE-)); // 삽입함수 void pushstacktype *s, element item) if is_fulls) ) fprintfstderr," 스택포화에러 \n"); return; else s->stack[++s->)] = item; // 삭제함수 element popstacktype *s) if is_emptys) ) fprintfstderr, " 스택공백에러 \n"); exit); else return s->stack[s->)--]; // 피크함수 element peekstacktype *s) if is_emptys) ) fprintfstderr, " 스택공백에러 \n"); exit); else return s->stack[s->]; typedef int element; typedef struct StackNode element item; struct StackNode *link; StackeNode; typedef struct StackNode *; LinkedStackType; 9 7 NULL 요소의타입노드의타입연결된스택의관련데이터 5

5 5 / 연결된스택에서 push 연산 스택응용 : 괄호검사 괄호의종류 : 대괄호 [, ] ), 중괄호, ), 소괄호, ) ) temp ) NULL D ) 조건. 왼쪽괄호의개수와오른쪽괄호의개수가같아야한다.. 같은괄호에서왼쪽괄호는오른쪽괄호보다먼저나와야한다.. 괄호사이에는포함관계만존재한다. // 삽입함수 void pushlinkedstacktype *s, element item) StackNode *temp=stacknode *)mallocsizeofstacknode)); if temp == NULL ) fprintfstderr, " 메모리할당에러 \n"); return; else temp->item = item; temp->link = s->; s-> = temp; 잘못된괄호사용의예 ab) ab)c) abc[d]ef) 6 8 연결된스택에서 pop 연산 스택응용 : 괄호검사 - 주요연산 if i== ) && j== ) NULL 비교 비교 오류 temp // 삭제함수 element poplinkedstacktype *s) if is_emptys) ) fprintfstderr, " 스택이비어있음 \n"); exit); else StackNode *temp=s->; int item = temp->item; s-> = s->->link; freetemp); return item; i+9 ) * j+ ) 비교 비교 비교 성공 7 9

6 스택응용 : 괄호검사 - 알고리즘 수식의계산 알고리즘의개요 수식의표기방법 : 문자열에있는괄호를차례대로조사하면서 왼쪽괄호를만나면스택에삽입하고, 오른쪽괄호를만나면스택에서 괄호를삭제한후 오른쪽괄호와짝이맞는지를검사한다. 이때, 스택이비어있으면조건 또는조건 등을위배하게되고 괄호의짝이맞지않으면조건 등에위배된다. 마지막괄호까지를조사한후여전히스택에괄호가남아있으면 조건 에위배되므로 거짓 ) 을반환하고, 그렇지않으면 참 ) 을반환한다. 전위 prefix), 중위 infix), 후위 postfix) 중위표기법 전위표기법 후위표기법 +* +* *+ a*b+5 +5*ab ab*5+ +) 컴퓨터에서의수식계산순서 중위표기식 후위표기식 계산 +* *+ 모두스택을사용 스택응용 : 괄호검사 - 알고리즘 cnt.) 후위표기식의계산 check_matchingexpr) while 입력 expr 의끝이아니면 ) ch expr 의다음글자 switchch) case '': case '[': case '': ch 를스택에삽입 break case ')': case ']': case ']': if 스택이비어있으면 ) then 오류 else 스택에서 open_ch 를꺼낸다 if ch 와 open_ch 가같은짝이아니면 ) then 오류보고 break if 스택이비어있지않으면 ) then 오류 왼쪽괄호이면스택에삽입 오른쪽괄호이면스택에서삭제비교 수식을왼쪽에서오른쪽으로스캔하여 피연산자이면스택에저장하고 연산자이면필요한수만큼의피연산자를스택에서꺼내연산을실행하고 연산의결과를다시스택에저장 예 ) 8/-*+ 토큰 8 / - [] 8 8 [] [] 스택 [] [] [5] [6] * /

7 7 / 후위표기식의계산 cnt.) 후위표기식계산알고리즘 : 언어 8 / - 8 / - 8 / 피연산자-> 삽입 피연산자-> 삽입 연산자-> 8/= 삽입 8 / - 8 / - 8 / - 피연산자-> 삽입 연산자-> -= 삽입종료-> 전체연산결과 = evalchar exp[]) int op, op, value, i=; int len = strlenexp); char ch; StackType s; init&s); for i=; i<len; i++) ch = exp[i]; if ch!= '+' && ch!= '-' && ch!= '*' && ch!= '/' )// 입력이피연산자이면 value = ch - ''; push&s, value); else // 연산자이면피연산자를스택에서제거 op = pop&s); op = pop&s); switchch) // 연산을수행하고스택에저장 case '+': push&s,op+op); break; case '-': push&s,op-op); break; case '*': push&s,op*op); break; case '/': push&s,op/op); break; return pop&s); 6 후위표기식계산알고리즘 : Pseudo code 중위표기식 후위표기식 스택 s를생성하고초기화한다. for 항목 in 후위표기식 do if 항목이피연산자이면 ) pushs, item) if 항목이연산자 op이면 ) then second pops) first pops) result first op second // op 는 +-*/ 중의하나 pushs, result) final_result pops); 중위표기와후위표기 중위표기법과후위표기법의공통점은피연산자의순서는동일 연산자들의순서만다름 우선순위순서 ) 연산자만스택에저장했다가출력하면된다. +* *+ 알고리즘 피연산자를만나면그대로출력 연산자를만나면스택에저장했다가스택보다우선순위가낮은연산자가나오면그때출력 왼쪽괄호는우선순위가가장낮은연산자로취급 오른쪽괄호가나오면스택에서왼쪽괄호위에쌓여있는모든연산자를출력 5 7

8 8 / 중위표기식 후위표기식 : 변환과정 중위표기식 후위표기식 : 변환과정 cnt.) a + b ) * c a + b ) * c a b + c * a + b ) * c a a + b ) * c a b + c * a + b ) * c a + 8 중위표기식 후위표기식 : 변환과정 cnt.) 중위표기식 후위표기식 : 알고리즘 a + b ) * c a b + a + b ) * c a b + a + b ) * c a b + * infix_to_postfixexp) 스택 s 를생성하고초기화 while exp 에처리할문자가남아있으면 ) ch 다음에처리할문자 switch ch) case 연산자 : while peeks) 의우선순위 ch 의우선순위 ) do e pops) e 를출력 pushs, ch); break; case 왼쪽괄호 : pushs, ch); break; case 오른쪽괄호 : e pops); while e 왼쪽괄호 ) do e 를출력 e pops) break; case 피연산자 : ch 를출력 break; while not is_emptys) ) do e pops) e 를출력 9

9 9 / 미로탐색문제 미로탐색알고리즘 체계적인방법필요 현재의위치에서가능한방향을스택에저장해놓았다가막다른길을만나면스택에서다음탐색위치를꺼낸다. 스택 s과출구의위치 x, 현재생쥐의위치를초기화 while 현재의위치가출구가아니면 ) do 현재위치를방문한것으로표기 if 현재위치의위, 아래, 왼쪽, 오른쪽위치가아직방문되지않았고갈수있으면 ) then 그위치들을스택에 push 입구 if is_emptys) ) then 실패 else 스택에서하나의위치를꺼내어현재위치로만든다 ; 성공 ; 출구 m x < 미로의배열표현 > 요약 스택의정의 스택을위한추상데이터타입 스택의주요연산 스택구현방법 배열을위한스택의구현 링크드리스트를이용한스택의구현 스택의응용 에디터에서되돌리기 undo) 기능 함수호출에서복귀주소기억 계산 중위, 전위, 후위표기법 미로탐색 5

10 / Dongwon Jeong Lab. of Information Sciences & Technology, Department of Informatics & Statistics, Kunsan National Unversity, Gunsan, Korea 6