JavaScript에서 Queue 구현하기: 배열 vs 연결 리스트 vs 두 개의 스택

들어가며

큐(Queue)는 중요한 자료구조 중 하나로, FIFO(First-In-First-Out) 특성을 가지는데요. 첫 번째로 들어간 요소가 가장 먼저 나옵니다.

 

이번 포스트에서는 자바스크립트를 사용하여 큐를 구현하는 세 가지 방법에 대해 알아보겠습니다.

 

---

1. 배열을 이용한 구현

자바스크립트에서 가장 간단하게 큐를 구현하는 방법은 배열(Array)을 사용하는 것입니다.

push 메서드로 새 요소를 추가하고, shift 메서드로 첫 번째 요소를 제거합니다.

 

enqueue는 O(1)에 수행됩니다.

dequeue는 O(n)에 수행됩니다. 배열에서 첫 번째 요소를 제거하면 모든 요소가 한 칸씩 앞으로 이동해야 하기 때문입니다.

 

아래는 구현 코드입니다.

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return null;
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

 

2. 단일 연결 리스트를 이용한 구현

단일 연결 리스트(Singly Linked List)를 사용하여 큐를 구현할 수 있습니다.

여기서 각 노드(Node)는 데이터와 다음 노드에 대한 참조값을 가집니다.

 

enqueue와 dequeue 모두 O(1)에 수행됩니다. 새로운 노드의 추가와 제거가 연결 리스트의 앞 또는 뒤에서만 발생하기 때문입니다.

 

자바스크립트에서 객체(여기서는 Node)를 생성하고 삭제하는 것은 비용이 발생합니다. 따라서, 메모리 할당 및 가비지 컬렉션에 관련된 오버헤드가 있을 수 있습니다.

 

아래는 구현 코드입니다.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(data) {
    const newNode = new Node(data);

    if (this.isEmpty()) this.front = newNode;
    else this.rear.next = newNode;

    this.rear = newNode;
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) return null;

    const dequeuedData = this.front.data;
    this.front = this.front.next;
    this.size--;

    if (this.isEmpty()) this.rear = null;

    return dequeuedData;
  }

  isEmpty() {
    return this.size === 0;
  }
}

 

3. 두 개의 스택을 사용한 구현

마지막으로, 두 개의 스택(Stack)을 이용해 큐를 구현할 수 있는데요.

스택은 LIFO(Last-In-First-Out) 특성을 가지는 자료구조입니다. 마지막으로 들어간 요소가 가장 먼저 나옵니다.

 

enqueue는 O(1)에 수행됩니다.

dequeue는 'lazy'하게 처리되므로, 최악의 경우 O(n)에 수행됩니다. 하지만 평균적으로 보면 각 요소당 한 번씩만 이동되므로 평균 실행시간은 여전히 O(1)입니다.

 

배열을 사용하므로 메모리 관리 면에서 효율적입니다. 자바스크립트 엔진은 배열에 대해 최적화된 처리를 수행할 수 있으며, 추가적인 객체 생성 없이 원소들을 관리할 수 있습니다.

 

아래는 구현 코드입니다.

class Queue {
  constructor() {
    this.inbox = [];
    this.outbox = [];
  }

  enqueue(data) {
    this.inbox.push(data);
  }

  dequeue() {
    if (!this.outbox.length) {
      while (this.inbox.length) {
        this.outbox.push(this.inbox.pop());
      }
    }

    return this.outbox.pop();
  }

  size() {
    return this.inbox.length + this.outbox.length;
  }

  isEmpty() {
    return this.size() === 0;
  }
}

 

dequeue 연산은 다음과 같이 수행됩니다.

1. outbox 스택이 비어 있지 않다면, outbox에서 pop 연산을 수행합니다. 이 경우 시간 복잡도는 O(1)입니다.
2. 그러나 outbox가 비어 있다면, inbox의 모든 요소를 pop하여 outbox로 push해야 합니다. 이 때 inbox에 n개의 요소가 있다고 가정하면, 각 요소를 pop하고 push하는 데 각각 상수 시간(O(1))이 걸리므로 총 시간 복잡도는 O(n)입니다.

위 구현에서 n번의 dequeue 연산을 생각해보면 첫 번째 dequeue에서만 O(n)시간이 소요되고, 그 후 n-1번의 dequeue에서는 O(1)시간이 소요됩니다.

따라서 n번의 dequeue연산에 대한 평균 실행시간은 (O(n) + O(1) * (n-1)) / n = O(1) 입니다.

 

정리

지금까지 살펴본 세 가지 방식의 시간 복잡도는 다음과 같습니다.

	배열	단일 연결 리스트	두 개의 스택
enqueue	O(1)	O(1)	O(1)
dequeue	O(n)	O(1)	최악 O(n) 평균 O(1)

 

장단점을 한번 정리해보도록 하죠.

 

배열

• 장점: 구현이 간단합니다.
• 단점: dequeue가 O(n)에 수행됩니다.

단일 연결 리스트

• 장점: enqueue와 dequeue 모두 O(1)에 수행됩니다.
• 단점: 메모리 할당 및 가비지 컬렉션에 관련된 오버헤드가 있을 수 있습니다.

두 개의 스택

• 장점: 메모리 관리 면에서 효율적입니다. enqueue와 dequeue 모두 평균적으로 O(1)에 수행됩니다.
• 단점: dequeue가 'lazy'하게 처리되므로, 최악의 경우 O(n)에 수행됩니다.

 

---

마치며

배열, 단일 연결 리스트, 두 개의 스택으로 큐를 구현하는 방법에 대해서 알아봤는데요.

각각 장단점이 있으니 상황에 따라 적절한 방법을 선택하면 될 것 같습니다.

 

잘못된 부분은 지적 부탁드립니다.

감사합니다 :D