스택과 큐 활용: 뒤로 가기 이력과 작업 대기열

브라우저에서 A, B, C 페이지를 차례로 연 뒤 뒤로 가기를 누르면 B로 돌아가고, 앞으로 가기를 누르면 다시 C가 나옵니다. 그런데 B에서 D라는 새 페이지를 열면 앞으로 가기 버튼이 비활성화되어 더는 C로 갈 수 없습니다. 프린터는 이와 다르게 동작합니다. 인쇄를 요청한 순서대로 작업을 하나씩 처리하고, 나중에 요청한 작업이 먼저 요청한 작업을 앞지르지 않습니다.

ArrayDeque로 스택과 큐 다루기에서 배운 스택(stack)과 큐(queue)가 바로 이 두 동작입니다. 스택은 나중에 넣은 것을 먼저 꺼내고(LIFO, Last In First Out), 큐는 먼저 넣은 것을 먼저 꺼냅니다(FIFO, First In First Out). 이 글에서는 둘을 써서 브라우저 이력과 작업 대기열을 직접 만듭니다. 자료구조의 연산만 정확히 쓰면 끝날 것 같지만, 막상 만들어 보면 다른 질문이 더 중요해집니다. 새 페이지를 열면 앞으로 가기 이력을 어떻게 할지, 꺼낸 작업이 실패하면 그 작업을 어디에 둘지 같은 질문입니다.

ArrayDeque 하나로 스택과 큐를 모두 쓰기

이 글의 예제는 모두 ArrayDeque를 씁니다. 같은 클래스라도 어떤 메서드를 부르느냐에 따라 스택이 되기도 하고 큐가 되기도 하므로, 쓰기 전에 각 메서드가 어느 끝을 쓰는지 다시 확인하겠습니다.

push는 addFirst, pop은 removeFirst와 같아서 스택의 맨 위(top)가 덱의 앞쪽입니다. 그래서 스택으로 쓰는 ArrayDeque를 출력하면 맨 위의 원소부터 나열됩니다. 예를 들어 A, B, C를 차례로 push한 스택은 [C, B, A]로 출력됩니다. 반면 offer는 offerLast와 같아서 큐는 넣은 순서대로 [A, B, C]로 보입니다. 클래스 이름이 아니라 부르는 메서드가 동작을 정한다는 점을 기억해 두세요.

새 페이지를 열면 앞으로 가기 이력을 지워야 하는 이유

브라우저 이력은 스택 두 개로 만들 수 있습니다. 지나온 페이지를 쌓아 두는 back 스택과, 뒤로 가기로 빠져나온 페이지를 쌓아 두는 forward 스택입니다. 지금 보고 있는 페이지는 어느 스택에도 넣지 않고 current 변수에 따로 둡니다.

먼저 흔히 하는 실수부터 보겠습니다. 다음 코드는 A, B, C를 방문하고 뒤로 가기로 B에 온 다음 D를 방문하는 과정을 스택 연산으로 직접 적었습니다. 그런데 D를 방문할 때 forward를 비우지 않았습니다.

import java.util.ArrayDeque;
import java.util.Deque;

public final class StaleForwardHistoryBug {
    public static void main(String[] args) {
        Deque<String> back = new ArrayDeque<>(), forward = new ArrayDeque<>();
        String current = "A";
        back.push(current);
        current = "B";
        back.push(current);
        current = "C";
        forward.push(current);
        current = back.pop();
        back.push(current);
        current = "D";
        System.out.println("current=" + current + ", invalid-forward=" + forward.peek());
    }
}

current=D, invalid-forward=C

코드를 한 줄씩 따라가 보면, forward.push(current)와 current = back.pop() 두 줄이 C에서 뒤로 가기를 눌러 B로 돌아온 동작입니다. 그다음 B를 back에 넣고 D로 옮겨 간 것이 새 페이지 방문입니다. 그런데 출력을 보면 forward의 맨 위에 아직 C가 남아 있습니다. 이 상태에서 앞으로 가기를 누르면 D 다음 페이지로 C가 나옵니다. C는 B 다음에 방문했던 페이지이지 D 다음 페이지가 아니므로, 사용자가 실제로 지나온 길과 맞지 않는 이동입니다.

push와 pop은 하나도 틀리지 않았지만 결과는 틀렸습니다. 빠진 것은 '새 페이지를 방문하면 앞으로 가기 이력은 의미를 잃는다'는 기능의 규칙입니다. 그래서 방문 동작에는 forward.clear()가 반드시 포함되어야 합니다. 자료구조의 연산이 맞는 것과 기능이 맞는 것은 별개의 문제입니다.

