큐 구현하기 - 연결리스트

백준 18258 참고

 

이전까지는 자바스크립트 내장 함수인 shift와 push를 이용해서 배열로 큐를 구현했었다.

하지만 shift 메서드 자체가 O(N)의 시간복잡도를 가지고 있기 때문에 데이터의 양이 많아지는 경우에는 비효율적이다.

물론 18258번 문제도 배열을 이용한 큐를 사용하면 통과하지 못한다.

그래서 가장 많이 사용하는 연결 리스트 방법을 이용해서 큐를 직접 구현해보기로 했다.

 

연결 리스트 방법이 O(1)의 시간복잡도를 가지는 이유는 큐에서 요소가 제거되어도 모든 요소를 탐색해서 끌어올 필요가 없기 때문이다. shift 메서드를 사용하면 배열의 맨 앞의 요소를 제거하고 모든 배열의 요소를 앞으로 끌어오는 과정에서 O(N)의 시간복잡도가 발생하지만 연결리스트는 front와 rear의 위치만 변경하면 되기 때문에 그럴 필요가 없다.

 

---

기본 구조

 

우선 노드와 큐의 구조로 나누어진다.

노드는 data와 그 다음 노드의 정보를 가지고 있는 next가 존재한다.

그리고 큐는 맨 앞의 요소 정보를 가지고 있는 front와 맨 마지막 요소의 정보를 가지고 있는 rear가 존재한다.

투포인터와 비슷한 개념이다.

 

Enqueue

큐에 요소를 삽입하는 과정이다.

 

 

만일 큐에 어떤 요소도 존재하지 않는다면 현재 front와 rear가 가리키는 것은 null이다.

그렇다면 다음의 과정을 거쳐서 큐에 노드를 추가해야한다.

 

1. 새로운 노드 newNode를 생성해서 데이터를 넣어준다.

2. front가 newNode를 가리키게한다.

3. newNode의 next에 기존 rear가 가리키는 값을 넣는다. (null 값이 들어올 것이다.)

4. rear가 newNode를 가리키게 한다.

5. 큐의 사이즈를 올려준다.

 

위의 과정을 거치면 성공적으로 큐에 데이터가 담기게 된다.

 

그렇다면 큐에 데이터가 이미 존재하는 경우에 데이터를 추가하려면 어떤 과정을 거쳐야하는가.

 

1. 새로운 노드 newNode를 생성한다.

2. rear가 가리키는 노드의 next가 newNode를 가리킨다.

3. rear가 newNode를 가리킨다.

 

Dequeue

큐에서 맨 첫번째 요소를 제거하는 과정이다.

 

1. front가 가리키는 요소를 임시 변수에 담는다.

2. front가 가리키는 요소의 next에 접근해서 front가 해당 요소를 가리키게 한다.

3. 큐의 사이즈를 줄인다.

 

 

하지만 요소가 한 개인 상황에서 Dequeue를 하게 되면 front와 rear를 모두 초기화 시켜줘야한다.

즉, 요소가 2개 이상인 경우와 한 개인 상황을 따로 고려해서 코드를 작성해야한다.

만일 요소가 없는 상황에서 Dequeue를 하게 되면 -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.head.next = this.tail;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.size += 1;
  }

  dequeue() {
    if (this.size >= 2) {
      const data = this.head.data;
      const newHead = this.head.next;
      this.head = newHead;
      this.size -= 1;

      return data;
    } else if (this.size === 1) {
      const data = this.head.data;
      this.head = null;
      this.tail = null;
      this.size -= 1;

      return data;
    } else {
      return -1;
    }
  }

  getSize() {
    return this.size;
  }
}