🌱 이전 포스트 정리
자료구조에 대한 설명과 종류에 대해서 담았고, 프로그램의 성능 측정 방법에 대해서도 얘기했습니다.
그리고 배열과 연결 리스트가 JS에서 어떻게 사용되며 어떤 특징을 가졌는지도 얘기했습니다.
이번 포스트에서는 선형 자료구조의 하나이며 중요한 자료구조 유형인 스택에 대해서 다뤄보겠습니다.
🌱 스택 Stack
스택은 먼저 들어온 데이터가 나중에 나가는, LIFO(Last In First Out) 자료구조입니다.
박스를 위로 탑을 쌓아올린 형태가 스택과 같습니다.
위 그림과 같다고 생각하면 좋습니다.
여러 개의 데이터를 삽입하고 삭제한다면 아래와 같이 데이터가 남죠.
연산 과정
push 3 - push 5 - pop - push 7 - pop - push 8 - pop - push 2 - push 9
결과
9, 2, 3
스택은 아주 기본적인 자료구조에 해당합니다. 알고리즘을 이용한 코딩테스트에 아주 많이 이용될 뿐 아니라,
브라우저에서 자바스크립트가 실행되는 순서도 콜스택을 사용합니다. 그만큼 스택은 자주 사용되죠.
그래서 스택에 대해 이해하고, 이를 이용하는 방법을 아는 것이 중요합니다.
| 연산 | 시간 복잡도 |
|---|---|
| 삽입 | O(1) |
| 추출 | O(1) |
| 최상위 원소(Top) | O(1) |
| Empty | O(1) |
JS에서 기본적으로 제공하는 스택 연산은 배열의 push = 삽입, pop = 추출이 있습니다.
let stack = [];
stack.push(5);
stack.push(2);
stack.push(3);
stack.push(7);
stack.pop();
stack.push(1);
stack.push(4);
stack.pop();
let reversed = stack.slice().reverse(); // 5231 -> 1325
console.log(reversed);
console.log(stack);배열로 구현된 스택은 bottom이 stack[0]과 같습니다.
당연히 top은 stack[stack.length -1]입니다.
연결 리스트를 사용해서 스택을 구현할 수도 있습니다.
스택을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있습니다.
연결 리스트로 구현할 때는 머리(head)를 가리키는 한 개의 포인터만 가집니다.
머리(head): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터
- 삽입할 때는 머리(head) 위치에 데이터를 넣습니다.
- 삭제할 때도 머리(head) 위치에서 데이터를 꺼냅니다.
연결 리스트에서 새로운 데이터를 삽입할 때는 기존 stack의 top의 머리에 연결합니다.
🌱 마무리
오늘은 스택에 대해서 알아봤습니다.
스택은 단방향으로 데이터의 입출력이 이루어지기 때문에 유용하게 사용할 수 있는 자료구조입니다.