두 스택으로 브라우저 이력 만들기

이제 규칙을 메서드로 묶어 보겠습니다. 동작은 세 가지입니다.

• 방문(visit): 현재 페이지를 back에 넣고, 새 페이지를 현재 페이지로 만든 뒤, forward를 비웁니다.
• 뒤로 가기(back): 현재 페이지를 forward에 넣고, back에서 꺼낸 페이지를 현재 페이지로 만듭니다.
• 앞으로 가기(forward): 뒤로 가기의 반대로, 현재 페이지를 back에 넣고 forward에서 꺼낸 페이지를 현재 페이지로 만듭니다.

뒤로 가기와 앞으로 가기는 꺼낼 스택이 비어 있으면 아무것도 바꾸지 않고 false를 돌려줍니다. 이동할 곳이 없는 것은 오류가 아니라 버튼이 비활성화된 정상 상태이기 때문입니다.

import java.util.ArrayDeque;
import java.util.Deque;

public final class BrowserHistory {
    public static void main(String[] args) {
        History h = new History("A");
        h.visit("B");
        h.visit("C");
        h.back();
        h.visit("D");
        System.out.println(h);
        System.out.println("forward=" + h.forward());
        h.back();
        h.back();
        System.out.println(h);
    }

    private static final class History {
        private final Deque<String> back = new ArrayDeque<>(), forward = new ArrayDeque<>();
        private String current;

        History(String home) {
            current = home;
        }

        void visit(String page) {
            back.push(current);
            current = page;
            forward.clear();
        }

        boolean back() {
            if (back.isEmpty()) return false;
            forward.push(current);
            current = back.pop();
            return true;
        }

        boolean forward() {
            if (forward.isEmpty()) return false;
            back.push(current);
            current = forward.pop();
            return true;
        }

        public String toString() {
            return "back=" + back + ", current=" + current + ", forward=" + forward;
        }
    }
}

back=[B, A], current=D, forward=[]
forward=false
back=[], current=A, forward=[B, D]

toString이 출력하는 두 스택은 앞에서 말한 대로 맨 위부터 나열됩니다. 호출마다 상태가 어떻게 바뀌는지 표로 따라가 보겠습니다.

출력의 첫 줄은 표의 다섯 번째 줄, 즉 D를 방문한 직후의 상태입니다. visit("D")가 forward를 비웠기 때문에 앞의 버그 코드와 달리 C가 남아 있지 않습니다. 둘째 줄의 forward=false는 비어 있는 forward에서 앞으로 가기를 시도했다가 거절된 결과이고, 세 상태 모두 그대로입니다. 마지막 두 번의 back()은 D에서 B로, B에서 A로 돌아가며 지나온 페이지를 forward에 쌓습니다. 그래서 셋째 줄에서 forward의 맨 위는 B이고, 앞으로 가기를 누르면 B, D 순서로 다시 나옵니다. back()의 반환값은 출력하지 않으므로 출력은 세 줄입니다.

이 마지막 상태에서 forward()를 세 번 더 호출하면 반환값은 차례로 true, true, false이고, current는 B, D, D가 됩니다. 세 번째 호출은 forward가 비어 있어서 아무것도 바꾸지 않습니다. 새 페이지를 방문할 때 forward를 비우는 것과, 빈 스택에서 이동을 거절하는 것은 서로 다른 규칙이라는 점을 구분해 두세요.

back()이 맨 먼저 back.isEmpty()를 검사하는 순서에도 이유가 있습니다. 검사 없이 forward.push(current)부터 하면, new History("A")로 만든 직후처럼 back이 비어 있을 때 다음 줄의 back.pop()이 NoSuchElementException을 던집니다. 그런데 그 전에 이미 현재 페이지를 forward에 넣었으므로 current=A와 forward=[A]가 동시에 남는 어긋난 상태가 됩니다. 상태를 바꾸기 전에 이동할 수 있는지부터 확인하면 이런 반쪽짜리 변경이 생기지 않습니다.

null 페이지를 막는 위치

ArrayDeque는 null을 원소로 받지 않아서 push(null)은 즉시 NullPointerException을 던집니다. 하지만 current는 스택 밖의 평범한 필드이므로 visit(null)은 아무 오류 없이 실행되고 current가 null이 됩니다. 문제는 그다음입니다. 이어서 back()이나 visit("Z")를 호출하면 null인 현재 페이지를 스택에 넣으려다 예외가 나는데, 예외가 난 곳은 null이 들어온 곳과 다른 호출입니다. 그래서 원인을 찾기 어렵습니다.

