1-5 스택·큐·힙 · JUNSEOK CS study

LIFO, FIFO, 우선순위. 세 개의 "줄 서기" 방식이 알고리즘의 절반을 설명한다. MinHeap을 배열로 직접 구현할 수 있어야 통과.

0. 세 자료구조를 한 그림으로 — 초심자용

0-1. 공통점과 차이

셋 다 "데이터를 하나씩 넣고 하나씩 꺼내는" 자료구조다. 어떤 순서로 꺼내느냐가 다르다.

이름	꺼내는 규칙	일상 비유
스택(Stack)	가장 최근에 넣은 것부터	책상 위 책 쌓기. 위에 올린 책부터 꺼냄
큐(Queue)	가장 먼저 넣은 것부터	줄 서기. 먼저 온 사람부터 서빙
힙(Heap)	가장 우선순위 높은 것부터	응급실 순서. 먼저 왔어도 중증 환자가 먼저

0-2. 두 줄 약어

LIFO (Last In, First Out) = 스택
FIFO (First In, First Out) = 큐
힙은 약어가 아니고 "우선순위 큐(Priority Queue)"라고도 불린다

0-3. 이게 왜 중요한가

프론트 개발자가 매일 쓰는 것들이 사실 이 자료구조다 (안 보일 뿐).

스택: 브라우저 뒤로가기(history), 함수 호출의 Call Stack, undo 기능
큐: 이벤트 루프의 Task Queue (2-6), 작업 대기열
힙: 메모리 할당(Heap 메모리), 타이머 관리, 최상위 N개 뽑기

0-4. 이 장의 도달점

셋을 직접 코드로 구현할 수 있어야 한다. 특히 힙은 라이브러리 없이는 JS에 없어서, 코딩 테스트에서 거의 반드시 나온다.

1. 스택 (Stack, LIFO)

1-1. 정의

후입선출 (Last In, First Out). 책상 위의 책 쌓기. 가장 나중에 올린 것이 가장 먼저 내려간다.

1-2. JS로 스택

배열의 push/pop이 둘 다 O(1)이므로 JS에선 배열이 곧 스택이다.

const stack = [];
stack.push(1);     // [1]
stack.push(2);     // [1, 2]
stack.pop();       // 2, stack = [1]
stack[stack.length - 1];  // peek: 1

1-3. 실전 1: 괄호 검증

function isValidParens(s) {
  const pair = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);
    else if (pair[ch]) {
      if (stack.pop() !== pair[ch]) return false;
    }
  }
  return stack.length === 0;
}
isValidParens("({[]})");   // true
isValidParens("([)]");     // false

1-4. 실전 2: Undo/Redo

두 개의 스택으로 구현.

class History {
  constructor() { this.undo = []; this.redo = []; }

  execute(command) {
    this.undo.push(command);
    this.redo = [];   // 새 액션 후 redo 스택 비움
  }

  undoLast() {
    const c = this.undo.pop();
    if (c) this.redo.push(c);
    return c;
  }

  redoLast() {
    const c = this.redo.pop();
    if (c) this.undo.push(c);
    return c;
  }
}

1-5. 실전 3: 콜 스택

JS 엔진 자체가 함수 호출 스택을 관리한다. 재귀가 깊어지면 Maximum call stack size exceeded가 뜨는 이유. Chrome V8에서 대략 10000 ~ 15000 프레임.

1-6. 실전 4: 브라우저 히스토리

history.back()은 두 개의 스택 구조. 현재 페이지 스택 + forward 스택.

2. 큐 (Queue, FIFO)

2-1. 정의

선입선출 (First In, First Out). 대기줄. 먼저 온 사람이 먼저 나간다.

2-2. ⚠️ JS 배열로 큐를 만들면 O(n)

const queue = [];
queue.push(1);
queue.shift();   // O(n)! 뒤의 원소 전부 앞으로 밀림

수만 개 이상을 처리하면 shift가 병목이 된다.

2-3. 해결책 1: 인덱스 큐

shift 대신 head 포인터를 증가시킨다.

class Queue {
  constructor() { this.items = []; this.head = 0; }
  enqueue(v) { this.items.push(v); }
  dequeue() {
    if (this.head >= this.items.length) return undefined;
    const v = this.items[this.head++];
    if (this.head > 50 && this.head * 2 > this.items.length) {
      this.items = this.items.slice(this.head);
      this.head = 0;
    }
    return v;
  }
  get size() { return this.items.length - this.head; }
}

