스택/큐

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.

1. 스택/큐란?

• 스택
  LIFO(Last In First Out)
  실 사용 예시 : 스택메모리, js 콜스택
• 큐
  FIFO(First In First Out)
  심화 : 원형 큐

3. 코테
   핵심 키워드 : 차례대로, 순서대로, 하나하나

   대표문제 
   - 올바른 괄호(쉬움)
   - 프린터(프로그래머스 고득점 kit lv 2)

   

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }

  peek() {
    return this.queue[this.front];
  }

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

function solution(priorities, location) {
  const queue = new Queue();
  for (let i = 0; i < priorities.length; i += 1) {
    queue.enqueue([priorities[i], i]);
  }

  priorities.sort((a, b) => b - a);

  let count = 0;
  while (true) {
    const currentValue = queue.peek();
    if (currentValue[0] < priorities[count]) {
      queue.enqueue(queue.dequeue());
    } else {
      const value = queue.dequeue();
      count += 1;
      if (location === value[1]) {
        return count;
      }
    }
  }
}

console.log(solution([1, 1, 9, 1, 1, 1], 1))

=> 스택/큐 코테에서 한가지 이슈가 있는데 큐를 구현하는 shift() 함수가 O(n)의 선형 시간이 걸린다는 점이다.
=> O(n)은 반복문과 함께 O(n^2)로 쉽게 진화할 여지가 있어 조심해서 써야한다.
=> 해결책은 위와 같이 list, likend list로 Queue를 직접 구현해 사용한다. (O(1) 상수 시간이 걸림)

심화 문제 : 다리를 지나는 트럭(프로그래머스 고득점 kit lv 2)