이전 내용

‣

7. 큐

7-a. 큐(Queue)란?

First In First Out, 선입선출의 구조를 가진 선형 자료구조

큐의 특징

• 대기열의 특성과 같다.
• Dequeue로 원소가 나가는 “Front" 부분과 Enqueue로 원소가 들어오는 **“Rear"**로 구성

큐의 종류

선형 큐

1.배열을 통한 큐 구현

Queue를 구현할 경우, EnQueue와 DeQueue 시 비워진 공간을 매꾸기 위해 O(n)이 소요되기 때문에 추천되지 않는다.

// 직접 구현해보기
class Queue {

enqueue(){}
dequeue(){}
peek(){}
size(){}
}

2.링크드 리스트를 통한 구현

Head = Front, Tail = Rear로 대응하여 구현 가능

//직접 구현해보기
class Node{}
class Queue{
	enqueue(){}
	dequeue(){}
	peek(){}
	size(){}
}

참고 shift를 통해 간단히 구현가능하지만, 선형시간이 소요되기 때문에, 본질적인 큐의 구조와 다르다

환형 큐

Front와 Rear가 이어져있는 Queue

• 환형 큐는 js에서 사용되는 경우가 많지는 않다.

7-b. 실습

• 💻프린터 문제 큐를 이용하여 풀어보기

  문제이해

  • location에 해당하는 문서가 몇번째로 인쇄되는지 구하는 문제
  • 처음 로케이션이 2였다는 것을 어떻게 나중에 보장할 것인가 처리가 핵심
    • idx와 중요도를 묶어서 자료형을 바꿔줌 properties: [2,1,3,2] => [[0,2],[1,1],[2,3],[3,2]]
  • 현재 인쇄된 문서수(order)로 관리

  풀이방법

  • (pre) priorities를 [ [중요도, idx], [1,1], [3,2], [2,3] ] 로 파싱
  • 맨 앞 문서 추출 [2,0]
  • 나머지와 중요도 비교 2 vs 1, 3, 2 , isMostImportant()
  • 1. 제일 중요하다면 문서 인쇄하고, 인쇄순서(order) 1증가
    • 재귀탈출 만약 현재 인쇄순서(order)가 target위치(location)가 일치한다면 order리턴!
  • 2. 제일 중요하지 않다면 제일 뒤로 이동 [ [1,1], [3,2], [2,3], [2,0] ]
  • 재귀를 통한 반복 실행

  function solution(priorities, location) {
  let order = 0;
  priorities = priorities.map((p,i)=>[p,i])
  
  function isMostImportant(p, pList){
      pList = pList.map(p => p[0])
      return p >= Math.max(...pList);
  }
  // 재귀로 풀기
  function print(pList){
      let [p, l] = pList.shift()
      if(isMostImportant(p, pList)){
          order++
          if(l === location) return order
      } else {
          pList.push([p,l])
      }
      return print(pList)
  }
  return print(priorities)
  }
  

8. 해시 테이블

키와 값을 받아, 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조

해시함수란

입력받은 값을 특정 범위 내 숫자로 변경하는 함수

해시충돌