TIL: 자료구조 | 큐 (queue)

선입선출 원리에 따라 정렬된 컬렉션

큐를 구현할 때 배열을 사용해도 크게손해는 아니지만..
객체로 구현할 수 있다

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

  getStorage() {
    return this.#storage
  }

  reset() {
    if (this.#front === this.#rear) {
      this.#front = 0
      this.#rear = 0
    }
  }

  size() { // 컬렉션에서는 length 보다는 size 라는 용어를 사용한다
    return Math.abs(this.#rear - this.#front)
  }

  enqueue(value) {
    this.reset()
    this.#storage[++this.#rear] = value
  }

  dequeue() {
    this.reset()
    const temp = this.#storage[++this.#front]
    delete this.#storage[this.#front]
    return temp
  }
}

const queue = new Queue()

queue.add(2)
console.log(queue.getStorage())
console.log(queue.popLeft())
console.log(queue.popLeft())
console.log(queue.getStorage())

우선순위 큐

큐애서 dequeue 되는 순서에 분류별로 우선순위를 주어
우선순위가 높은것 먼저 사용되도록 하는 방식

마이크로 태스크 큐와 태스크 큐 같은 느낌

class QueueElement {
	constructor(element, priority) {
    	this.element = element
      	this.priority = priority
    }
}

class PriorityQueue {
	constructor() {
      this.arr = []
    }
  
  	isEmpty() {
    	return this.arr.length === 0
    }
  	
  	enqueue(element, priority) {
    	const queueElement = new QueueElement(element, priority)
     	if (this.isEmpty()) this.arr.push(queueElement)
      	else {
        	let isAdded = false
            const len = this.arr.length
           	for (let i=0; i<len; i++) {
            	if (queueElement.quriority < this.arr[i].priority) {
                	this.arr.splice(i, 0,  queueElement)
                  	isAdded = true
                  	break
                }
            }
          	if (!isAdded) this.arr.push(queueElement)
        }
      	
    }
  // 다른 메서드는 일반 큐와 동일
}

환형 큐

뜨거운 감자 게임
일정 횟수 반복 후 걸리는 사람은 한 제거되고
최후의 1인이 승리하는 게임
dequeue 를 한 데이터를 enqueue 하다가 일정 횟수에 도달하면 enqueue 를
안하는 방식으로..??