Queue/Deque
Queue : 한 방향에서 입력이 이뤄지고, 그 반대편 방향에서 출력이 이루어지는 자료구조
- 큐의 구조는 스택과 다르게 '선입선출'의 구조를 가지고 있음 (먼저 들어온 것이 먼저 나가는 구조)
- 대기열은 양쪽 끝에 있으며 한쪽은 데이터를 삽입(enqueue), 반대쪽은 제거(dequeue)에 사용
- 예) 이메일, 쇼핑몰 주문, 콜센터 전화, 은행 대기 번호표
장단점
- 데이터접근, 삽입, 제거가 빠름
- 중간 데이터에 대한 접근이 불가능
큐의 추상자료형
- enqueue: 큐의 맨 뒤에 요소 삽입
- dequeue: 큐의 맨 앞에 요소 삭제
- peek: front에 위치한 데이터 참조
- front: 큐의 맨 앞의 위치 인덱스(프론트 데이터 출력)
- rear: 큐의 맨 뒤의 위치 인덱스(레어 데이터 출력)
Deque(Double-ended Queue)
- FILO + FIFO 형태의 자료구조
장단점
- FILO형식이든 FIFO 형식이든 둘다 사용가능한 유연성
- 양쪽에서 빠르게 요소의 추가/제거 가능
- 중간 데이터 접근은 느림
- 이중연결 리스트이기에 메모리 사용량이 큼
덱의 추상자료형
- printall: 모든 요소 출력
- addFirst: head에 데이터 삽입
- removeFirst: head에 데이터 제거
- addLast: tail에 데이터 삽입
- removeLast: tail에 데이터 제거
- isEmpty: 비어있는지 확인
힙(Heap): 완전 이진 트리 형태
- 마지막을 제외한 모든 노드에서 자식들이 채워진 이진트리구조
- 힙은 최대 힙과 최소 힙으로 구분가능
- 최대 힙은 모든 부모 노드의 값이 자식 노드의 값보다 큰 힙을 말함, 최소 힙은 그 반대
- 중복값을 허용
- 배열로 쉽게 구현가능
배열로 구현
- root 노드를 배열의 0번째에 저장시
- 왼쪽 자식노드는 a[ i * 2 +1] 에 저장
- 오른쪽 자식노드는 a[ i * 2 +2]에 저장
- 특정 노드에서 부모노드는 a[ (i - 1) //2]로 찾기 가능
힙의 재구조화(Heapify)
- 삽입과 삭제시 힙의 구조가 깨질때 재구조화를 통해 부모노드는 항상 자식노드보다 큰 조건을 만족하게 됨
- 추가할 경우 가장 말단에 있는 노드의 자식 노드로 추가가 되고 재구조화 과정이 일어남
- 삭제할 경우 가장 말단노드를 루트노드 자리에 대채한 후 재구조화 과정이 일어남
자바스크립트에서의 힙
- 콜스택과 힙메모리의 관계
메모리 누수
- 전역변수를 너무 많이 만들경우
- 캐시사이즈가 점점 커질경우 방대한 메모리 사용을 야기시킴
- 잊혀진 타이머와 콜백: setInterval()나 addEventListener()를 사용했다가 해제하지 않은 경우
- 사용하지 않지만 콘솔로 출력하는 경우
- DOM외부에서의 참조: DOM에서 removeChild()되었지만 여전히 해당 node를 querySelector등으로 사용하고 있는 경우
- 잘못된 클로져의 사용