코딩테스트를 위한 JavaScript : Queue

JavaScript로 Queue 구현

JavaScript는 다른 언어들과 다르게 기본적으로 Queue관련 라이브러리가 따로 없어서 직접 구현해야한다.

크게 배열을 활용하여 구현하는 방법 또는 연결리스트를 활용하여 구현하는 방법 2가지가 있다.

 

배열로 Queue구현

class Queue {
  constructor() {
    this.queue = [];
    this.head = 0;
    this.tail = 0;
  }

  enqueue(value) {
    this.queue[this.tail] = value;
    this.tail += 1;
  }

  dequeue() {
    const value = this.queue[this.head];
    delete this.queue[this.head];
    if (this.tail - this.head > 0) {
      this.head += 1;
    }
    return value;
  }
}

위와 같이 구현하면 빠르게 queue를 구현할 수 있지만 데이터가 커지면 메모리의 양을 많이 잡아 먹는다는 단접이 있다.

 

연결리스트로 Queue구현

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  enqueue(value) {
    let newNode = new Node(value);
    if (this.head === null) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size += 1;
  }

  dequeue() {
    if (this.head === null) {
      return null;
    }
    let nowNode = this.head;
    this.head = this.head.next;
    this.size -= 1;
    return nowNode.value;
  }
}

위와 같이 구현하면 구현이 조금 복잡하지만 메모리를 적게 효율적으로 queue를 구현할 수 있다.