이 예제는 페이지 이름이 null이 아니라고 전제합니다. 외부 입력을 받는다면 생성자에서는 home을, visit에서는 page를 첫 줄에서 Objects.requireNonNull로 검사해, 상태를 바꾸기 전에 잘못된 값을 거절해야 합니다.

인쇄 대기열: 꺼낸 작업이 실패하면

이번에는 큐입니다. 인쇄 요청을 큐에 넣고, 앞에서부터 하나씩 꺼내 인쇄합니다. 여기서 생각해 볼 문제가 있습니다. poll()은 큐의 맨 앞 작업을 꺼내면서 큐에서 지웁니다. 그러니 꺼낸 작업이 인쇄에 실패하면 그 작업은 이미 큐에 없습니다. 이 순간 작업을 붙잡고 있는 것은 지역 변수 하나뿐이므로, 아무 처리도 하지 않고 다음 반복으로 넘어가면 작업이 그대로 사라집니다.

실패한 작업을 살리는 방법은 크게 두 가지입니다. 하나는 실패한 작업을 다시 큐에 넣는 것입니다. 다른 하나는 peek()으로 맨 앞 작업을 보기만 하고 처리한 뒤, 성공했을 때만 remove()로 지우는 것입니다. 두 번째 방법은 작업이 실패하는 동안 그 작업이 계속 맨 앞에 남아 뒤의 작업을 모두 막는다는 문제가 있습니다. 첫 번째 방법도 계속 실패하는 작업을 영원히 다시 넣을 수는 없으니, 몇 번까지 시도할지 한도를 정해야 합니다.

다음 예제는 첫 번째 방법을 씁니다. 작업마다 지금까지 실패한 횟수(attempts)를 들고 다니다가, 실패하면 횟수를 1 늘려 큐 뒤에 다시 넣습니다. 실패가 세 번째가 되면 더는 다시 넣지 않고 dead 목록으로 옮깁니다. 이렇게 자동 재시도를 포기한 작업을 따로 모아 두는 곳을 데드 레터(dead letter) 목록이라고 부르며, 나중에 사람이 원인을 확인하는 데 씁니다. print는 이름이 broken인 작업만 실패하는 가짜 함수이고 실제로 인쇄하지는 않습니다.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public final class PrinterRetryQueue {
    public static void main(String[] args) {
        Deque<Job> pending = new ArrayDeque<>();
        pending.add(new Job("notes", 0));
        pending.add(new Job("broken", 0));
        List<String> done = new ArrayList<>(), dead = new ArrayList<>();
        while (!pending.isEmpty()) {
            Job job = pending.poll();
            if (print(job)) {
                done.add(job.name());
                continue;
            }
            Job retried = new Job(job.name(), job.attempts() + 1);
            if (retried.attempts() >= 3) dead.add(job.name());
            else pending.offer(retried);
        }
        System.out.println("done=" + done + ", dead=" + dead);
    }

    private static boolean print(Job job) {
        return !job.name().equals("broken");
    }

    private record Job(String name, int attempts) {}
}

done=[notes], dead=[broken]

Job은 불변 record이므로 실패 횟수를 늘릴 때는 attempts를 바꾸는 대신 횟수가 1 많은 새 Job을 만듭니다. 반복문 안에서 꺼낸 작업은 세 곳 중 한 곳으로만 갑니다. 성공하면 done으로, 실패 횟수가 한도에 못 미치면 pending의 뒤로, 한도에 닿으면 dead로 갑니다. 세 곳 가운데 어디에도 들어가지 않고 사라지는 작업은 없습니다. 루프는 isEmpty()를 먼저 확인하므로 poll()이 빈 큐에서 null을 돌려주는 경우도 생기지 않습니다.

broken(n)의 n은 꺼내기 전까지 쌓인 실패 횟수입니다. 처음 만든 작업은 아직 한 번도 실패하지 않았으므로 0에서 시작합니다. 최대 시도 횟수 3은 처음 시도 1번과 재시도 2번을 합한 것입니다. 세 번째 실패에서 횟수가 3이 되면 dead로 옮기므로, 횟수가 3인 작업을 다시 인쇄하는 일은 없습니다.

다시 넣은 작업은 다른 작업 뒤로 간다

