스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주).

스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주)

자료구조 스택에 대해서 이해한다. 스택의 특징과 연산 방법을 알아본다. 순차 자료구조 방법을 이용한 스택과 연결 자료구조 방법을 이용한 스택을 구현해본다. 스택의 응용 방법을 알아본다.

스택(stack) 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조
스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능 top의 위치에서만 원소를 삽입하므로 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓인다. 마지막에 삽입(Last-In)한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제(First-Out)된다. ☞ 후입선출 구조 (LIFO, Last-In-First-Out) [그림 6-2] 스택의 구조

후입선출 구조의 예1 : 연탄 아궁이 연탄을 하나씩 쌓으면서 아궁이에 넣으므로 마지막에 넣은 3번 연탄이 가장 위에 쌓여 있다. 연탄을 아궁이에서 꺼낼 때에는 위에서부터 하나씩 꺼내야 하므로 마지막에 넣은 3번 연탄을 가장 먼저 꺼내게 된다. [그림 6-3] 스택 자료구조의 예_연탄아궁이

후입선출 구조의 예2 : 슈퍼맨의 옷 갈아입기 수퍼맨이 옷을 벗는 순서 슈퍼맨이 옷을 입는 순서
후입선출 구조의 예2 : 슈퍼맨의 옷 갈아입기 수퍼맨이 옷을 벗는 순서 ①장화 → ②망토 → ③빨간팬츠 → ④파란옷 슈퍼맨이 옷을 입는 순서 ④파란옷 → ③빨간팬츠 → ②망토 → ①장화 [그림 6-4] 스택 자료구조의 예_슈퍼맨 옷 입기

스택의 연산 스택에서의 삽입 연산 : push 스택에서의 삭제 연산 : pop
[그림 6-5] 만원 전철에서의 pop과 push

스택에서의 원소 삽입/삭제 과정 공백 스택에 원소 A, B, C를 순서대로 삽입하고 한번 삭제하는 연산과정 동안의 스택 변화
[그림 6-6] 스택의 자료 삽입ㆍ삭제 과정

스택에 대한 추상 자료형 ADT Stack 데이터 : 0개 이상의 원소를 가진 유한 순서 리스트 연산 :
데이터 : 0개 이상의 원소를 가진 유한 순서 리스트 연산 : Stack ∈ Stack; item ∈ Element; createStack( ) ::= create an empty stack; // 공백 스택을 생성하는 연산 push(Stack, item) ::= insert item onto the top of Stack; // 스택의 top에 item(원소)을 삽입하는 연산 isEmpty(Stack) ::= if (Stack is empty) then return true else return false; // 스택이 공백인지 아닌지를 확인하는 연산 pop(Stack) ::= if (isEmpty(Stack)) then return error else { delete and return the top item of Stack }; // 스택의 top에 있는 item(원소)을 스택에서 삭제하고 반환하는 연산 delete(Stack) ::= if (isEmpty(Stack)) then return error else delete the top item; // 스택의 top에 있는 item(원소)을 삭제하는 연산 peek(Stack) ::= if (isEmpty(Stack)) then return error else return (the top item of the Stack); // 스택의 top에 있는 item(원소)을 반환하는 연산 End Stack

스택의 push 알고리즘 top ← top+1; S(top) ← x; push(S, x) top ← top+1; // ①
스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하려면 먼저 top의 위치를 하나 증가 만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면 오버플로우(overflow)상태가 되므로 삽입 연산을 수행하지 못하고 연산 종료 S(top) ← x; 오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x 삽입 push(S, x) top ← top+1; // ① if (top > stack_SIZE) then overflow; else S(top) ← x; // ② end push( )

