[JS|자료구조] 자바스크립트(javascript)의 Queue(큐) 알아보기

 

- Queue 란?

 

FIFO (First In First Out)
가장 먼저 들어온 데이터가 가장 먼저 나가는 형태.
즉, 양방향으로 데이터를 넣고 뺄 수 있다.

 

front 변수를 사용하여 데이터를 삽입하기에 복잡도는 O(1)이다.

데이터 삭제의 복잡도 또한 O(1)이지만, 자바스크립트에서는 주의해야할 점이 있다.

자바스크립트에 있는 Array의 shift() 메소드를 사용하면 첫 번째에 있는 데이터를 삭제하여 O(1)처럼 보이지만, 두 번째 데이터부터 맨 끝까지 정렬하기에 O(n)의 복잡도를 가진다.

따라서 front 변수와 rear 변수를 사용하여 데이터 삭제를 해줘야 O(1)의 처리를 할 수 있다.

 

---

- Queue의 ADT 연산 정의

0. Queue의 구조

function Queue(array = new Array()) {
  this.arr = array
  this.front = 0
  this.rear = 0
}

1. Queue의 데이터 삽입

Queue.prototype.push = function (data) {
  this.arr[this.rear++] = data
}

2. Queue의 데이터 삭제

Queue.prototype.pop = function () {
  return this.arr[this.front++]
}

3. Queue가 비어있는지 확인

Queue.prototype.isEmpty = function () {
  return this.rear === this.front
}

 

Queue 전체 코드

function Queue(array = new Array()) {
  this.arr = array
  this.front = 0
  this.rear = 0
}
Queue.prototype.push = function (data) {
  this.arr[this.rear++] = data
}
Queue.prototype.pop = function () {
  return this.arr[this.front++]
}
Queue.prototype.isEmpty = function () {
  return this.rear === this.front
}
Queue.prototype.next = function () {
  return this.arr[this.front]
}
Queue.prototype.head = function () {
  return this.arr[0]
}

 

 

---

Queue 관련 문제 풀이

1. 기능 개발

프로그래머스

 

function Queue(array = new Array()) {
  this.arr = array
  this.front = 0
  this.rear = 0
}
Queue.prototype.push = function (data) {
  this.arr[this.rear++] = data
}
Queue.prototype.pop = function () {
  return this.arr[this.front++]
}
Queue.prototype.isEmpty = function () {
  return this.rear === this.front
}
Queue.prototype.next = function () {
  return this.arr[this.front]
}
Queue.prototype.head = function () {
  return this.arr[0]
}

function solution(progresses, speeds) {
  var answer = []
  let queue = new Queue()

  progresses.map((progress, idx) =>
    queue.push(Math.ceil((100 - progress) / speeds[idx]))
  )

  let maxVal = queue.head()
  let cnt = 0
  while (!queue.isEmpty()) {
    let val = queue.pop()

    if (maxVal >= val) cnt++
    else {
      answer.push(cnt)
      maxVal = val
      cnt = 1
    }
  }

  if (cnt > 0) answer.push(cnt)

  return answer
}

 

---

2. 카드 뭉치

프로그래머스

 

function Queue(array = new Array()) {
  this.arr = array
  this.front = 0
  this.rear = 0
}
Queue.prototype.push = function (data) {
  this.arr[this.rear++] = data
}
Queue.prototype.pop = function () {
  return this.arr[this.front++]
}
Queue.prototype.head = function () {
  return this.arr[this.front]
}
Queue.prototype.isEmpty = function () {
  return this.front === this.rear
}

function solution(cards1, cards2, goal) {
  let queue1 = new Queue()
  let queue2 = new Queue()
  cards1.map((card) => queue1.push(card))
  cards2.map((card) => queue2.push(card))

  for (let i = 0; i < goal.length; i++) {
    let target = goal[i]
    if (target === queue1.head()) queue1.pop()
    else if (target === queue2.head()) queue2.pop()
    else return 'No'
  }

  return 'Yes'
}