주기적으로 배열을 압축하지 않으면 메모리가 계속 커진다.

2-4. 해결책 2: 연결 리스트

앞/뒤 포인터를 유지하면 enqueue/dequeue 모두 O(1).

2-5. 실전: BFS의 기본 자료구조

function bfs(start, graph) {
  const queue = new Queue();
  const visited = new Set();
  queue.enqueue(start);
  visited.add(start);
  while (queue.size > 0) {
    const node = queue.dequeue();
    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.enqueue(next);
      }
    }
  }
}

2-6. 실전: 이벤트 루프

JS 런타임은 태스크 큐와 마이크로태스크 큐를 유지한다. setTimeout은 태스크 큐에, Promise.then은 마이크로태스크 큐에 들어간다. (2단계에서 심화)

3. 덱 (Deque, Double-Ended Queue)

3-1. 정의

양 끝에서 삽입/삭제 모두 O(1).

3-2. 실전: 슬라이딩 윈도우 최댓값

크기 k 윈도우 안의 최댓값을 매 위치마다 구한다. 덱에 인덱스를 저장, 새 원소보다 작은 꼬리 원소들을 제거해 단조 감소 유지.

function slidingMax(arr, k) {
  const deque = [];   // 인덱스 저장, 값은 arr[deque[0]]
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    // 1. 윈도우 벗어난 인덱스 제거
    while (deque.length && deque[0] <= i - k) deque.shift();
    // 2. 새로 온 값보다 작은 꼬리 제거
    while (deque.length && arr[deque[deque.length - 1]] < arr[i]) deque.pop();
    deque.push(i);
    // 3. 윈도우 완성되면 답에 추가
    if (i >= k - 1) result.push(arr[deque[0]]);
  }
  return result;
}
slidingMax([1, 3, -1, -3, 5, 3, 6, 7], 3);  // [3, 3, 5, 5, 6, 7]

각 원소는 덱에 한 번 들어가고 한 번 나온다 → O(n).

4. 힙 (Heap)과 우선순위 큐

4-1. 정의

완전 이진 트리 + 힙 속성.

완전 이진 트리: 마지막 레벨 제외 전부 채워짐, 마지막 레벨은 왼쪽부터 채움
MinHeap: 부모 ≤ 자식 (루트가 최솟값)
MaxHeap: 부모 ≥ 자식 (루트가 최댓값)

4-2. 배열 기반 표현

완전 이진 트리는 배열에 순서대로 담으면 낭비 없이 표현된다.

        1         인덱스 0
       / \
      3   2       1, 2
     / \ /
    5  4 8        3, 4, 5

부모-자식 관계 공식:

부모: (i - 1) >> 1
왼쪽 자식: 2i + 1
오른쪽 자식: 2i + 2

4-3. MinHeap 구현

class MinHeap {
  constructor() { this.heap = []; }

