7주차 배운 내용

덱, 자바스크립트에서 큐와 스택이 어떻게 사용되는지와 힙에 대해 배웠습니다.

큐 (queue)

큐의 삭제(dequeue)는 항상 헤드노드에서, 추가(enqueue)는 항상 테일노드에서 일어나는 구조이다.

덱 (deque)

덱이란 Dobulee Ended Queue의 줄임말인 deque를 말하며, 큐(queue)자료 구조형과는 다르게 일방향 단일연결리스트구조가 아닌 이중연결리스트이다.

단일연결리스트에서는 한 노드가 다음 노드의 주소값만을 가지며 이전 노드에 대한 데이터가 없기 때문에 한 방향성을 유지하는 반면에, 이중연결리스트는 노드가 이전과 다음 노드의 주소값을 모두 가져서 양방향성을 가질 수 있다.

덱의 특징으로는 헤드노드와 테일노드의 양쪽에서 추가/삭제가 가능하여 끝 단의 자료를 수정하는데 용이하다. 대신에 중앙에 가까운 자료일수록 비용이 크다.

자바스크립트 내의 큐와 스택

콜스택

자바스크립트는 싱글 스레드 기반의 언어이며 하나의 호출 스택을 가진다. 한번에 하나의 일 밖에 못하므로 스택구조에서 한 작업당 한 스택씩 수행해나가는 구조이다. 컴파일(개발자가 작성한 코드를 바이너리 코드로 변환)하는 동안 스택을 쌓아 나간다. 원시형 자료나 함수 또는 참조형 자료의 주소를 저장한다.

//컴파일
let myNumber = 1; 
//integer -> 원시형 -> 4바이트 -> 콜스택
let myObject = { objName: 'none', objType: 'obj' }; 
//Object -> 참조형 -> 콜스택에 주소만, 크기는 ?? -> 메모리힙

콜스택은 가상 메모리 영역을 할당받으며, 지정된 가상 메모리 크기 이상으로 스택이 쌓여 최대치에 도달하면 Maxium callstack exceed 에러를 출력한다. 재귀함수에 base case가 없거나 while loop에 break
case가 없으면 쉽게 만나볼 수 있다.

메모리힙

런타임(실행되는 환경인 동안)에 동적으로 할당되는 자료를 가진다. 컴파일 단계에서는 참조형 자료의 주소값이 스택에 저장되고 이 후 런타임 때 실제 자료의 내용과 크기가 변할 수 있도록 한다.

메모리힙도 가상 메모리 영역에서 할당되므로, 메모리힙내의 자료양이 최대 크기 이상으로 쌓이기 시작하면 Out of memory 에러를 출력한다. 잘못 사용된 클로저나 의도치 않게 생성된 전역 변수가 메모리를 먹고 있을 때 만나볼 수 있다. 참고로 전역 변수는 Garbege Collector에 의해서 수집되지 않는다.

마치며

초반에 너무 요약해서 대충 지나간 내용들이 많아서 앞으로도 중복되는 글이 늘어날 것 같다.

한 주제당 하나씩 자세하게 다룰 수 있도록 다시 개편해야 할 것 같다.