실패한 작업을 큐의 뒤에 넣으므로, 실패와 재시도 사이에 다른 작업이 먼저 처리될 수 있습니다. 같은 예제에서 큐에 broken, notes 순서로 넣으면 broken이 처음 실패한 뒤 notes가 앞에 남아 먼저 끝나고, 그다음에 broken(1)이 꺼내집니다. 꺼내는 순서는 broken(0), notes(0), broken(1), broken(2)로 바뀌지만, 최종 출력은 똑같이 done=[notes], dead=[broken]입니다.

뒤의 작업이 막히지 않는다는 점에서는 장점이지만, 반대로 요청한 순서대로 끝나야 하는 작업이라면 문제가 됩니다. 문서의 1쪽이 실패해서 2쪽보다 늦게 인쇄되면 안 되는 경우가 그렇습니다. 그때는 실패한 작업을 다시 넣는 대신 그 자리에서 정해진 횟수만큼 재시도하는 등 다른 방법이 필요합니다. 어떤 자료구조를 쓰느냐만큼, 실패했을 때 순서를 어떻게 다룰지도 처음에 정해야 합니다. 이 예제는 이름으로 실패를 정하는 모의 실행이라서, 인쇄 도중 프로그램이 멈추거나 같은 문서가 두 번 인쇄되는 상황까지는 다루지 않습니다.

큐에 넣은 명령을 차례로 실행하기

큐에는 데이터뿐 아니라 '해야 할 일' 자체를 넣을 수도 있습니다. 다음 예제는 게시글을 등록하는 Add, 공개하는 Publish, 현재 상태를 출력하는 Print 명령을 큐에 넣고, 앞에서부터 하나씩 꺼내 실행합니다. 세 명령은 모두 execute 메서드 하나만 가진 Command 인터페이스를 구현하므로, 큐에서 꺼내는 쪽은 명령의 종류를 몰라도 execute만 호출하면 됩니다. 인터페이스로 역할을 나누는 방법은 인터페이스로 역할과 구현 분리하기에서 배웠습니다. 실제 서버라면 명령을 넣는 스레드와 꺼내는 스레드가 따로 있겠지만, 여기서는 한 스레드로 처리 순서만 확인합니다. 여러 스레드가 함께 큐를 쓰는 방법은 18장부터 배웁니다.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.Map;

public final class PostTaskQueueCli {
    public static void main(String[] args) {
        Deque<Command> queue = new ArrayDeque<>();
        queue.offer(new Add("map", 40));
        queue.offer(new Add("queue", 50));
        queue.offer(new Publish("map"));
        queue.offer(new Print());
        State state = new State();
        while (!queue.isEmpty()) {
            queue.poll().execute(state);
        }
    }

    private interface Command {
        void execute(State s);
    }

    private record Add(String title, int viewCount) implements Command {
        public void execute(State s) {
            s.viewCount.put(title, viewCount);
        }
    }

    private record Publish(String title) implements Command {
        public void execute(State s) {
            if (!s.viewCount.containsKey(title)) throw new IllegalArgumentException(title);
            s.published.put(title, true);
        }
    }

    private record Print() implements Command {
        public void execute(State s) {
            System.out.println("viewCount=" + s.viewCount + ", published=" + s.published);
        }
    }

    private static final class State {
        final Map<String, Integer> viewCount = new LinkedHashMap<>();
        final Map<String, Boolean> published = new LinkedHashMap<>();
    }
}

viewCount={map=40, queue=50}, published={map=true}

큐는 넣은 순서대로 명령을 내주므로 두 Add가 조회 수를 먼저 채우고, Publish("map")이 map을 공개한 뒤, 마지막 Print가 두 Map을 출력합니다. 앞의 세 명령은 상태만 바꾸고 아무것도 출력하지 않으므로 출력은 한 줄입니다. 두 Map이 LinkedHashMap이라서 넣은 순서대로 나옵니다. Publish는 등록되지 않은 글을 공개하려 하면 예외를 던지는데, 이 순서에서는 map이 이미 등록돼 있으므로 통과합니다.

명령 하나가 실패하면 남은 명령은

이 main은 예외를 잡지 않습니다. 큐에 Publish("map")과 Print()만 넣고 실행하면 어떻게 될까요? 첫 poll()이 Publish를 꺼내 실행하지만, map이 등록되지 않았으므로 IllegalArgumentException: map이 발생합니다. 예외가 main 밖으로 나가면서 프로그램이 끝나므로 Print는 큐에 남은 채 실행되지 않고, 상태 출력도 나오지 않습니다. 실패한 Publish는 이미 큐에서 꺼냈으므로 다시 들어가지도 않습니다.