스택의 pop 알고리즘 return S(top); top ← top-1; pop(S)
if (top = 0) then error; else { return S(top); // ① top ← top-1; // ② } end pop( )

순차 자료구조를 이용한 스택의 구현 순차 자료구조인 1차원 배열을 이용하여 구현 스택의 크기 : 배열의 크기
스택에 저장된 원소의 순서 : 배열 원소의 인덱스 인덱스 0번 : 스택의 첫번째 원소 인덱스 n-1번 : 스택의 n번째 원소 변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장 공백 상태 : top = -1 (초기값) 포화 상태 : top = n-1 [그림 6-7] 스택에 대한 1차원 배열 표현

크기가 5인 1차원 배열의 스택에서 연산 수행과정 [그림 6-8] 순차 자료구조를 사용한 스택에서의 연산 과정

순차 자료구조를 이용한 스택 프로그램 01 #include <stdio.h> 27 void del( )
02 #include <stdlib.h> 03 #define STACK_SIZE 100 04 05 typedef int element; 06 element stack[STACK_SIZE]; 07 int top= -1; 08 09 void push(element item) 10 { 11 if(top >= STACK_SIZE -1) { 12 printf("\n\n Stack is FULL ! \n"); 13 return; 14 } 15 else stack[++top]=item; 16 } 17 18 element pop( ) 19 { 20 if(top==-1) { 21 printf("\n\n Stack is Empty!!\n"); 22 return 0; 23 } 24 else return stack[top--]; 25 } 26 27 void del( ) 28 { 29 if(top==-1) { 30 printf("\n\n Stack is Empty !\n"); 31 exit(1); 32 } 33 else top--; 34 } 35 36 element peek( ) 37 { 38 if(top==-1){ 39 printf("\n\n Stack is Empty !\n"); 40 exit(1); 41 } 42 else return stack[top]; 43 } 44 45 void printStack( ) 46 { 47 int i; 48 printf("\n STACK [ "); 49 for(i=0; i<=top; i++) 50 printf("%d ",stack[i]); 51 printf("] "); 52 } 53

54 void main(void) 55 { 56 int item; 57 printStack( ); 58 push(1); 59 printStack( ); 60 push(2); 61 printStack( ); 62 push(3); 63 printStack( ); 64 65 item = peek( ); 66 printStack( ); 67 printf("peek top => %d", item); 68 69 del( ); 70 printStack( ); 71 72 item = pop( ); 73 printStack( ); 74 printf("\t pop top => %d", item); 75 76 item = pop( ); 77 printStack( ); 78 printf("\t pop top => %d", item); 79 80 pop( ); 81 82 getchar( ); 83 }

실행 결과 순차 자료구조로 구현한 스택의 장점 순차 자료구조로 구현한 스택의 단점
순차 자료구조인 1차원 배열을 사용하여 쉽게 구현 순차 자료구조로 구현한 스택의 단점 물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경 어려움 순차 자료구조의 단점을 그대로 가지고 있다.

연결 자료구조를 이용한 스택의 구현 단순 연결 리스트를 이용하여 구현 스택의 원소 : 단순 연결 리스트의 노드
스택 원소의 순서 : 노드의 링크 포인터로 연결 push : 리스트의 마지막에 노드 삽입 pop : 리스트의 마지막 노드 삭제 변수 top : 단순 연결 리스트의 마지막 노드를 가리키는 포인터 변수 초기 상태 : top = null [그림 6-9] 스택에 대한 단순 연결 리스트 표현

단순 연결 리스트의 스택에서 연산 수행과정 A, B, C를 순서대로 삽입하면서 스택을 생성한 후에 원소 하나를 삭제하는 과정
① 공백 스택 생성 : create(stack); ③ 원소 B 삽입 : push(stack, B); ⑤원소 삭제 : pop(stack); ② 원소 A 삽입 : push(stack, A); ④ 원소 C 삽입 : push(stack, C); [그림 6-9-1] 연결 자료구조를 사용한 스택에서의 연산 과정

단순 연결 리스트를 이용한 스택 프로그램 001 #include <stdio.h>
002 #include <stdlib.h> 003 #include <string.h> 004 005 typedef int element; 006 007 typedef struct stackNode { 008 element data; 009 struct stackNode *link; 010 }stackNode; 011 012 stackNode* top; 013 014 void push(element item) 015 { 016 stackNode* temp=(stackNode *)malloc(sizeof(stackNode)); 017 temp->data = item; 018 temp->link = top; 019 top = temp; 020 } 021 022 element pop( ) 023 { 024 element item; 025 stackNode* temp=top; 026 027 if(top == NULL) { 028 printf("\n\n Stack is empty !\n"); 029 return 0; 030 } 031 else { 032 item = temp->data; 033 top = temp->link; 034 free(temp); 035 return item; 036 } 037 } 038 039 element peek( ) 040 { 041 element item; 042 if(top == NULL) { 043 printf("\n\n Stack is empty !\n"); 044 return 0; 045 } 046 else { 047 item = top->data; 048 return item; 049 } 050 } 051

052 void del( ) 053 { staackNode*temp; 055 if(top == NULL) { 056 printf("\n\n Stack is empty !\n"); 057 058 } 059 else { 060 temp = top; 061 top = top->link; 062 free(temp); 063 } 064 } 065 066 void printStack( ) 067 { 068 stackNode* p=top; 069 printf("\n STACK [ "); 070 while(p){ 071 printf("%d ",p->data); 072 p = p->link; 073 } 074 printf("] "); 075 } 076 077 void main(void) 078 { 079 element item; 080 top = NULL; 081 printStack( ); 082 push(1);

실행 결과

역순 문자열 만들기 스택의 후입선출(LIFO) 성질을 이용 문자열을 순서대로 스택에 push 하기
[그림 6-10] 역순 문자열 만들기_① 순서대로 스택에 삽입하기

스택을 pop하여 문자열로 저장하기 [그림 6-11] 역순 문자열 만들기_② 스택에서 삭제하여 문자열 만들기

시스템 스택 프로그램에서의 호출과 복귀에 따른 수행 순서를 관리
가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 후입선출 구조의 스택을 이용하여 수행순서 관리 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임(stack frame)에 저장하여 시스템 스택에 삽입 함수의 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장되어있던 복귀주소를 확인하고 복귀 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

함수 호출과 복귀에 따른 전체 프로그램의 수행 순서
[그림 6-12] 함수 호출과 복귀에 따른 전체 프로그램 수행 순서

프로그램이 실행을 시작하여 main( ) 함수가 실행되면서 main( ) 함수에 관련된 정보를 스택 프레임에 저장하여 시스템 스택에 삽입
main( ) 함수 실행 중에 F_1( ) 함수 호출을 만나면 함수 호출과 복귀에 필요한 정보를 스택 프레임에 저장하여 시스템 스택에 삽입하고, 호출된 함수인 F_1( ) 함수로 이동 스택 프레임에는 호출된 함수의 수행이 끝나고 main( ) 함수로 복귀할 주소 a를 저장 [그림 6-13] main( ) 함수 실행 시작 [그림 6-14] F_1( ) 함수 호출

시스템 스택의 top에 있는 스택 프레임을 pop하여 정보를 확인하고, F_1( ) 함수의 b주소로 복귀
F_1( ) 함수 실행 중에 F_2( ) 함수 호출을 만나면 다시 함수 호출과 복귀에 필요한 정보를 스택 프레임에 저장하여 시스템 스택에 삽입. 호출된 함수인 F_2( ) 함수를 실행 스택 프레임에는 F_1( ) 함수로 복귀할 주소 b를 저장 호출된 함수 F_2( ) 함수를 실행 완료 시스템 스택의 top에 있는 스택 프레임을 pop하여 정보를 확인하고, F_1( ) 함수의 b주소로 복귀 [그림 6-15] F_2( ) 함수 호출 [그림 6-16] F_1( ) 함수로 복귀

복귀된 함수 F_1( ) 함수의 b주소 이후 부분을 실행
시스템 스택의 top에 있는 스택 프레임을 pop하여 정보를 확인하고 main( ) 함수의 a주소로 복귀 복귀된 main( ) 함수의 a주소 이후 부분에 대한 실행이 완료되면 시스템 스택의 top에 있는 스택 프레임을 pop하는데, 시스템 스택이 공백이 되었으므로 전체 프로그램 실행 종료 [그림 6-17] main( ) 함수로 복귀 [그림 6-18] main( ) 함수 실행 종료

수식의 괄호 검사 수식에 포함되어있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 후입선출 구조로 구성되어있으므로, 후입선출 구조의 스택을 이용하여 괄호를 검사한다. 수식을 왼쪽에서 오른쪽으로 하나씩 읽으면서 괄호 검사 왼쪽 괄호를 만나면 스택에 push 오른쪽 괄호를 만나면 스택을 pop하여 마지막에 저장한 괄호와 같은 종류인지를 확인 같은 종류의 괄호가 아닌 경우 괄호의 짝이 잘못 사용된 수식! 수식에 대한 검사가 모두 끝났을 때 스택은 공백 스택 수식이 끝났어도 스택이 공백이 되지 않으면 괄호의 개수가 틀린 수식!

수식의 괄호 검사 알고리즘 testPair( ) exp ← Expression; Stack ← null;
while (true) do{ symbol ← getSymbol(exp); case { symbol = "(" or "[" or "{" : push(Stack, symbol); symbol = ")" : open_pair ← pop(Stack); if (open_pair ≠ "(") then return false; symbol = "]" : if (open_pair ≠ "[") then return false; symbol = "}" : if (open_pair ≠ "{") then return false; symbol = null : if (isEmpty(Stack)) then return true; else return false; else : } } end testPair( )

수식의 괄호 검사 예 ① ②

③ ④

⑤ ⑥ ⑦ [그림 6-19] 수식 처리에 따른 스택 사용 과정

수식의 괄호 검사 C 프로그램 001 #include <stdio.h>
002 #include <stdlib.h> 003 #include <string.h> 004 005 typedef char element; 006 007 typedef struct stackNode { 008 element data; 009 struct stackNode *link; 010 }stackNode; 011 012 stackNode* top; 013 014 void push(element item) 015 { 016 stackNode* temp=(stackNode *)malloc(sizeof(stackNode)); 017 temp->data = item; 018 temp->link = top; 019 top = temp; 020 } 021 022 element pop( ) 023 { 024 element item; 025 stackNode* temp=top; 026 027 if(top == NULL) { 028 printf("\n\n Stack is empty !\n"); 029 return 0; 030 } 031 else { 032 item = temp->data; 033 top = temp->link; 034 free(temp); 035 return item; 036 } 037 } 038 039 element peek( ) 040 { 041 element item; 042 if(top == NULL) { 043 printf("\n\n Stack is empty !\n"); 044 return 0; 045 } 046 else { 047 item = top->data; 048 return item; 049 } 050 } 051 052 void del( ) 053 { 054 stackNode* temp;

055 if(top == NULL) { 056 printf("\n\n Stack is empty !\n"); 057 058 } 059 else { 060 temp = top; 061 top = top->link; 062 free(temp); 063 } 064 } 065 066 void printStack( ) 067 { 068 stackNode* p=top; 069 printf("\n STACK [ "); 070 while(p){ 071 printf("%d ",p->data); 072 p = p->link; 073 } 074 printf("] "); 075 } 076 077 int testPair(char *exp) 078 { 079 char symbol, open_pair; 080 int i, length=strlen(exp); 081 top=NULL; 082 083 for(i=0; i<length; i++){ 084 symbol = exp[i]; 085 switch(symbol){ 086 case '(' : 087 case '[' : 088 case '{' : 089 push(symbol); break; 090 case ')' : 091 case ']' : 092 case '}' : 093 if(top==NULL) return 0; 094 else { 095 open_pair = pop( ); 096 if( (open_pair=='(' && symbol != ')') || 097 (open_pair=='[' && symbol != ']') || 098 (open_pair=='{' && symbol != '}')) 099 return 0; 100 else break; 101 } 102 } 103 } 104 if(top==NULL) return 1; 105 else return 0; 106 } 107

실행 결과 108 109 void main(void) 110 { 111 char* express = "{(A+B)-3}*5+[{cos(x+y)+7}-1]*4"; 112 printf("%s", express); 113 if(testPair(express) == 1) 114 printf("\n\n 수식의 괄호가 맞게 사용되었습니다!"); 115 else 116 printf("\n\n 수식의 괄호가 틀렸습니다!"); 117 118 getchar( ); 119 }

수식의 후위 표기법 변환 전위표기법(prefix notation) 중위표기법(infix notation)
연산자를 앞에 표기하고 그 뒤에 피연산자를 표기하는 방법 예) +AB 중위표기법(infix notation) 연산자를 피연산자의 가운데 표기하는 방법 예) A+B 후위표기법(postfix notation) 연산자를 피연산자 뒤에 표기하는 방법 예) AB+

