스택(Stack)이란?
- 최근 프로그래머스 코딩테스트를 풀어보면서 스택/큐 태마에 문제를 풀다 문득, 스택에 대한 정의를 확실히 내릴 수 없었습니다.
- 코드와 씨름하며, 프레임웍과 aws sdk들과 씨름하며 기능개발에 몰두하는 것도 좋지만 기본기를 다지고 싶었습니다.
- 때문에 자료구조에 대해서 정리해봅니다.
- 자료구조를 생각하면 대표적으로 떠오르는 스택(Stack)이란? 무엇일까요?
1. 스택의 개념 정리
- 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있습니다.
- 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 합니다.
- 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 됩니다.
- 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조(한국어로 후입선출)라고 합니다.
- 쉽게 설명하면 스택은 바닥이 막힌 상자라고 보면 됩니다. 나중에 넣은 물건이 위에 있으므로 먼저 꺼낼 수 밖에 없습니다.
2. 스택의 구현
- 위에서 설명한 것 처럼 스택은 후입선출 개념입니다. 배열을 이용하여 구현을 예로 들어보겠습니다.
- 예제로 사용할 배열 array를 아래와 같이 만들어 줍니다.
let array = new Array();
- 자료를 밀어넣는 이벤트인 push를 사용하여 5개의 자료(값)을 차례대로 넣어줍니다.
array.push('m');
array.push('i');
array.push('n');
array.push('g');
array.push('y');
array.push('u');
- m,i,n,g,y,u 순서대로 array라는 바닥이 막힌 상자에 차곡차곡 쌓이게 됩니다.
- 이제 자료를 꺼내는 Pop을 사용해보면 후입 선출개념에 맞게 'm'이 먼저 나오는게 아니라 'u'부터 나오게 됩니다.
let pop = array.pop();
console.log(pop); // print :: u
- 자료를 한개 꺼낸 array를 console에 찍어보면 u 다음으로 넣었던 y가 마지막으로 오게됩니다.
console.log(array);
// print :: ['m','i','n','g','y']
- 후입선출, 이것이 스택 구현의 기초되는 사용법입니다.
3. 스택의 응용
- 위에서 보신 것 처럼 구현이 너무 쉬운데 응용하기에 따라 무궁무진하게 프로그래밍에 사용할 수 있습니다.
- 쉬운 예제로 웹사이트 뒤로가기 혹은 편집기의 control+z 기능도 가장 최근에 실행한 무언가를 취소한 후 마지막에 들어간 자료가 먼저 나오는 스택구조를 응용하여 개발되었습니다.
- 또다른 예제로 재귀함수(자기 자신을 호출하여 사용하는 함수)도 스택을 기반으로 하고 있습니다.
function factorial(num) {
if (num < 1) {
return 1;
}
return num * factorial(num - 1);
}
console.log(factorial(5));
// print :: 120
- 위 예제는 팩토리얼을 구하는 재귀함수 예제입니다. 함수가 자신의 안에서 자신을 호출합니다.
- 풀이를 한다면 console.log(5)를 하였을 경우 아래와 같이 연산이 됩니다.
- 5는 1보다 큼으로 return 5 * factorial(4);
- 4는 1보다 큼으로 return 4 * factorial(3);
- 3은 1보다 큼으로 return 3 * factorial(2);
- 2는 1보다 큼으로 return 2 * factorial(1);
- 1은 1보다 작지않음으로 return 1 * factorial(0);
- 0은 1보다 작음으로 return 1;
- 1번부터 6번까지가 실행된 이후 (마지막에 실행된 것 부터) 차례대로 아래와 같이 실행됩니다.
- 6의 리턴값이 5의 factorial(0)값이 되어 1*1
- 4의 factorial(1)의 값이 1이되어 factorial(2)는 return 2*1 = 2
- 2의 factorial(3)의 값은 return 3* 2 = 6
- 1의 factorial(4)의 값은 return 4*6 = 24
- 결국 console.log(factorial(5));의 facotrial(5)는 5*24 = 120이 됩니다.
- 스택 구조와 마찬가지로 마지막에 들어갔던 것 부터 차례대로 사용되는 것을 확인할 수 있습니다.
마무리
- 스택은 후입선출 특성을 가지는 자료구조를 일컫는 말입니다.
- 스택은 바닥이 막힌 상자에 자료를 넣고 빼는 것을 생각하면 이해하기 쉽습니다.
