[JS] 큐(Queue) 만들기

큐 (Queue)

 

큐는 선입선출 (FIFO, First-In First-Out) 형식의 자료 구조로, 후입선출 (LIFO, Last-In First-Out) 배열인 스택과는 반대되는 개념이다.

BFS 문제를 풀 때 주로 사용하게 되는데, JS에는 dequeue와 동일한 역할을 하는 shift 메소드가 존재하지만, 시간 복잡도가 O(n)인 관계로 배열의 길이가 긴 알고리즘 풀이에 활용하려면 큐를 직접 구현할 필요가 있다...

 

같은 코드에 shift(위), queue(아래)를 적용한 것. 메모리 차가 많이 난다;

 

 

코드

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.size === 0) this.head = newNode;
    else this.tail.next = newNode;
    this.tail = newNode;
    this.size++;
  }

  // 데이터 삭제
  dequeue() {
    if (this.size === 0) return undefined;
    const data = this.head.data;
    this.head = this.head.next;
    this.size--;
    return data;
  }

  // 큐 전체 데이터 조회
  getQueue() {
    if (this.size === 0) return [];

    let node = this.head;
    const arr = [];
    while (node) {
      arr.push(node.data);
      node = node.next;
    }
    return arr;
  }
}

 

위와 같이 코드 작성 시, 큐에 데이터를 추가할 때마다 마트료시카처럼 마지막 노드의 next에 다음 노드가 추가되는 것을 볼 수 있다.

 

 

 

결과 테스트

const q = new Queue();

q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);

console.log(q.getQueue()); // [ 1, 2, 3, 4 ]

const ret = q.dequeue();

console.log(ret); // 1