중위표기식의 전위표기식 변환 방법 ① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
예) A*B-C/D 1단계: ( (A*B) - (C/D) ) 2단계: ⇒ -(*(A B) /(C D)) 3단계 -*AB/CD ① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다. ② 각 연산자를 그에 대응하는 왼쪽괄호의 앞으로 이동시킨다. ③ 괄호를 제거한다.

중위표기식의 후위표기식 변환 방법 ① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
예) A*B-C/D 1단계: ( (A*B) - (C/D) ) 2단계: ⇒ ( (A B)* (C D)/ )- 3단계: AB*CD/- ① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다. ② 각 연산자를 그에 대응하는 오른쪽괄호의 뒤로 이동시킨다. ③ 괄호를 제거한다.

스택을 사용하여 입력된 중위표기식을 후위표기식으로 변환
변환 방법 ⑴ 왼쪽괄호를 만나면 무시하고 다음 문자를 읽는다. ⑵ 피연산자를 만나면 출력한다. ⑶ 연산자를 만나면 스택에 push한다. ⑷ 오른쪽괄호를 만나면 스택을 pop하여 출력한다. ⑸ 수식이 끝나면, 스택이 공백이 될 때까지 pop하여 출력한다.

예) ((A*B)-(C/D)) [그림 6-20] 스택을 사용한 후위 표기식 변환 과정

