자료구조 ) Javascript의 스택과 큐

작성일 In Views: Disqus:

이번 포스팅에서는 가장 기본적인 자료구조인 스택과 큐에 대해 알아보고, 우리가 자바스크립트로 개발하면서 어떻게 적용되고 있었는지 확인해보겠습니다. 가볍게 이런식으로 사용되고 있었구나 정도만 확인하고 정확한 동작원리는 따로 자바스크립트 포스팅에서 자세히 다루겠습니다.

▪︎ 스택 (Stack)

image.png

스택은 가장 마지막에 저장된 데이터가 먼저 실행되는 후입 선출 (Last In First Out, LIFO) 구조입니다. 스택은 데이터의 삽입과 삭제 (실행)가 O(1), 탐색에는 O(N)의 시간복잡도를 가집니다.

▪︎ 큐 (Queue)

image.png

큐는 삽입된 순서되로 삭제 (실행)되는 선입 선출 (First In First Out, FIFO) 구조입니다. 큐와 마찬가지로 삽입과 삭제에는 O(1), 탐색에는 O(N)의 시간복잡도를 가집니다.

▪︎ 자바스크립트의 실행 컨텍스트 스택

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const a = 1;
const b = 2;
const c = 3;

console.log(a);

const sum = (...element) => {
  return element.reduce((acc, cur) => acc + cur);
};

const minus = (element1, element2) => {
  return element1 - element2;
};

const result1 = sum(a, b, c);
const result2 = minus(b, a);

console.log(result1);
console.log(result2);

image.png

우리가 자바스크립트로 짠 코드가 실행되는 런타임에서 코드를 읽어가면서 함수를 호출할 때마다 스택에 실행컨텍스트를 쌓고, 실행이 완료되면 삭제하는 과정을 거칩니다. 위 예시를 통해 이해해보겠습니다. 먼저 자바스크립트가 실행되면 (런타임) 전역 실행 컨텍스트를 스택에 등록하고 해당되는 코드들을 실행하기 시작합니다. 그렇게 코드들을 실행하다가 함수의 호출부를 만나게 되면 진행되던 코드 실행을 잠시 멈추고 해당 함수에 대한 실행 컨텍스트를 스택에 삽입하게 됩니다. 그리고 함수를 실행하고 삭제하는 과정을 거친 뒤, 다시 전역 실행 컨텍스트의 코드 실행을 진행하며 모든 코드가 실행되었을 때, 전역 실행컨텍스트를 삭제하게 되면서 자바스크립트 실행이 끝나게 됩니다.

▪︎ 자바스크립트의 태스크 큐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const a = 1;

console.log(a);

const consoleAfter1 = (element) => {
  setTimeout(console.log(element), 1000);
};

const consoleAfter2 = (element) => {
  setTimeout(console.log(element), 2000);
};

consoleAfter1(a);
consoleAfter2(a);

console.log(a);

image.png

위 코드에서 우리에게 익숙한 setTimeOut 함수가 보입니다. 우리는 setTimeOut을 막연하게 설정한 시간(ms) 이후에 실행되는 함수라고 알고 있습니다. 그렇다면 위 코드에서 consoleAfter1, consoleAfter2 함수가 호출되기 전 10초가 걸릴 정도의 코드가 작성되었다 가정해봅시다. 그럼 console.log가 어떤 순서로 실행될까요? 여전히 1 → 2 → consoleAfter1 → consoleAfter2 의 순서로 실행될 것입니다.

즉 정확히 말하면 setTimeOut 함수는 ‘정해진 시간 뒤에 실행해라’가 아닌 ‘정해진 시간 뒤에 태스크 큐에 콜백함수를 집어넣어라!’라는 동작을 하는 함수입니다. 태스크큐는 이렇듯 비동기 함수들이 실행컨텍스트 스택 내에서 실행되면 순서대로 태스크 큐에 함수들을 쌓게 됩니다. 그리고 실행컨텍스트들이 모두 실행되어 실행컨텍스트 스택이 비게 되면, 비로소 태스크큐에 삽입된 순서대로 실행되게 됩니다.