제 8 장 · Elegant Code with Stacks and Queues

스택과 큐로 우아한 코드

스택과 큐는 완전히 새로운 자료구조가 아니다. 제약이 있는 배열일 뿐이다. 그러나 바로 그 제약이 이들을 우아하게 만든다 — LIFO와 FIFO.

스택 큐 LIFO FIFO 린터

§ 1 · 처리하고 버린다임시 데이터

스택과 큐는 임시 데이터(temporary data)를 다루는 우아한 도구다. 임시 데이터는 식당의 음식 주문과 같다 — 음식이 만들어져 제공되면 주문서를 버린다.

처리된 후에는 의미가 없는 정보지만, 처리하는 순서는 중요할 수 있다. 식당은 이상적으로 요청된 순서대로 음식을 만든다. 스택과 큐는 데이터를 순서대로 처리하고, 더 이상 필요 없으면 제거하게 해준다.

§ 2 · 접시 더미스택 — LIFO

스택(stack)은 배열처럼 요소의 목록이지만 세 가지 제약이 있다.

Constraints스택의 세 가지 제약

① 삽입 — 데이터는 스택의 끝(맨 위)에만 넣을 수 있다. 이를 푸시(push)라 한다.

② 읽기 — 데이터는 스택의 끝에서만 읽을 수 있다.

③ 삭제 — 데이터는 스택의 끝에서만 제거할 수 있다. 이를 팝(pop)이라 한다.

스택은 실제 접시 더미와 같다. 맨 위 접시만 보이고, 맨 위에만 올릴 수 있고, 맨 위만 치울 수 있다. 약어는 LIFO — Last In, First Out(후입선출). 마지막에 푸시된 항목이 가장 먼저 팝된다.

모션 · 스택의 push와 pop (LIFO) 단계 01 / 0

space 재생 · → 단계 · R 리셋

§ 3 · 괄호 검사스택으로 만든 린터

스택의 우아함을 보여주는 예 — JavaScript 린터(linter)의 괄호 검사. 여는 괄호를 만나면 스택에 푸시하고, 닫는 괄호를 만나면 스택 맨 위와 짝이 맞는지 확인한다.

모션 · 스택으로 괄호 짝 검사 단계 01 / 0

space 재생 · → 단계 · R 리셋

린터의 핵심 — Ruby

def lint(text)
  text.each_char.with_index do |char, index|
    if opening_brace?(char)
      # 여는 괄호 → 스택에 푸시
      @stack.push(char)
    elsif closing_brace?(char)
      if closes_most_recent_opening_brace?(char)
        @stack.pop                    # 짝이 맞으면 팝
      else
        @error = "Incorrect closing brace"
        return
      end
    end
  end
  if @stack.any?
    @error = "#{@stack.last} does not have a closing brace"
  end
end

핵심 스택은 수신된 순서와 반대로 처리해야 하는 모든 데이터에 이상적이다(LIFO). 워드 프로세서의 "실행 취소" 기능, 함수 호출 추적이 그 예다.

§ 4 · 영화관 줄큐 — FIFO

큐(queue)도 제약이 있는 배열이지만, 제약 세트가 다르다. 큐는 영화관의 줄과 같다 — 먼저 선 사람이 먼저 들어간다. 약어는 FIFO — First In, First Out(선입선출).

Constraints큐의 세 가지 제약

① 삽입 — 데이터는 큐의 끝에만 넣는다(스택과 동일). 이를 인큐(enqueue)라 한다.

② 읽기 — 데이터는 큐의 앞에서만 읽는다(스택과 반대).

③ 삭제 — 데이터는 큐의 앞에서만 제거한다(스택과 반대). 이를 디큐(dequeue)라 한다.

모션 · 큐의 enqueue와 dequeue (FIFO) 단계 01 / 0

space 재생 · → 단계 · R 리셋

§ 5 · 인쇄 큐큐의 활용

큐는 인쇄 작업, 웹 애플리케이션의 백그라운드 작업에 흔히 쓰인다. 네트워크에서 인쇄 작업을 받는 프린터 인터페이스를 보자.

인쇄 큐 — Ruby

class PrintManager
  def initialize
    @queue = []
  end

  def queue_print_job(document)
    @queue.push(document)         # 끝에 추가 (enqueue)
  end

  def run
    while @queue.any?
      print(@queue.shift)         # 앞에서 제거 (dequeue)
    end
  end
end

세 문서를 받은 순서대로 인쇄한다. 큐는 비동기 요청을 받은 순서대로 처리하고, 이륙을 기다리는 비행기나 의사를 기다리는 환자처럼 특정 순서로 발생해야 하는 실제 시나리오를 모델링하는 데 완벽하다.

§ 6 · 정리이 장이 남긴 것

스택과 큐는 온갖 실용적 알고리즘을 우아하게 처리하는 프로그래머의 도구다. 그리고 스택을 이해했으니 새로운 성취를 잠금 해제했다 — 재귀다. 재귀는 스택에 의존하며, 책 나머지의 고급 알고리즘들의 기초가 된다.