노트

큐

Queue

CS#algorithm · 연결된 개념 9개

쉽게 말하면

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

비유가 깨지는 곳 줄은 사람들이 알아서 한 칸씩 당겨 서지만, 배열에서 그 당기기는 공짜가 아니에요. 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)
  • 인쇄 대기, 요청 버퍼링

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

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 재귀

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

  • 이진 힙

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

  • LRU 캐시와 캐시 계층 비교

    LRU(Least Recently Used) 캐시는 크기를 정해 두고, 가득 차면 가장 오랫동안 쓰지 않은 항목부터 버리는 메모리 캐시다. Node.js에서는 lru-cache 패키지가 대표적이다. 자주 쓰는 데이터는 계속 남고 안 쓰는 것만 밀려난다.

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

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

  • 정렬 알고리즘

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

보기 옵션