pop()은 O(1), shift()는 O(n)
자바스크립트에서 배열을 사용하다 보면, pop()과 shift() 메서드로 배열의 원소를 제거할 수 있다. 일반적으로 pop()은 배열의 맨 뒤 원소를, shift()는 배열의 맨 앞 원소를 제거하는 메서드로 알려져 있다. 그런데, pop()과 shift()를 구글에서 찾다 보면, 시간복잡도 이야기가 늘 따라붙는다. pop()은 O(1) time에, shift()는 O(n) time에 수행된다는 점이다.
기존 구현방식: 배열에 역순으로 값 넣기
배열의 가장 뒤에서 원소를 뽑아내는 것이 효율적이므로, 나는 큐를 사용하는 경우에 역순으로 배열에 집어넣는 선택을 하고 큐를 사용하고 있었다. 이 방법은 큐의 길이를 동적으로 조정해줘야 하는 경우가 아니라면 꽤 간단히 구현하고 사용할 수 있는 방법이었다. 그래서 최초 구현 당시 아무 고민없이 구현하고 사용했다. 1-2-3-4-5 의 순서로 이루어진 데이터를 5-4-3-2-1 순서로 배열에 넣으면 pop() 메서드로 1을 꺼낼 수 있기 때문이다.
하지만 이 방식도 늘 좋은 것은 아니다. 큐의 크기가 변하면 길이를 조정해 주어야 하는 문제가 있고, FIFO 원칙이 직관적으로 드러나지 않아 유지보수에 어려움을 겪을 수 있어 보인다. 향후 개발의 번거로움을 줄이기 위해 새로운 방식을 찾아보기로 했다.
대안1: 스택(Stack) 두 개를 사용하여 FIFO 원칙 구현
스택은 push()와 pop()이 O(1) 타임에 동작하기 때문에 이를 두 개 사용하여 효율적인 큐를 만들 수 있다. 첫 번째 스택(stack1)은 원소를 큐에 넣을 때 사용하고, 두 번째 스택(stack2)은 원소를 큐에서 꺼낼 때 사용하는 방법이다. 원소를 큐에서 꺼낼 때, stack2가 비어 있으면, stack1의 모든 원소를 pop()하여 stack2에 push()하고, 그 후 stack2에서 원소를 pop()하여 꺼내는 방식이다. 이렇게 하면 두 스택을 이용해 큐의 앞부분에서 꺼내는 것처럼 동작하게 된다. 그럼 개별 원소 입장에서 생각해보면, stack1.pop() -> stack2.push() -> stack2.pop() 순서로 꺼내지므로 O(3)로 사실상 O(1)같이 동작할 수 있는 것이다.
class Queue {
constructor() {
this.stack1 = [];
this.stack2 = [];
}
// 큐에 원소를 추가하는 메서드
enqueue(value) {
this.stack1.push(value);
}
// 큐에서 원소를 제거하고 반환하는 메서드
dequeue() {
if (this.stack2.length === 0) {
// stack2가 비어 있으면 stack1의 모든 원소를 옮긴다
while (this.stack1.length > 0) {
this.stack2.push(this.stack1.pop());
}
}
return this.stack2.pop();
}
// 큐가 비어 있는지 확인하는 메서드
isEmpty() {
return this.stack1.length === 0 && this.stack2.length === 0;
}
}
대안2: Linked List를 이용한 Queue 클래스 구현
링크드 리스트를 사용하면, 맨 앞에서 원소를 제거하는 dequeue()와 뒤에 원소를 삽입하는 enqueue() 모두 O(1) 시간복잡도를 유지할 수 있다. 성능을 더욱 최적화해야 하는 경우에는 링크드 리스트를 사용하는 것이 좋아 보인다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
}
enqueue(value) {
const newNode = new Node(value);
if (!this.rear) {
this.front = this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
}
dequeue() {
if (!this.front) return null;
const value = this.front.value;
this.front = this.front.next;
if (!this.front) this.rear = null;
return value;
}
isEmpty() {
return !this.front;
}
}
Linked List를 이용한 Queue 구현이 O(n) 타임 피하기라는 원래의 목적과, 클래스화를 통한 유지보수 용이성 개선이라는 목적을 모두 달성할 수 있어서 이 방식으로 가기로 마음먹었다. 코드 수정하러 가자.
'🔨 개발 > 🖥️ 웹개발' 카테고리의 다른 글
| MVC 패턴과 Flux 패턴: 차이점과 이해 (1) | 2024.12.25 |
|---|---|
| 로컬 스토리지(LocalStorage)란 무엇인가?, 어떻게 사용하는가? (1) | 2024.09.19 |
| CORS(Cross-Origin Resource Sharing)란 무엇인가? (1) | 2024.09.06 |
| JWT 로그인 인증 방식: Stateful vs Stateless (1) | 2024.09.06 |
| 메뉴 드롭다운 구현하기 (1) | 2024.09.03 |