Queue

2019-02-18 devychdatastructure

이전 글에서 Stack을 이야기했고, 이번에는 Queue에 대해서 적어볼까해요.

Queue란?

Queue도 Stack과 마찬가지로 선형 자료구조에 속해요.

다만 Queue가 Stack과 다른점이라면 먼저 들어온 놈이 먼저 나간다는 것?

아래 그림을 보고가면 이해가 편할 것 같아요.

일상생활에서 찾아볼 수 있는 예로 놀이공원에서 놀이기구를 타기위해 기다리는 줄과 비슷하죠?

1번이라는 사람이 먼저 줄을 섰으니까 먼저 놀이기구를 타고 떠나는거죠.

이러한 부분을 FIFO(First In First Out)이라고 하고 우리나라 말로는 ‘선입선출’이라고 하면 되겠네요.

그러면 Queue도 JavaScript로 Stack과 비슷한 형태를 구현해볼까요? 근데 Queue는 Stack과 달리 조금 헷갈렸어요. 그림도 그리고 자필로 메모도 적었는데 헷갈렸어요…..바보죠

먼저 Queue는 마지막에 엘리먼트를 추가하는 enqueue, 가장 먼저들어온 엘리먼트를 방출하는 dequeue 메소드가 필요하겠네요.

//먼저 앞서 작성한 스택과 동일하게 새로운 Queue 클래스를 만들어줍시다.
const Queue = function() {
  this.storage = {}; //저장소이구요
  this.enqueNum = 0; //엘리먼트가 마지막에 추가될때마다 늘어나는 숫자가 될거에요.
  this.dequeNum = 0; //가장 앞에있는 엘리먼트가 방출될때마다 하나씩 증가할거에요.
};
Queue.prototype.enqueue = function(value) {
  this.storage[this.enqueNum] = value; //enqueNum을 키로 가지는 밸류를 저장해요
  this.enqueNum++; // 그리고 enqueNum을 증가시켜서 다음번 실행을 기다려요.
};
Queue.prototype.dequeue = function() {
  //만약 방출할게 없거나, dequeNum이 enqueNum보다 같거나 커지면 false를 리턴합니다.
  if (!this.storage || this.dequeNum >= this.enqueNum) {
    return false;
  }
  //그리고 가장 먼저 들어갔던 엘리먼트를 방출합니다.
  delete this.storage[this.dequeNum];
  //dequeueNum을 증가시켜서 다음 가장 앞에있는 값을 가리키도록 합니다.
  this.dequeNum++;
};

어때요? 참 쉽죠?

이걸로 큐에 관련 글 작성은 마무리 하겠습니다.