Exception in thread "main" java.lang.IllegalArgumentException: map
	at PostTaskQueueCli$Publish.execute(PostTaskQueueCli.java:29)
	at PostTaskQueueCli.main(PostTaskQueueCli.java:13)

스택 트레이스의 줄 번호는 본문 파일의 main에서 처음 두 Add를 지운 상태를 기준으로 한 것이라, 직접 고쳐 본 파일에 따라 다를 수 있습니다. 이 결과는 '큐에서 꺼냈다', '명령이 성공했다', '결과를 사용자에게 보여 줬다'가 서로 다른 사건이라는 것을 보여 줍니다. 꺼냈다고 해서 성공한 것이 아니고, 성공했다고 해서 출력된 것도 아닙니다. 명령 하나가 실패해도 나머지를 계속 실행하려면, 반복문 안에서 예외를 잡고 실패한 명령을 따로 기록하면 됩니다. 다음은 main의 while 부분을 바꾼 것으로, 파일 위쪽에 import java.util.ArrayList;와 import java.util.List;를 추가해야 합니다.

List<Command> failed = new ArrayList<>();
while (!queue.isEmpty()) {
    Command command = queue.poll();
    try {
        command.execute(state);
    } catch (IllegalArgumentException e) {
        failed.add(command);
    }
}
System.out.println("failed=" + failed);

이렇게 바꾸면 같은 입력에서 Print가 빈 상태 viewCount={}, published={}를 출력하고, 마지막 줄에 failed=[Publish[title=map]]이 나옵니다. 실패한 명령을 버릴지, 다시 넣을지, 기록만 해 둘지는 앞의 인쇄 대기열과 마찬가지로 기능의 요구 사항에 따라 정합니다.

정리

• 스택과 큐는 ArrayDeque 하나로 쓸 수 있지만, 동작은 클래스가 아니라 부르는 메서드가 정합니다. 스택은 push·pop으로 앞쪽만 쓰고, 큐는 offer로 뒤에 넣고 poll로 앞에서 꺼냅니다.
• 브라우저 이력은 back과 forward 두 스택과, 스택 밖의 current로 만듭니다. 새 페이지를 방문하면 forward를 비워야 하며, 이것은 스택 연산이 아니라 기능의 규칙입니다.
• 상태를 바꾸기 전에 이동할 수 있는지부터 확인하면, 예외 때문에 상태가 반쯤만 바뀌는 일을 막을 수 있습니다.
• poll()로 꺼낸 작업은 큐에 없으므로, 실패했을 때 다시 넣을지, 따로 모아 둘지, 버릴지를 정해야 합니다. 다시 넣는다면 재시도 한도도 함께 정합니다.

연습 문제

1. 본문의 History로 A에서 시작해 B, C, D를 차례로 방문한 뒤 back()을 두 번 호출하면 current는 무엇이고, 그 뒤 forward()를 호출하면 어떤 순서로 페이지가 나올까요? 이어서, 두 번 back()한 직후 B에서 E를 새로 방문하면 back, current, forward는 각각 어떻게 될까요?
2. PrinterRetryQueue에서 큐에 notes, broken, memo를 이 순서로 넣으면 작업이 어떤 순서로 꺼내지는지 적고, 최종 출력을 예측하세요.
3. 뒤로 가기 이력을 최근 두 페이지까지만 보관하도록 visit을 고치세요. 가장 오래된 페이지는 스택의 어느 끝에 있는지 생각해 보세요. 고친 뒤 A에서 시작해 B, C, D를 방문하면 back은 어떻게 될까요?

import java.util.ArrayDeque;
import java.util.Deque;

public final class BrowserBackTwiceSolution {
    public static void main(String[] args) {
        Deque<String> back = new ArrayDeque<>(), forward = new ArrayDeque<>();
        String current = "A";
        for (String page : new String[] {"B", "C", "D"}) {
            back.push(current);
            current = page;
            forward.clear();
        }
        for (int i = 0; i < 2; i++) {
            forward.push(current);
            current = back.pop();
        }
        System.out.println(
                "current=" + current + ", next=" + forward.pop() + ", then=" + forward.pop());
    }
}

current=B, next=C, then=D

void visit(String page) {
    back.push(current);
    if (back.size() > limit) back.removeLast();
    current = page;
    forward.clear();
}

다음 글

16장에서는 Map, 스택, 큐, 덱을 직접 써 봤습니다. 다음 장의 Iterable과 Iterator에서는 이런 컬렉션을 for문 하나로 같은 방식으로 순회할 수 있는 이유를 살펴봅니다.