50. 스택(Stack)

- 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다. 

- 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO; Last-In , First-Out) 방식으로 자료를 처리한다. 

 

TOP : Stack으로 할당된 기억공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소, 스택 포인터라고도 함

Botton : 스택의 가장 밑바닥임

PUSH : 스택에 자료를 입력하는 명령

POP : 스택에서 자료를 출력하는 명령

 

Stack의 용도

- 부프로그램 호출 시 복귀주소를 저장할 때

- 함수 호출의 순서 제어

- 인터럽트가 발생하여 복귀주소를 저장할 때

- 후위 표기법(Postfix Notation)으로 표현된 산술식을 연산할 때

- 0 주소지정방식 명령어의 자료 저장소

- 재귀(Recursive) 프로그램의 순서 제어

- 컴파일러를 이용한 언어 번역 시 

 

* 재귀 프로그램이란? : 한 루틴이 자기를 다시 호출하여 실행하는 프로그램을 말합니다. 

 

후위 표기법(Postifx)

- 연산자(기호)를 피연산자의 뒤에 놓는 방법

- 괄호가 없어도 계산 순서가 일정하며 연산자의 우선순위 고려 안해도 됨 --> 컴퓨터에 유리

 

* 중위 표기법(Infix)에서 후위 표기법으로 변경하기

1. 숫자가 나오면 그대로 출력한다.

2. (가 나오면 스택에 push

3. * /가 나오면 스택에 push

4. 연산자일 때 : 1. 스택 안 연산자 우선순위가 더 크거나 같으면 pop한 후 , 입력받은 연산자 push

                     2. 스택 안 연산자 우선순위가 더 작으면 입력받은 연산자 push 

5. 닫는 괄호가 나오면 여는 괄호가 나올 때 까지 pop 하여 스택 끝까지 출력한다. 

 

* 괄호를 제거하고 후위표기법으로 바꾸는 방법 

1. 연산자 우선순위에 맞게 괄호를 쳐준다

   ((A*B) - (C/D))

2. 각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동시켜 

  ((AB)*(CD)/)-

3. 괄호 제거 

   AB*CD/-

 

* 연산자 우선순위 

1. * /

2. + -

3. (