게시판 탐색 이력과 작업 큐
두 Stack으로 게시판 탐색 이력을 이동하고 FIFO Queue로 알림 작업을 처리하며 실패 복구 위치까지 설계합니다.
자료 구조는 실제 기능의 상태 전이를 설명할 때 가장 잘 이해됩니다.
브라우저 이력은 현재 페이지와 back·앞으로 Stack 사이를 이동하고, 프린터는 제출 순서대로 Queue에서 작업을 꺼냅니다.
두 예제 모두 “어느 끝에서 넣고 빼는가”와 실패 시 원소가 어느 구조에 남는가를 명시합니다.
forward 이력 초기화
A→B→C 방문 뒤 back으로 B에 왔다가 D를 새로 방문하면 C로 가는 앞으로 경로는 더 이상 유효하지 않습니다.
다음 잘못된 구현은 앞으로 Stack을 남겨 B→D 이후에도 C로 이동합니다.
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());
}
}새 분기가 생기면 앞으로.clear가 방문 트랜잭션의 일부여야 합니다.
Stack 연산만 맞아도 기능 상태 기계 규칙을 빠뜨리면 결과는 틀립니다.
현재 페이지는 Stack 밖의 명시적 상태로 배치
back을 누르면 현재를 앞으로에 push하고 back에서 새 current를 pop합니다.
앞으로는 반대로 현재를 back에 push한 뒤 앞으로에서 꺼냅니다.
빈 Stack이면 current를 바꾸지 않고 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;
}
}
}Stack 내부 반복 순서는 기능 규칙이 아니며 디버깅 출력일 뿐입니다.
사용자는 현재 페이지와 이동 성공 여부를 봅니다.
방문할 때 앞으로를 비우는 규칙이 분기 이력을 일관되게 만듭니다.
프린터 Queue의 실패 작업 소유권
poll 후 인쇄가 실패하면 작업은 대기 중에서 이미 사라졌습니다.
재시도하려면 실패 작업을 재시도 Queue에 넣거나 성공 후에만 제거하는 peek/remove 패턴을 사용합니다.
후자는 같은 실패 작업이 뒤 작업을 영원히 막을 수 있어 최대 재시도와 dead-letter 정책이 필요합니다.
다음 예제는 대기 중에서 꺼낸 작업이 실패하면 attempts를 늘려 뒤에 다시 넣고, 세 번째 실패에서는 dead letter로 보냅니다.
성공 작업은 done 목록에 기록합니다.
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) {}
}Queue 뒤에 재삽입하므로 실패 작업 사이에 다른 작업이 처리될 수 있습니다.
순서 절대 보장이 요구되면 정책이 달라집니다.
자료 구조 선택은 전달 의미와 함께 설계해야 합니다.
비동기 명령의 단일 스레드 실행
실제 스레드를 도입하기 전에 Queue 소비 규칙을 단일 스레드로 확인합니다.
등록, 공개, 출력 명령을 FIFO로 처리하고 각 명령 결과를 누적 상태에서 확인합니다.
동시성은 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<>();
}
}연습 문제
History에 A, B, C, D를 방문하고 두 번 back 하세요.
current는 B, 앞으로 pop 순서는 C 다음 D여야 합니다.
직접 Stack 두 개로 확인합니다.
정답과 해설
방문마다 기존 current를 back에 push합니다.
back 두 번은 D와 C를 차례로 앞으로에 push하므로 top은 C입니다.
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로 소유권을 옮겨야 합니다.