자바스크립트 queue 구현

우선 전체 코드는 이러하다.

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }
  peek() {
    return this.elements[this.head];
  }

  back() {
    return this.elements[this.tail - 1];
  }
  get length() {
    return this.tail - this.head;
  }
  get isEmpty() {
    return this.length === 0;
  }
}

Step 1

우선 생성자를 만들어준다. 

elements 는 변수를 저장할 것이고

head와 tail은 각각 queue의 head와 tail을 가르킬 것이다.

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  //...
}

 

Step 2

값을 추가하면 elements 에 값이 들어가고 tail 이 1 증가한다.

class Queue {
  //...
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }

  //...
}

그림으로 표현하면 다음과 같다.

https://carrotweb.tistory.com/191

 

Step 3

head 가 가르키는 요소 즉 앞쪽 요소를 제거하여 리턴하고 head 를 1 증가시킨다.

class Queue {

  // ...
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }

  //...
}

그림으로 설명하면 다음과 같다.

https://carrotweb.tistory.com/191

 

Step 4

가장 앞에 있는 요소는 head가 가르키고 있는 요소이다.

class Queue {
  //...
  peek() {
    return this.elements[this.head];
  }
  //...  
}

step 5 

back은 가장 뒤 tail-1 이 가르키고 있는 요소이다.

back() {
    return this.elements[this.tail - 1];
  }

Step 6

queue 의 길이는 tail - head 와 같다.

class Queue {
  //...
  get length() {
    return this.tail - this.head;
  }
  //...
}

 

Step 7

마지막으로 대기열이 비어있으면 true 를 반환하는 isEmpty를 만든다.

class Queue {
  // ...
  get isEmpty() {
    return this.tail - this.head;
  }
  // ... 
}

참고자료

https://www.javascripttutorial.net/javascript-queue/

JavaScript Queue

https://carrotweb.tistory.com/191

JavaScript Queue - 큐 만들기, Data Structures