게시판 탐색 이력과 작업 큐

자료 구조는 실제 기능의 상태 전이를 설명할 때 가장 잘 이해됩니다.

브라우저 이력은 현재 페이지와 back·앞으로 Stack 사이를 이동하고, 프린터는 제출 순서대로 Queue에서 작업을 꺼냅니다.

두 예제 모두 “어느 끝에서 넣고 빼는가”와 실패 시 원소가 어느 구조에 남는가를 명시합니다.

forward 이력 초기화

A→B→C 방문 뒤 back으로 B에 왔다가 D를 새로 방문하면 C로 가는 앞으로 경로는 더 이상 유효하지 않습니다.

다음 잘못된 구현은 앞으로 Stack에 C를 남깁니다. 실제 코드는 이동하지 않고 invalid-forward=C를 출력합니다.

lab/StaleForwardHistoryBug.java

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());
    }
}

새 분기가 생기면 forward.clear()가 visit 동작에 포함되어야 합니다. 이 코드는 단일 스레드 예제이며 원자적 갱신이나 실패 시 롤백을 구현하지 않습니다.

Stack 연산만 맞아도 기능 상태 기계 규칙을 빠뜨리면 결과는 틀립니다.

현재 페이지는 Stack 밖의 명시적 상태로 배치

back을 누르면 현재를 앞으로에 push하고 back에서 새 current를 pop합니다.

앞으로는 반대로 현재를 back에 push한 뒤 앞으로에서 꺼냅니다.

빈 Stack이면 current를 바꾸지 않고 false를 반환합니다.

src/BrowserHistory.java

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;
        }
    }
}

top부터 읽는 두 이력과 새 방문의 초기화
main의 생성·호출 순서	back · top부터	current	forward · top부터
`new History("A")`	`[]`	`A`	`[]`
`visit("B")`	`[A]`	`B`	`[]`
`visit("C")`	`[B, A]`	`C`	`[]`
첫 `back()`	`[A]`	`B`	`[C]`
`visit("D")`	`[B, A]`	`D`	C 경로 삭제: `[]`
`forward()` → `false`	`[B, A]`	`D`	`[]`
둘째 `back()`	`[A]`	`B`	`[D]`
셋째 `back()`	`[]`	`A`	`[B, D]`

new History("A"): back · top부터: []
current: A
forward · top부터: []
visit("B"): back · top부터: [A]
current: B
forward · top부터: []
visit("C"): back · top부터: [B, A]
current: C
forward · top부터: []
첫 back(): back · top부터: [A]
current: B
forward · top부터: [C]
visit("D"): back · top부터: [B, A]
current: D
forward · top부터: C 경로 삭제: []
forward() → false: back · top부터: [B, A]
current: D
forward · top부터: []
둘째 back(): back · top부터: [A]
current: B
forward · top부터: [D]
셋째 back(): back · top부터: []
current: A
forward · top부터: [B, D]

두 이력은 맨 왼쪽이 push/pop하는 top입니다. 각 행은 호출 직후의 소스 추적입니다. 실제 출력은 D 방문 뒤 상태, forward=false, 마지막 A 상태의 세 줄이며, back() 반환값은 출력하지 않습니다.

이 예제의 ArrayDeque는 push와 pop을 맨 앞에서 수행하며, 디버깅 출력도 top부터 나열합니다.

사용자는 현재 페이지와 이동 성공 여부를 봅니다.

방문할 때 앞으로를 비우는 규칙이 분기 이력을 일관되게 만듭니다.

프린터 Queue의 실패 작업 소유권

poll 후 인쇄가 실패하면 작업은 대기 중에서 이미 사라졌습니다.

재시도하려면 실패 작업을 재시도 Queue에 넣거나 성공 후에만 제거하는 peek/remove 패턴을 사용합니다.

후자는 같은 실패 작업이 뒤 작업을 영원히 막을 수 있어 최대 재시도와 dead-letter 정책이 필요합니다.

다음 예제는 대기 중에서 꺼낸 작업이 실패하면 attempts를 늘려 뒤에 다시 넣고, 세 번째 실패에서는 dead letter로 보냅니다. print는 이름으로 성공 여부를 판정하는 모의 함수이며 실제 인쇄를 수행하지 않습니다.

성공 작업은 done 목록에 기록합니다.

src/PrinterRetryQueue.java

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) {}
}

