노트

큐

Queue

CS#algorithm · 연결된 개념 11개

쉽게 말하면

큐는 버스 정류장 줄이에요. 먼저 선 사람이 먼저 타고 새로 온 사람은 맨 뒤에 서니까, 작업이나 요청을 들어온 순서대로 공평하게 처리할 수 있어요.

비유의 한계 줄은 사람들이 알아서 한 칸씩 당겨 서지만, 배열에서 그 당기기는 공짜가 아니에요. shift는 남은 원소를 전부 당겨 O(n)이라, 시작 인덱스를 따로 두거나 연결 리스트로 O(1)을 만들어요.

먼저 넣은 것을 먼저 꺼내는(First In, First Out) 자료구조. 줄을 서듯 뒤에 넣고(enqueue) 앞에서 꺼낸다(dequeue).

구현할 때 주의

JavaScript 배열로 push + shift를 쓰면 shift가 남은 원소를 모두 앞으로 당겨 O(n)이 된다. 원소가 많다면 연결 리스트(head에서 꺼내고 tail에 넣기)나 시작 인덱스를 따로 들고 있는 방식으로 양쪽 모두 O(1)을 만든다.

class Queue<T> {
  private items: Record<number, T> = {}
  private head = 0
  private tail = 0
  enqueue(v: T) { this.items[this.tail++] = v }
  dequeue() {
    if (this.head === this.tail) return undefined
    const v = this.items[this.head]
    delete this.items[this.head++]
    return v
  }
}

어디에 쓰나

  • 너비 우선 탐색: 가까운 노드부터 방문하려고 큐를 쓴다
  • 작업 대기열: 브라우저의 태스크 큐(Task Queue)와 마이크로태스크 큐, 서버의 백그라운드 작업 큐, 서비스 사이의 메시지 큐(Kafka)
  • 인쇄 대기, 요청 버퍼링

먼저 꺼낼 순서를 도착 순서가 아니라 우선순위로 정하면 우선순위 큐가 된다. 반대 구조는 스택.

책: 4장. 큐와 BFS: 가까운 곳부터

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 재귀

    함수가 자기 자신을 다시 호출해 문제를 푸는 방식. 같은 함수를 점점 작은 입력으로 부르다가 더 나눌 필요가 없는 지점(기저 조건, Base Case)에서 멈춘다.

  • 이진 힙

    부모가 항상 자식보다 크거나(최대 힙, Max Heap) 작은(최소 힙, Min Heap) 완전 이진 트리(Complete Binary Tree). 형제끼리의 순서는 정하지 않는다. 가장 크거나 작은 값이 항상 루트에 있어 꺼내기 쉽다.

  • 퀵 정렬

    기준값(피벗, Pivot)을 하나 골라 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 뒤, 양쪽을 다시 같은 방식으로 정렬하는 알고리즘. 나누고 나면 피벗은 최종 자리에 놓이므로 합치는 단계가 필요 없다.

  • 정렬 알고리즘

    컬렉션의 원소를 어떤 순서(크기, 사전순, 날짜…)로 다시 배치하는 알고리즘. 같은 일을 하는 방법이 여럿이고 각자 강점이 달라, 트레이드오프를 익히기 좋은 주제다.

  • 운영 Node 프로세스의 메모리 누수 찾기

    살아 있는 Node 서버에 inspector를 붙이고, 힙 스냅샷 두 장을 비교해 무엇이 쌓이는지, retainer로 누가 붙잡고 있는지 찾는 절차.

보기 옵션