Data Structure - Queue

 Queue 

• ‘줄을 서다’ 라는 뜻으로
• FIFO, First Input First Out 먼저 들어간 것이 먼저 나오는 선입선출의 자료구조다.
• 여러 이벤트가 발생했을 때, 작업을 순서대로 처리해야 할 때 Queue가 사용된다.
• enqueue : 맨 뒤의 데이터 추가 , dequeue : 맨 앞의 데이터 제거
• JavaScript shift( )메서드 또는 배열을 사용해 구현 가능하다.

스택 이미지 출처 https://velog.io/@soor/Data-structure-stack-queue

 

 JavaScript로 Queue 구현하기 

class Queue {
  items = [];
  front = 0;
  rear = 0;

  enqueue(item) {
    this.items.push(item);
    this.rear++;
    console.log(`Enqueue: ${item} - Queue: [${this.items}]`);
  }

  dequeue() {
    if (this.front === this.rear) {
      console.log("Queue is empty");
      return;
    }
    const item = this.items[this.front];
    this.front++;
    console.log(`Dequeue: ${item} - Queue: [${this.items.slice(this.front)}]`);

    return item;
  }
 
  size() {
    return this.rear - this.front;
  }
}

const queue = new Queue();
queue.enqueue(1); // 1
queue.enqueue(3); // 1,3
queue.enqueue(4); // 1,3,4
queue.enqueue(7); // 1,3,4,7
queue.dequeue();  // 3,4,7
queue.dequeue();  // 4,7

 

 

 요세푸스 문제  

( 코딩테스트 합격자되기 BOOK - 자바스크립트 편 ) 
N명의 사람이 원 형태로 서 있습니다. 각 사람은 1부터 N까지 번호표를 갖고 있습니다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앱니다

• 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앱니다
• 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.

N과 K가 주어질 때 마지막에 살아있는 사람의 번호를 반환하는 solution()함수를 구현해주세요

// 제약 조건
N과 K는 1이상 1000이하의 자연수입니다

// 입출력 예
N = 5
K = 2
return 3

원 형태로 서 있다고 했지만 배열에서 충분히 문제를 풀 수 있다.

• N명의 사람을 배열에 push한다.
• K번째 사람을 지운다.
  • queue배열의 K-1을 제거하면 K번째 사람이 맨 앞으로 오게 된다. 이를 제거한다
  • K번째 사람을 찾는다. K-1까지의 데이터를 front에서 지우고 rear에 추가한다.
  • K번째를 지운다. 위 과정을 N의 개수가 1개 남을 때까지 계속한다.
• ⇒ queue로 구현하게 된다면 , K번째 사람이 맨 앞으로 오도록 만들어야 한다

const N = 5
const K = 2

function solution(N,K){
	// N명의 사람을 배열에 넣는다
	const queue = new Queue()
	  for (let i = 1; i <= N; i++) {
    queue.enqueue(i);
  }
  
  while (queue.size() > 1) {
  for (let i = 0; i < K - 1; i++) {
    const moved = queue.dequeue();
    queue.enqueue(moved);
    console.log(`이동된 데이터 : ${moved}`);
  }
  const removed = queue.dequeue();
  console.log(`제거된 데이터 : ${removed}`);
	}
  const lastReminding = queue.dequeue();
  console.log(`마지막 남은 데이터 : ${lastReminding}`);
  return lastReminding;
}