Chapter 06. 스택.

Presentation on theme: "Chapter 06. 스택."— Presentation transcript:

1 chapter 06. 스택

2 학습 목표 스택 개념 이해 스택의 연산 스택의 구현 스택의 응용 순차 자료구조 방법을 이용한 구현
연결 자료구조 방법을 이용한 구현 스택의 응용

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

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

5 스택 스택의 연산 스택에서의 삽입 연산 : push 스택에서의 삭제 연산 : pop

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

7 추상자료형 스택 스택에 대한 추상 자료형 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

8 추상자료형 스택 스택의 push 알고리즘 top ← top+1; S(top) ← x; push(S, x)
스택 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()

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

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

11 스택의 구현 크기가 5인 1차원 배열의 스택에서 [그림 6-6]의 연산 수행과정

12 스택의 구현 – 프로그램(1) 순차 자료구조를 이용한 스택 프로그램 01 #include <stdio.h>
스택의 구현 – 프로그램(1) 순차 자료구조를 이용한 스택 프로그램 01  #include <stdio.h> 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 >> 계속

13 스택의 구현 – 프로그램(2) 27 void del() 28 { 29 if(top==-1) {
스택의 구현 – 프로그램(2) 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  >> 계속

14 스택의 구현 – 프로그램(3) 54 void main(void) 55 { 56 int item; 57 printStack();
스택의 구현 – 프로그램(3) 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  }

15 스택의 구현 – 프로그램 실행 결과 실행 결과 >

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

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

18 스택의 구현 단순 연결 리스트의 스택에서 [그림6-6]의 연산 수행과정 공백 스택 생성 : create(stack);
원소 A 삽입 : push(stack, A); 원소 B 삽입 : push(stack, B);

19 스택의 구현 원소 C 삽입 : push(stack, C); 원소 삭제 : pop(stack);

20 스택의 구현 – 프로그램(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  >> 계속

21 스택의 구현 – 프로그램(2) 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; >> 계속

22 스택의 구현 – 프로그램(3) 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); >> 계속

23 스택의 구현 – 프로그램(4) 083 printStack(); 084 push(2); 085 printStack();
088  089      item = peek(); 090      printStack(); 091      printf("peek top => %d", item); 092  093      del(); 094      printStack(); 095  096      item = pop(); 097      printStack(); 098      printf("\t pop top => %d", item); 099      100      item = pop(); 101      printStack(); 102      printf("\t pop top => %d", item); 103      104      pop(); 105       106      getchar(); 107  }

24 스택의 구현 – 프로그램 실행 결과 실행 결과 >

25 스택의 응용 – (1) 역순 문자열 만들기 역순 문자열 만들기 스택의 후입선출(LIFO) 성질을 이용
문자열을 순서대로 스택에 push 하기

26 스택의 응용 – (1) 역순 문자열 만들기 스택을 pop하여 문자열로 저장하기

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

28 스택의 응용 – (2) 시스템 스택 함수 호출과 복귀에 따른 전체 프로그램의 수행 순서

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

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

31 스택의 응용 – (2) 시스템 스택 복귀된 함수 F_1() 함수의 b주소 이후 부분을 실행
시스템 스택의 top에 있는 스택 프레임을 pop하여 정보를 확인하고 main() 함수의 a주소로 복귀 복귀된 main() 함수의 a주소 이후 부분에 대한 실행이 완료되면 시스템 스택의 top에 있는 스택 프레임을 pop하는데, 시스템 스택이 공백이 되 었으므로 전체 프로그램 실행 종료 스택 프레임 삭제 top=null stack_Frame(main) main( ) 함수 실행 관련 정보

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

33 스택의 응용 – (3) 수식의 괄호 검사 수식의 괄호 검사 알고리즘 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() 

34 스택의 응용 – (3) 수식의 괄호 검사 수식의 괄호 검사 예
검사할 수식 : {(A+B)-3}*5+[{cos(x+y)+7}-1]*4 >> 계속

35 스택의 응용 – (3) 수식의 괄호 검사 >> 계속

36 스택의 응용 – (3) 수식의 괄호 검사

37 스택의 응용 – (3) 수식의 괄호 검사 -프로그램
수식의 괄호 검사 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  >> 계속

38 스택의 응용 – (3) 수식의 괄호 검사 -프로그램
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; >> 계속

39 스택의 응용 – (3) 수식의 괄호 검사 -프로그램
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  >> 계속

40 스택의 응용 – (3) 수식의 괄호 검사 -프로그램
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 >> 계속

41 스택의 응용 – (3) 수식의 괄호 검사 -프로그램
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  }

42 스택의 응용 – (3) 수식의 괄호 검사 –프로그램 실행결과
실행 결과 >

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

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

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

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

47 스택의 응용 – (4) 수식의 후위표기법 변환 예) ((A*B)-(C/D))

48 스택의 응용 – (4) 수식의 후위표기법 변환 후위표기법 변환 알고리즘 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()

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

50 스택의 응용 – (5) 후위표기수식의 연산 후위표기식의 연산 알고리즘 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()

51 스택의 응용 – (5) 후위표기수식의 연산 예) AB*CD/-

52 스택의 응용 – (5) 후위표기수식의 연산

53 스택의 응용 – (5) 후위표기수식의 연산 - 프로그램
후위표기식의 연산 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  >> 계속

54 스택의 응용 – (5) 후위표기수식의 연산 - 프로그램
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; >> 계속

55 스택의 응용 – (5) 후위표기수식의 연산 - 프로그램
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; >> 계속

56 스택의 응용 – (5) 후위표기수식의 연산 - 프로그램
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 >> 계속

57 스택의 응용 – (5) 후위표기수식의 연산 - 프로그램
110      result = evalPostfix(express); 111      printf("\n\n 연산결과 => %d", result); 112       113      getchar(); 114  }

58 스택의 응용 – (5) 후위표기수식의 연산 – 프로그램 실행결과
실행 결과 >