Javascript 자료구조 시리즈(3) Queue 대기열

Queue

큐는 FIFO(선입 선출) 원칙을 따르는 선형 데이터 구조입니다.
여기에는 1) 전면 포인터, 2) 후면 포인터, 두 개의 포인터가 포함됩니다.
앞쪽 포인터는 시작 요소의 주소를 포함하고 뒤쪽 포인터는 큐의 마지막 요소 주소를 포함합니다.
큐 구현에 사용되는 두 가지 주요 방법은 enqueue 및 dequeue 방법입니다.
Enqueuing은 큐에서 요소를 추가하는 프로세스이고 Dequeuing은 큐에서 요소를 제거하는 프로세스입니다.

 

전형적인 실생활의 Queue로 은행을 예를들 수 있습니다. 은행 업무를 보기위해 맨 처음 온 사람이 먼저 업무를 보고 그뒤에 순차적으로
업무를 보기 위해서 창구를 기다립니다.

또한 새로운 고객이 들어오면 가장 맨뒤에 서게 됩니다. 그리고 가장 맨 마지막에 업무를 보고 떠납니다.

 

여기서 가장 처음 온 고객이 Head가 되고 마지막에 온 고객이 Tail이 됩니다.

 

 

 

Enqueue & dequeue

 

Queue는 enqueue와 dequeue의 2가지 주요 작업을 지원합니다. 또한 peek, length 및 print 작업으로 유용하게 쓸 수 있습니다.

 

 

Alex라는 고객이 새로 들어오면 마지막 고객이 되고 Tail이 됩니다.

 

 

James라는 고객이 업무를 다 보고 나가면 dequeue가 됩니다. 가장 먼저 온 고객이 먼저 나가는 FIFO구조 입니다.

 

 

length는 남아있는 사람의 수 라고 보시면 되겠습니다.

 

 

 

이제 코드로 어떻게 표현되는지 한번 보실까요? 우선 Queue Class를 만들어 줍니다.

class Queue {
  constructor() {
    this.items = {}
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  /*
  Queue는 enqueue와 dequeue의 2가지 주요 작업을 지원합니다. 또한 peek, length 및 print 작업으로 유용하게 쓸 수 있습니다.
  */

  /*
  Enqueue 작업
  enqueue 작업은 대기열의 맨 뒤에 요소를 삽입합니다. 대기열에 넣은 요소는 대기열의 tail이 됩니다.
  */
  enqueue(item) {
    this.items[this.tailIndex] = item
    this.tailIndex++
  }

  /*
  Dequeue 작업
  Queue에서 dequeue 작업은 대기열의 맨 앞에 있는 요소를 추출합니다. 추출한 요소의 다음 요소가 head가 됩니다.
  */
  dequeue() {
    const item = this.items[this.headIndex]
    delete this.items[this.headIndex]
    this.headIndex++
    return item;
  }

  /*
  Peek 작업
  peek 작업은 대기열을 변경하지 않고 대기열의 head를 반환합니다.
  */
  peek() {
    return this.items[this.headIndex];
  }

  /*
  Queue length
  length 연산은 큐에 포함된 항목 수를 계산합니다.
  */
  get length() {
    return this.tailIndex - this.headIndex
  }

  /*
  Queue 출력
  현재 que.
  */
  print() {
    console.log('Queue items : ', this.items);
  }
}

 

그리고 구현된 Queue Class를 사용해봅니다.

const queue = new Queue()

queue.enqueue('James')
queue.enqueue('Emma')
queue.enqueue('Olivia')
queue.enqueue('Isabella')
queue.enqueue('Alex')
queue.print()
queue.dequeue()
queue.print()
console.log('queue.peek() : ',queue.peek());
console.log('queue.length : ',queue.length);

/*
LOG RESULTS
 Queue items :  {0: 'James', 1: 'Emma', 2: 'Olivia', 3: 'Isabella', 4: 'Alex'}
 Queue items :  {1: 'Emma', 2: 'Olivia', 3: 'Isabella', 4: 'Alex'}
 queue.peek() :  Emma
 queue.length :  4
 */