제 5 장. 스택(Stack).

Presentation on theme: "제 5 장. 스택(Stack)."— Presentation transcript:

1 제 5 장. 스택(Stack)

2 5.1 스택(Stack)의 개념

3 5.1 스택(Stack)의 개념 ￭ 스택(stack) 모든 자료의 삽입과 삭제가 선형 리스트의 한쪽 끝(top)에서만
이루어지는 특별한 자료 구조 Pushdown 리스트 혹은 후입 선출 구조(LIFO-Last In-First Out)라 한다. <스택의 구조>

4 5.1.1 스택의 동작 과정(1/4) ￭ 스택의 변화 과정

5 5.1.1 스택의 동작 과정(2/4) ￭ 스택의 변화 과정 ※ top
스택 포인터(stack pointer)라 하며, 스택에서 top의 위치는 삽입, 삭제 조작에 따라 유동적으로 변화한다. 스택 포인터가 가리키는 곳이 가장 최근에 삽입된 자료 (삭제-출력)를 가리키고 있기 때문이다. ※ bottom 스택 포인터는 bottom에서 시작하여 항목이 삽입 되면 하나 증가하고, 삭제되면 하나 감소한다. 미리 정해 놓은 크기에 따라서 삽입할 수 있는 한계가 있어, 그 한계를 초과하여 삽입할 수 없다.

6 5.1.1 스택의 동작 과정(3/4) ￭ 스택의 응용 ※ 응용의 예
- 호출과 피호출 함수의 실행 제어, 모든 순환적인 알고리즘이 실행될 때 시스템에서 내부적으로 순환호출(recursive call)되는 과정을 제어 - 인터럽트 처리 과정에 대한 제어, 산술식을 컴파일러가 평가하 는 과정, 트리 운행 알고리즘, 깊이 우선 탐색 알고리즘, 퀵 정 렬 알고리즘 등에 사용된다

7 5.1.1 스택의 동작 과정(4/4) ￭ 스택의 응용(호출과 피호출 함수의 실행순서)

8 5.1.2 스택의 자료 처리(1/9) ￭ 스택의 자료 처리 함수 ￭ 배열을 사용한 스택 생성
※ create() : 새로운 공백 스택을 정의하고 top을 초기화 ※ push() : push(data) 스택에 자료를 삽입 ※ pop() : 스택에서 top이 가리키는 자료를 보환 후 삭제(또는 출력) ※ top_exam() : 스택의 top이 가르키는 자료의 내용을 조사 ※ isempty() : 스택에서 삭제(출력) 전에 스택의 공백 유무를 조사 ￭ 배열을 사용한 스택 생성 1. #define SIZE 50 2. static char stack[SIZE];/* 크기가 50인 배열 stack을 선언 */ 3. int top = 1;/* 스택 포인터 top을 초기화 */

9 5.1.2 스택의 자료 처리(2/9) ￭ 스택의 삽입(push()) 모듈 1. void push(char data) {
2. top++; 3. if(overflow()) 4. { 5. printf("%s", "stack overflows."); 6. exit(1); 7. } 8. else 9. stack[top] = data; 10. }

10 5.1.2 스택의 자료 처리(3/9) ￭ 스택의 삭제(출력-pop()) 모듈 1. void pop() {
2. char temp; 3. if(isempty()) { 4. printf("%s", "stack empty."); 5. exit(1); 6. } 7. else { 8. temp = stack[top]; 9. top--; 10. return(temp); 11. } 12. }