  push(val) {
    this.heap.push(val);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 0) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._sinkDown(0);
    }
    return top;
  }

  peek() { return this.heap[0]; }
  get size() { return this.heap.length; }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _sinkDown(i) {
    const n = this.heap.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let smallest = i;
      if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
      if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
      if (smallest === i) break;
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

4-4. 동작 시각화

push(5):  [5]
push(3):  [3, 5]          ← 3이 5보다 작아 위로
push(8):  [3, 5, 8]
push(1):  [1, 3, 8, 5]    ← 1이 5와 스왑, 다시 3과 스왑
push(6):  [1, 3, 8, 5, 6]

pop():    1 반환
  마지막 6을 루트로: [6, 3, 8, 5]
  6 > 3이므로 3과 스왑: [3, 6, 8, 5]
  6 > 5이므로 스왑: [3, 5, 8, 6]
  ← 최종

4-5. 복잡도

연산	복잡도
`push`	O(log n)
`pop`	O(log n)
`peek`	O(1)
`heapify` (배열 → 힙)	O(n)

heapify가 O(n)인 이유: 리프 노드부터 거꾸로 sinkDown을 실행하면, 위로 갈수록 노드 수가 절반씩 줄어든다. 수학적으로 n × (1/2 × 1 + 1/4 × 2 + ...) ≈ 2n.

4-6. 실전: Top-K

상위 K개를 구할 때 전체 정렬(O(n log n))보다 크기 K인 MinHeap 유지가 빠르다.

function topK(arr, k) {
  const heap = new MinHeap();
  for (const v of arr) {
    heap.push(v);
    if (heap.size > k) heap.pop();
  }
  return [...heap.heap].sort((a, b) => b - a);
}

복잡도: O(n log k). n=10⁶, k=10이면 대략 2 × 10⁷. 전체 정렬은 2 × 10⁷. 비슷하지만 메모리를 O(k)만 쓴다는 장점이 크다.

4-7. 실전: 다익스트라 / A*

최단 경로 알고리즘의 핵심. "지금까지 가장 거리 짧은 노드"를 꺼내는 연산을 O(log V)에 수행. (1-7 챕터에서 심화)

4-8. 실전: 이벤트 스케줄러

브라우저 setTimeout은 timer queue를 유지하는데, 만료 시각 기준 MinHeap을 쓰는 엔진이 많다 (Node.js libuv 포함). 매 틱마다 "가장 먼저 만료될 타이머"를 O(log n)에 꺼낼 수 있기 때문.

5. JS에 내장된 힙이 없다

Java의 PriorityQueue, Python의 heapq에 해당하는 내장이 JS엔 없다. 항상 직접 구현하거나 라이브러리를 써야 한다 (@js-sdsl/priority-queue, heap-js).

면접과 코테에서는 배울 내용 중 하나로 간주된다. 위 클래스는 외워두는 것이 좋다.

연습 문제

스택으로 "3 + 4 * 2" (중위식)을 "3 4 2 * +" (후위식)으로 변환하라.
JS 배열로 큐를 만들면 왜 O(n)인지, head 포인터 버전이 왜 O(1)인지 설명하라.
덱을 써서 크기 K 슬라이딩 윈도우의 최솟값을 O(n)에 구하라.
MinHeap을 직접 구현하고, [7, 2, 5, 1, 8, 3]을 push 순서대로 넣었을 때 pop 4번의 결과와 배열 상태를 추적하라.
Top-K 문제를 MinHeap 버전과 정렬 버전 양쪽으로 구현하고 복잡도를 비교하라.
다익스트라에서 왜 MaxHeap이 아닌 MinHeap을 쓰는지 설명하라.

연습 문제 정답

1. 중위 → 후위

function infixToPostfix(expr) {
  const precedence = { '+': 1, '-': 1, '*': 2, '/': 2 };
  const output = [];
  const ops = [];
  for (const token of expr.split(/\s+/)) {
    if (/\d+/.test(token)) output.push(token);
    else {
      while (ops.length && precedence[ops[ops.length - 1]] >= precedence[token]) {
        output.push(ops.pop());
      }
      ops.push(token);
    }
  }
  while (ops.length) output.push(ops.pop());
  return output.join(' ');
}
infixToPostfix("3 + 4 * 2");  // "3 4 2 * +"

2. 큐 O(n) → O(1)

Array.shift는 모든 뒤 원소를 한 칸씩 앞으로 이동시켜 O(n). head 포인터 방식은 인덱스만 증가시키므로 O(1). 대신 주기적으로 배열을 압축해야 메모리 누수가 없다.

3. 슬라이딩 윈도우 최솟값

function slidingMin(arr, k) {
  const deque = [];
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    while (deque.length && deque[0] <= i - k) deque.shift();
    while (deque.length && arr[deque[deque.length - 1]] > arr[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(arr[deque[0]]);
  }
  return result;
}

단조 감소 대신 단조 증가를 유지하면 된다.

4. MinHeap 추적

push(7): [7]
push(2): [2, 7]
push(5): [2, 7, 5]
push(1): [1, 2, 5, 7]
push(8): [1, 2, 5, 7, 8]
push(3): [1, 2, 3, 7, 8, 5]

pop(): 1 → [2, 7, 3, 5, 8] (5를 루트에 놓고 내려보냄)
pop(): 2 → [3, 5, 8, 7]
pop(): 3 → [5, 7, 8]
pop(): 5 → [7, 8]

5. Top-K

MinHeap 버전: O(n log k), 메모리 O(k)
정렬 버전: O(n log n), 메모리 O(n)

k가 n보다 훨씬 작을 때 MinHeap이 유리하다.

6. 다익스트라에서 MinHeap

매 단계마다 "지금까지 발견된 최단 거리가 가장 작은 노드"를 확장해야 한다. 최솟값 추출이 반복되므로 MinHeap.

MaxHeap은 "가장 큰 것부터" — 다익스트라의 요구와 반대다.

체크리스트

이전: 1-4. 배열·문자열·해시 | 다음: 1-6. 연결 리스트·트리·그래프