큐를 이용한 알고리즘 문제를 풀 때 매번 shift 메소드를 이용해서 문제를 풀다보니 시간초과를 많이 겪게 된다. shift 메소드를 이용하면 맨 앞의 원소를 꺼내고 다른 모든 원소들을 한칸씩 인덱스를 당겨줘야하기 때문인데 연결리스트를 구현하게 되면 O(N)의 시간복잡도를 O(1)로 줄일 수 있다.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
enqueue(data) {
const newNode = new Node(data);
// 기존 데이터가 없는 경우
if (!this.head) {
this.head = newNode;
this.tail = newNode;
}
// 기존 데이터가 있는 경우 뒤로 삽입
else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size += 1;
}
dequeue() {
// 기존 데이터가 없는 경우 null을 리턴
if (!this.head) {
return null;
}
const removedNode = this.head;
// 기존 데이터가 있는 경우 두번째 노드를 head로 만든다.
this.head = this.head.next;
// 두번째 노드가 null이 었을 때(원소가 없는 경우)
if (!this.head) {
this.tail = null;
}
this.size--;
return removedNode.data;
}
isEmpty() {
return this.size === 0;
}
}
'자료구조 및 알고리즘' 카테고리의 다른 글
Javascript - 최소 힙(MinHeap) (1) | 2023.12.21 |
---|