Queue를 class로 구현해보자.

오늘 문제를 풀다가 queue를 구현해야 풀 수 있는 문제를 만났다. 평소에 queue라는 것을 생각하면, FIFO에 대해서만 생각하고 생각을 끝냈던 것 같다. 먼저 들어가면 먼저 나온다. 그래서 오늘 백준에서 문제를 풀이할 때 queue의 구현성을 먼저 생각하지 못했던 것 같다.

queue 언제 쓸까?

아니, queue의 특징을 조금 더 나열하는게 좋을 것 같다.

• FIFO
• search bigO(n)
• insert bigO(1)
• delete bigO(1)

탐색이 적고, enqueue dequeue가 많은 경우에 사용하기 좋다. 이전에 스택 문제를 풀 때 스택을 구현하여도 불편하지 않았던 이유는 배열을 이용하여 pop을 이용하여도 손쉽게 풀리며 배열을 사용하면, search도 1, pop도 1 push도 1이기때문에 별다른 불편함이 없이 쉽게 풀었던 것 같다.

queue 를 구현하려면 필요한 것

• 본인 개인(Node)
• 전체 맵(Linked List)

두가지가 필요하다. 먼저 각 노드를 구선언해보자.

본인의 앞뒤가 누구인지 확인하고, 전체의 맨끝과 맨앞이 필요하다. 우선 본인 개인의 클래스를 선언해보자. 본인이 알아야할 것은 본인의 숫자, 앞, 뒤 세가지이다.

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

이제 전체 맵을 선언해보자. 전체 맵에는 head, tail, value가 필요하고, head를 얻는 것과 length를 얻는 것, head를 제거하는 것 3개가 필요하다

class LinkedList {
  #size
  constructor(){
    this.head = null;
    this.tail = null;
    this.#size = 0;
  }
  add(n){
    const node = new Node(n);
    if(!this.head) this.head = node;
    else{
      this.tail.next = node;
      node.prev = this.tail
    }
    this.tail = node
    this.#size++
    return node
  }
  getHead(){
    return this.head.value;
  }
  removeHead(){
    this.head = this.head.next;
    this.head.prev = null;
    this.#size --;
  }
  getLength(){
    return this.#size;
  }
}

문제에서 무엇을 필요하고 어떤 흐름으로 흐르는지 알게 되니 queue가 자연스럽고 쉽게 구현이 된 것 같다! 내가 잘이해하고 있나 내일 다시 테스트 봐야지!