Reference
JS로 알고리즘 문제 풀이시, 가장 답답한 점은 기본적으로 제공되는 자료구조가 빈약하다는 점입니다.
가장 기본적인 Stack, Queue, Deque 를 시작으로 자료구조의 개념을 JS에서 어떻게 구현할 수 있는지에 대해 포스팅해보겠습니다.
이후에 Linked List, Map, Set, Heap(Priority Queue), 이진 tree, graph 등에 대해서도 다루어보도록 하겠습니다.
0. Array
JS에는 내장된 Stack, Queue, Deque 객체가 없습니다. 가장 유사한 Array 객체를 사용하여 Stack, Queue, Deque를 흉내낼 수 밖에 없습니다.
배열은 메모리 상에 원소를 연속하게 배치한 자료구조입니다.
우선 배열의 특징을 먼저 알아보겠습니다.
-
임의의 위치에 있는 원소에 O(1)으로 접근・수정할 수 있다.
-
배열의 끝에 O(1)으로 원소를 추가할 수 있다.
-
배열의 마지막 원소를 O(1)으로 삭제할 수 있다.
-
임의의 위치에 원소를 추가・삭제는 O(N)이다.
JS에서 배열은 Array 객체를 이용합니다.
Array는 크기를 동적으로 늘였다 줄일 수 있습니다. 즉, C++과 같은 정적 언어에서의 배열과 달리 원소를 추가하면 길이가 늘어나고,
임의의 인덱스의 요소에도 접근・할당할 수 있습니다.
왜냐하면, Array는 프로퍼티 키가 숫자열인 객체이기 때문입니다.
1. Stack
정의
Stack은 바로 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조입니다.
Stack은 구조의 특성상 나중에 넣은 원소가 먼저 나오게 되어 있습니다. (LIFO: Last-In-First-Out)
특징
Stack의 특징은 아래와 같습니다.
-
최상단에 원소를 O(1)으로 추가할 수 있다.
-
최상단에 원소를 O(1)으로 삭제할 수 있다.
-
최상단에 원소를 O(1)으로 접근할 수 있다.
JS에서의 활용
Array를 이용하여 Stack을 정의해보겠습니다.
-
push_back: 최상단에 원소를 추가
-
pop_back: 최상단의 원소를 접근후 삭제
-
back: 최상단의 원소에 접근
-
size: Stack의 길이를 판별
const stack = [1, 2, 3];
// push_back: 최상단에 원소를 추가
stack.push(4);
console.log(stack); // [1,2,3,4]
// pop_back: 최상단의 원소를 접근 후 삭제
const last = stack.pop();
console.log(last, stack); // 4 [1,2,3]
// back: 최상단의 원소에 접근
const last2 = stack[stack.length - 1];
console.log(last2, stack); // 3 [1,2,3]
// size: Stack의 길이를 판별
const size = stack.length;
console.log(size); // 3;