broken은 세 번 실패하고 두 번만 다시 대기한다
poll로 꺼낸 작업	판정과 이번 조치	조치 뒤 대기·결과
`notes` `attempts=0`	모의 `print` 성공 `done.add("notes")`	`pending=[broken(0)]` `done=[notes]` `dead=[]`
`broken` `attempts=0`	첫 실패: `0 → 1` `offer`로 뒤에 재삽입	`pending=[broken(1)]` `done=[notes]` `dead=[]`
`broken` `attempts=1`	둘째 실패: `1 → 2` `offer`로 뒤에 재삽입	`pending=[broken(2)]` `done=[notes]` `dead=[]`
`broken` `attempts=2`	셋째 실패: `2 → 3` `dead.add("broken")`	`pending=[]` `done=[notes]` `dead=[broken]`

notes attempts=0: 판정과 이번 조치:
모의 print 성공
done.add("notes")
조치 뒤 대기·결과:
pending=[broken(0)]
done=[notes]
dead=[]
broken attempts=0: 판정과 이번 조치:
첫 실패: 0 → 1
offer로 뒤에 재삽입
조치 뒤 대기·결과:
pending=[broken(1)]
done=[notes]
dead=[]
broken attempts=1: 판정과 이번 조치:
둘째 실패: 1 → 2
offer로 뒤에 재삽입
조치 뒤 대기·결과:
pending=[broken(2)]
done=[notes]
dead=[]
broken attempts=2: 판정과 이번 조치:
셋째 실패: 2 → 3
dead.add("broken")
조치 뒤 대기·결과:
pending=[]
done=[notes]
dead=[broken]

broken(n)의 n은 꺼내기 전까지 누적된 실패 횟수 attempts입니다. 처음 시도와 재시도 두 번이 모두 실패합니다. 이 코드는 이름으로 성공 여부를 판정하며 실제 인쇄를 하지 않습니다. 중간 상태는 소스 추적이고 최종 출력은 done=[notes], dead=[broken]입니다.

Queue 뒤에 재삽입하므로 실패 작업 사이에 다른 작업이 처리될 수 있습니다.

순서 절대 보장이 요구되면 정책이 달라집니다.

자료 구조 선택은 전달 의미와 함께 설계해야 합니다.

큐에 등록한 명령의 단일 스레드 실행

실제 스레드를 도입하기 전에 Queue 소비 규칙을 단일 스레드로 확인합니다.

등록, 공개, 출력 명령을 FIFO로 처리하고 각 명령 결과를 누적 상태에서 확인합니다.

동시성은 18장에서 별도로 추가합니다.

app/PostTaskQueueCli.java

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<>();
    }
}

네 명령을 순서대로 실행하고 Print에서만 출력한다
꺼내어 실행한 명령	명령이 바꾸는 상태	표준 출력
`Add("map", 40)`	`viewCount={map=40}`	없음
`Add("queue", 50)`	`viewCount=` `{map=40, queue=50}`	없음
`Publish("map")`	`published={map=true}`	없음
`Print()`	상태 변경 없음	`viewCount={map=40, queue=50},` `published={map=true}`

Add("map", 40): 명령이 바꾸는 상태:
viewCount={map=40}
표준 출력: 없음
Add("queue", 50): 명령이 바꾸는 상태:
viewCount=
{map=40, queue=50}
표준 출력: 없음
Publish("map"): 명령이 바꾸는 상태: published={map=true}
표준 출력: 없음
Print(): 명령이 바꾸는 상태: 상태 변경 없음
표준 출력:
viewCount={map=40, queue=50},
published={map=true}

처음에는 두 Map이 비어 있습니다. poll().execute(state)가 명령 하나를 같은 스레드에서 끝낸 뒤 다음 명령을 꺼냅니다. 마지막 셀의 두 부분은 실제로 한 줄의 출력이며, 두 Map의 나열은 이 코드의 LinkedHashMap 삽입 순서입니다.

연습 문제

History에 A, B, C, D를 방문하고 두 번 back 하세요.

current는 B, 앞으로 pop 순서는 C 다음 D여야 합니다.

직접 Stack 두 개로 확인합니다.

정답과 해설

방문마다 기존 current를 back에 push합니다.

back 두 번은 D와 C를 차례로 앞으로에 push하므로 top은 C입니다.

exercise/BrowserBackTwiceSolution.java

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입니다.

Stack의 top이 최근 이동 대상을 나타냅니다.

브라우저와 프린터 예제의 공통점은 원소 순서보다 상태 전이 규칙이 먼저라는 것입니다.

새 방문은 앞으로를 폐기하고, 작업 실패는 재시도 또는 dead-letter로 소유권을 옮겨야 합니다.

forward 이력 초기화

현재 페이지는 Stack 밖의 명시적 상태로 배치

프린터 Queue의 실패 작업 소유권

큐에 등록한 명령의 단일 스레드 실행

연습 문제

이 페이지의 목차