JavaScript로 Queue 자료구조 구현하기

JavaScript 로 Queue 자료구조 구현하기

 

Queue란?

큐는 먼저 입력된 데이터가 먼저 나오는 자료구조를 말합니다.

FIFO(First In First Out) 이라고도 합니다.

 

흔히 대기열이나 선착순을 생각하면 됩니다.

먼저 줄을 서면 먼저 처리됩니다.

 

Queue의 속성으로는 

가장 앞을 가리키는 Head(front)와 가장 뒤를 가리키는 Rear(tail)가 있고,

 

front는 데이터를 get(delete) 할 수 있는 위치를 의미하고,

tail은 데이터를 put(insert) 할 수 있는 위치를 의미합니다.

 

데이터를 꺼내는 것이 get(queue에서 delete)

데이터를 입력하는 것이 put(queue로 insert) 입니다.

 

이 중에서 get(delete) 작업을 deQueue 매소드로,

put(insurt) 작업을 enQueue 매소드로 구현해보았습니다.

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

// 값이 없을때 사이즈는 0을 리턴하는데, storage 객체의 rear 키값이 undefined라면
// 아무런 값이 없을 때라고 할 수 있을 것 같아서 그렇게 조건식을 만들었습니다. 
// 물론 front의 키값이 undefined 라고해도 마찬가지일 것입니다.
// 둘 모두의 키가 0이기 때문에 front와 rear가 같은 곳을 바라볼때, 라는 조건식으로 생각했다가,
// 값이 하나가 들어와도 0이면서 둘다 같은 곳을 바라보기 때문에, 명확하게 undefined로 정하였습니다.
// 숫자의 개수는 뒷수-앞수+1 개 라는 산수식을 떠올려 구현했습니다.
// Object.keys[객체].lenght를 사용할 수도 있겠습니다. 
  size() {
    if (this.storage[this.rear] === undefined) {
      return 0;
    } else {
      return this.rear - this.front + 1
    }
  }
  
  // 처음 값이 들어올 때를 제외하고는, rear가 1씩 증가하도록 구현했습니다.
  enqueue(element) {
    if (this.size() === 0) {
      this.storage['0'] = element;
    } else {
      this.rear += 1;
      this.storage[this.rear] = element;
    }
  }

// front와 rear가 같은 곳을 바라보고 있다면, 증감하지 않고 리턴하고,
// 다른 곳을 바라보고 있을땐 front가 1씩 증가되도록 하였습니다.
// 왜냐면 값이 단 하나일 때, front와 rear가 같은 곳을 바라보게되는데,
// 이때 dequeue를 했다면, 빈 객체가 되고, 이때 다시 0부터 시작할 수 있도록 초기화를 해줍니다.

  dequeue() {
    let temp;
    if (this.front === this.rear) {
      temp = this.storage[this.front];
      delete this.storage[this.front];
	  this.front = 0;
	  this.rear = 0;
      return temp;
    } else {
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front += 1;
      return temp;
    }
  }
}

Queue는 Stack과는 다르게 front와 rear 양방향에서 작업이 수행됩니다.

값이 들어올 때는 rear 방향으로 쌓이고,

값이 나갈 때는 front의 자료가 먼저 나갑니다. 

생각해볼 문제는
값이 하나도 없을 때와

단 하나의 값만 있을 때.

front와 rear 이 같은 곳을 바라보고 있기 때문에 
이를 고려하여 구현하는 것이 중요한 것 같습니다. 

---

다양한 자료와 글을 참고하여 배우고 있는 개발 뉴비의 블로그입니다. 
수정 보완할 것이 있다면 부담없이 댓글 남겨주세요 :)

 

JavaScript 로 Queue 자료구조 구현하기