[TIL 2021.10.06] 스택

Today I Learned
스택

스택은 객체와 그 객체가 저장되는 순서를 기억하는 자료구조를 말한다.

스택은 밑바닥과 사방이 막힌 통에 차례대로 무언가를 넣은 것을 상상하면 된다. 그 안에 순서대로 그 통에 맞는 객체를 넣었다고 생각하면 된다.

이 때, 그 객체와 그 객체의 순서를 기억하는 자료구조이다.

가장 맨위에 놓여진 객체를 모두가 top 이라고 부른다. 그리고 객체를 삭제할때는 항상 top 에서 빼야하고 그것을 pop 라고 한다. 반대로 추가할때는 push 라고 한다.

스택은 크게 1. 변수 생명주기 관리 2. 서브루틴 호출 관리 (함수 주소를 저장하기 위한) 3. 수식 계산으로 응용된다.

1,2번은 늘 쓰던 함수들을 생각해보면 된다.

예를 들어서 Main -> A -> B 와 같이 3개의 함수가 있고 각각 화살표모양의 의존성을 가진다고 생각해본다.

이때 Main, A, B 순서대로 실행이 될 것인데, 이것이 스택에서 관리가 된다. 함수를 호출하기 전에 사용되는 변수들도 같이 저장이 되었다가 사용되어진다.

수식계산할때도 사용되어진다.

사칙연산식의 전위/후위/중위 표현이 있다. 예를 들어 후위표현은 A+B를 AB+ 라고 표현하고 이것을 스택에 차례대로 넣는다.

예를 들어 A + ((Z - B) * C) 라는 식이 있으면,

1. (ZB-)
2. (ZB-)C*
3. A((ZB-)C*)+

이런식으로 괄호에 있는 것먼저 계산이 되어지고 수식은 뒤로 간다. 이걸 차례대로 스택에 넣는다.