11 5.1.2 스택의 자료 처리(4/9) ￭ isempty()함수 – 스택에 자료가 있는지 조사하는 모듈
1. int isempty() { 2. if(top < 0) return(1); 3. else return (0); 4. } ￭ 스택의 overflow() 모듈 1. int overflow() { 2. if(top >= SIZE) return (1); 3. else return(0);

12 5.1.2 스택의 자료 처리(5/9) ￭ 연결 리스트를 이용한 스택의 구현
※ 스택의 크기를 사전에 알 수 없는 프로그램에서 효율적임 <“APPLE”를 연결리스트에 삽인한 예>

13 5.1.2 스택의 자료 처리(6/9) ￭ 연결형 스택 초기화 알고리즘
1. typedef struct stack_node stack_node; 2. struct stack_node { 3. char data; 4. stack_node *link; 5. }; 6. stack_node *top = NULL; // 초기 연결 링크는 top으로 null이 저장된다. <연결 스택의 초기 상태>

14 5.1.2 스택의 자료 처리(7/9) ￭ 연결형 스택 삽입(push()) 알고리즘
1. void push(char data) { 2. struct stack_node { 3. char data; 4. stack_node *link; 5. } *new; 6. new = malloc(sizeof(stack_node)); 7. if(new == NULL) { 8. printf("memory allocation error\n"); 9. exit(1); 10. } 11. else { 12. new->data = data; 13. new->link = top; 14. top = new; 15. } 16. }

15 5.1.2 스택의 자료 처리(8/9) ￭ 연결형 스택 삽입(push()) 알고리즘 실행 예

16 5.1.2 스택의 자료 처리(9/9) ￭ 연결형 스택 삭제(pop()) 알고리즘 1. char pop() 2. {
3. struct stack_node { 4. char data; 5. stack_node *link; 6. } *ptr; 7. char temp; 8. if(isempty()) { 9. printf("%s", "stack empty."); 10. exit(1); 11. } 12. else { 13. temp = top->data; 14. ptr = top; 15. top = top->link; 16. free(ptr); 17. return(temp); 18. } 19. }

17 5.2 다중 배열 스택

18 5.2 다중 배열 스택(1/5) ￭ 다중 배열 스택 다중 배열 스택은 하나의 배열에 두 개 이상의 스택을 운영하는 경우
로 스택 공간의 효율적 사용, 오버플로우 현상 감소 등이 장점이다. ※ 다중 배역 스택의 삽입 조작 첫 번째 스택은 stack[n] 방향으로 top-1을 증가 두 번째 스택은 stack[0] 방향으로 top-2을 감소 ※ 다중 배열 스택의 삭제 조작 첫 번째 스택은 stack[0] 방향으로 top-1을 감소 두 번째 스택은 stack[n] 방향으로 top-2를 증가

19 5.2 다중 배열 스택(2/5) ￭ 1차원 배열에 두 개의 스택을 운영하는 예 ※ bottom과 top의 관계
bottom[m+1] = top[i] = n/m(i-1), bottom[m+1] = n (단, 1≤i<m) bottom[m+1] = n의 초기화는 m번째 스택의 오버플로우를 검사하기 위하여 사용 i번째 스택의 공백 상태는 bottom[i] == top[i]의 관계를 갖고 있으며, i번째 스택의 오버플로우 상태는 top[i] == bottom[i+1]의 관계를 갖는다.

20 5.2 다중 배열 스택(3/5) ￭ 1차원 배열에 m개의 스택을 운영하기 위하여 초기화한 예
※ 다중 배역 스택 삽입 모듈은 top[i] == bottom[i+1]를 확인하여 자료의 삽입이 가능한 상태인지를 확인하는 것으로 시작된다. 1. void m_push(int i, char data) 2. { 3. if(top[i] == bottom[i+1]) 4. overflow(i); 5. else { 6. stack[top[i]] = data; 7. top[i] = top[i] + 1; 8. } 9. }

21 5.2 다중 배열 스택(4/5) ※ 다중 배역 스택의 삭제(pop()) 모듈
top[i] == bottom[i]의 여부를 체크하여 스택의 자료 유무 상태를 먼저 확인 1. char m_pop(int i) 2. { 3. char temp; 4. if(top[i] == bottom[i]) { 5. printf("%s", stack empty."); 6. exit(1); 7. } 8. else { 9. temp = stack[top[i]]; 10. top[i] = top[i] - 1; 11. return(temp); 12. } 13. }

22 5.2 다중 배열 스택(5/5) ￭ 다중 스택에서 오버플로우를 해결하는 과정에 대한 예
※ 다중 배역 스택의 오버플로우 해결방안 배열을 여러 개의 스택으로 분할하여 모든 스택이 전부 오버플로우 상태가 아닌 경우를 양방향으로 찾아 해결한다.

23 5.3 다중 연결 스택

24 5.3 다중 연결 스택(1/4) ￭ 다중 연결 스택 ￭ 다중 연결 스택의 구현 ※ 다중 배열 스택의 문제점
재포장(repacking)의 문제로 오버플로우를 해결하기 위해 스택의 많은 요소들이 이동해서 재배열 되어야 함 이 문제점을 해결하기 위한 방안으로 다중 연결 스택을 이용한다. ￭ 다중 연결 스택의 구현 - 노드를 선언하고 초기화한다. - n개의 top 포인터가 저장되는 배열 top 선언하고, - 다음으로 n개의 공백 스택으로 포인터 배열 top[]을 초기화한다.

25 5.3 다중 연결 스택(2/4) ※ n개의 연결 스택에 대한 초기화 1. struct stack_node {
2. char data; 3. stack_node *link; 4. } 5. stack_node *top[n];

26 5.3 다중 연결 스택(3/4) ※ 다중 연결 스택의 삽입 모듈
1. void multi_push(int I, char data) 2. { 3. struct stack_node { 4. char data; 5. stack_node *link; 6. } *new; 7. new = malloc(sizeof(stack_node)); 8. if(new == NULL) { 9. printf("memory allocation error\n"); 10. exit(1); 11. } 12. else { 13. new->data = data; 14. new->link = top[i]; 15. top[i] = new; 16. } 17. }

27 5.3 다중 연결 스택(4/4) ※ 다중 연결 스택의 삭제 모듈 1. char multi_pop(int i) 2. {
3. struct stack_node { 4. char data; 5. stack_node *link; 6. } *ptr; 7. char temp; 8. if(top[i] == NULL) { 9. printf("%s", stack empty."); 10. exit(1); 11. } 12. else { 13. temp = top[i]->data; 14. ptr = top[i]; 15. top[i] = top[i]->link; 16. free(ptr); 17. return(temp); 18. } 19. }

28 5.4 스택의 응용 예 – 산술식 계산

29 5.4 스택의 응용 예(1/4) ￭ 컴퓨터 프로그램을 이용한 스택의 구현 예 ※ 산술식 계산의 종류
- 전위표기 (pre-fix) - 중위표기 (in-fix) - 후위표기 (post-fix) ※ 중위 표기 - 두 개의 피연산자(operand)사이에 연산자를 기술하는 표기 방법 - 실제 자료가 저장되는 피연산자 스택과 연산자 스택 두 개를 사용 - 우선순위를 판단하여 조작하거나 다른 연산자가 존재하지 않을 경 우에는 그대로 삽입하는 것을 기본으로 한다. 이러한 방법을 스택이 모두 공백 상태가 될 때까지 반복한다.

30 5.4 스택의 응용 예(2/4) ※ 연산자 우선순위 판단 기준
- ISP(In Stack Priority) : 연산지 스택의 top에 저장된 연산자 우선순위 - ICP(In Coming Priority) : 새로운 연산자가 연산자 스택에 들어 올 경 우의 연산자 우선순위 ※ ISP < ICP - 새로운 연산자를 연산자 스택에 삽입(push) ※ ISP >= ICP - 연산자 스택에서 출력(pop)한 연산자와 피 연산자 스택에서 두번 pop하여 계산을 수행 - 한 후 계산된 결과를 피연산자 스택에 push하여 다시 ISP와 Icp를 비교하는 과정을 반복적으로 수행

31 5.4 스택의 응용 예(3/4) ￭ 산술식 3+8*f-7의 중위 표기 계산을 위한 스택

32 5.4 스택의 응용 예(4/4) ￭ 산술식 3+8*f-7의 후위 표기 계산을 위한 스택