후위표기법 변환 알고리즘 infix_to_postfix(exp) while (true) do {
symbol ← getSymbol(exp); case { symbol = operand : // 피연산자 처리 print(symbol); symbol = operator : // 연산자 처리 push(stack, symbol); symbol = ")" : // 오른쪽괄호 처리 print(pop(Stack)); symbol = null : // 수식의 끝 처리 while (top > -1) do else : } end infix_to_postfix( )

스택을 사용하여 후위표기식을 연산 연산 방법 ⑴ 피연산자를 만나면 스택에 push 한다.
수식이 끝나고 스택에 마지막으로 남아있는 원소는 전체 수식의 연산결과 값이 된다. ⑴ 피연산자를 만나면 스택에 push 한다. ⑵ 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push 한다. ⑶ 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.

후위표기식의 연산 알고리즘 evalPostfix(exp) while (true) do {
symbol ← getSymbol(exp); case { symbol = operand : // 피연산자 처리 push(stack, symbol); symbol = operator : // 연산자 처리 opr2 ← pop(stack)); opr1 ← pop(stack)); result ← opr1 op(symbol) opr2; // 스택에서 꺼낸 피연산자들을 연산자로 연산 push(stack, result); symbol = null : // 후위수식의 끝 print(pop(stack)); } } end evalPostfix( )

예) AB*CD/-

예) AB*CD/- [그림 6-21] 스택을 사용한 후위 표기식 연산 과정

후위표기식의 연산 C 프로그램 001 #include <stdio.h>
002 #include <stdlib.h> 003 #include <string.h> 004 005 typedef int element; 006 007 typedef struct stackNode { 008 element data; 009 struct stackNode *link; 010 }stackNode; 011 012 stackNode* top; 013 014 void push(element item) 015 { 016 stackNode* temp=(stackNode *)malloc(sizeof(stackNode)); 017 temp->data = item; 018 temp->link = top; 019 top = temp; 020 } 021 022 element pop( ) 023 { 024 element item; 025 stackNode* temp=top; 026 027 if(top == NULL) { 028 printf("\n\n Stack is empty !\n"); 029 return 0; 030 } 031 else { 032 item = temp->data; 033 top = temp->link; 034 free(temp); 035 return item; 036 } 037 } 038 039 element peek( ) 040 { 041 element item; 042 if(top == NULL) { 043 printf("\n\n Stack is empty !\n"); 044 return 0; 045 } 046 else { 047 item = top->data; 048 return item; 049 } 050 } 051 052 void del( ) 053 { 054 stackNode* temp;

055 if(top == NULL) { 056 printf("\n\n Stack is empty !\n"); 057 058 } 059 else { 060 temp = top; 061 top = top->link; 062 free(temp); 063 } 064 } 065 066 void printStack( ) 067 { 068 stackNode* p=top; 069 printf("\n STACK [ "); 070 while(p){ 071 printf("%d ",p->data); 072 p = p->link; 073 } 074 printf("] "); 075 } 076 077 element evalPostfix(char *exp) 078 { 079 int opr1, opr2, value, i=0; 080 int length = strlen(exp); 081 char symbol; 082 top = NULL; 083 084 for(i=0; i<length; i++){ 085 symbol = exp[i]; 086 if(symbol != '+' && symbol != '-' && symbol != '*' && symbol != '/'){ 087 value = symbol - '0'; 088 push(value); 089 } 090 else{ 091 opr2 = pop( ); 092 opr1 = pop( ); 093 switch(symbol){ 094 case '+' : push(opr1 + opr2); break; 095 case '-' : push(opr1 - opr2); break; 096 case '*' : push(opr1 * opr2); break; 097 case '/' : push(opr1 / opr2); break; 098 } 099 } 100 } 101 return pop( ); 102 } 103 104 void main(void) 105 { 106 int result; 107 char* express = "35*62/-"; 108 printf("후위표기식 : %s", express); 109

실행 결과 110 result = evalPostfix(express);
111 printf("\n\n 연산결과 => %d", result); 112 113 getchar( ); 114 }

스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주).

Similar presentations

Presentation on theme: "스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주)."— Presentation transcript:

Similar presentations

About project

지원

로그인

Auth with social network:

스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주).

Similar presentations

Presentation on theme: "스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주)."— Presentation transcript:

Similar presentations

About project

지원