스택이란?
Last In First Out 이라는 개념을 가진 선형 자료구조이다.
나중에 들어간 요소가 먼저 나오고, 먼저 들어간 요소가 나중에 나온다.
흔히 상자에 물건을 넣으면 나중에 넣은 것이 위에 쌓이는 것과 같은 이치이다.
여기서 상자에 물건을 넣는 것을 push, 물건을 빼는 것을 pop 이라고 부른다.
그리고 맨 위에 있는 요소를 top 이라고 부른다.
더 비유하기에 좋은 물건을 들자면 프링글스 통이 있다. 프링그스는 구조상 맨 위에 있는 것부터만
과자를 꺼낼 수 있다. 아래에 위치한 과자는 먼저 꺼내고 싶어도 꺼낼 수 없는 구조이다.
스택의 동작 원리
스택의 동작 원리는 굉장히 단순하다. 할 수 있는 행동은 요소를 넣는 push 와 요소를 뺴는 pop 만이 존재한다. 가장 맨 위에 있는 요소만 컨트롤하기에 구현도 어렵지 않다.
스택 자료구조를 이용하는 가장 대표적인 것은 스택 메모리이다. 스택 메모리는 함수가 호출되며 생성되는 지역 변수, 매개 변수가 저장되는 메모리 영역이다. 좌측 코드 실행을 보며 스택 메모리가 어떤 식으로 동작하는지 확인 할 수 있다.
먼저 가장 안쪽에 위치한 sum 함수가 실행된다. 실행되면서 스택 메모리에는 매개변수, 지역변수, 반환 주소값이 push 되어 기록된다. sum 함수 실행이 종료되어 값이 반환되면 스택 메모리에서 pop 이 수행되어 제거가 된다.
이어서 print 함수가 실행된다. 아까 반환된 값으로 실행되어 스택 메모리에 기록이 된다.
print 함수 내부에는 console.log 함수가 있다. 따라서 console.log 함수가 실행 되면서 스택 메모리에 다시 쌓이게 된다.
무사히 log 출력을 마쳤다면, 스택 메모리에서 제거가 된다. print 함수도 호출이 완료되어서 스택 메모리에서 제거가 된다.함수 호출은 이런 식으로 스택 자료구조를 통해 메모리에 기록되고 제거된다.
자바스크립트 코드 표현 방법
그림 이 스택을 코드로 표현하는 방법은 2가지가 있다.
먼저 스택은 배열로 표현이 가능하다. push 를 하면 배열의 첫 번째부터 순차적으로 요소가 삽입된다. 그리고 pop 을 하면 가장 마지막 요소를 제거한다. 이런 방식은 배열의 단점인 중간 요소 추가, 삭제 로직이 전혀 사용되지 않기 때문에 굉장히 유리한 방식이다. 특히 자바스크립트에서 배열의 크기가 유연하게 증감되기 때문에 더 편하게 구현이 가능하다. 물론 자바스크립트의 배열은 엄밀히 따져서 진짜 배열이라고 할 수 없다.
const stack = []; // Push stack.push(1); stack.push(2); stack.push(3); console.log(stack); // [1, 2, 3] // Pop stack.pop(); console.log(stack); // [1, 2] // Get Top console.log(stack[stack.length - 1]); // 2다른 방법은 연결 리스트(Linked List)를 이용하는 것이다. C 언어나 Java 와 같은 언어에선 스택의 크기가 고정되지 않는 경우에 유한한 배열 대신 연결 리스트를 이용하여 구현하는 경우가 많았다. 이 경우 연결 리스트의 Head 가 Top 이라고 할 수 있다. 연결 리스트(Linked List)로 구현하는 방법은 조금 더 복잡하다. 연결 리스트 코드에서 Head 를 Top 으로 지정하고 제거 로직은 오직 Head 를 제거하는 방식으로 로직을 수정하면 된다.
