Stack Queue Patterns

스택·큐 패턴 기준

같은 stack이나 queue를 써도 언제 넣고 언제 빼는지에 따라 중복 방문, 무한 루프, 잘못된 순서가 생긴다.

01

삽입 시점 고정

BFS는 큐에 넣는 순간 방문 처리해야 같은 정점이 여러 번 들어가지 않는다.

02

제거 조건을 말로 쓴다

단조 스택은 새 값이 들어왔을 때 더 이상 답 후보가 아닌 원소를 제거한다.

03

상태 크기 관찰

무한 루프나 중복 삽입은 queue 크기가 비정상적으로 커지는 신호로 먼저 보인다.

Monotonic stack
후보 압축 현재 값이 이전 후보를 무효화할 때 pop한다.
비교 부등호가 핵심이다.
BFS queue
거리 층 유지 큐에서 꺼낸 순서가 시작점으로부터 거리 증가 순서가 된다.
가중치가 있으면 다익스트라를 본다.
Two queues
라운드 구분 현재 레벨과 다음 레벨을 나누면 시간 단계를 명확히 할 수 있다.
size snapshot도 가능하다.
Deque
양끝 후보 관리 윈도우 밖 원소와 나쁜 후보를 다른 쪽에서 제거한다.
인덱스를 저장하면 경계 검사가 쉽다.

중복 삽입 · 부등호 · 레벨 점검

중복 삽입 같은 상태가 queue에 여러 번 들어가는 경로가 없는가.
부등호 단조 구조에서 같은 값 처리 규칙이 문제 조건과 맞는가.
레벨 거리나 시간 단계를 출력해야 하면 레벨 구분을 보존하는가.

BFS 방문 시점

visited[start] = true;
q.push(start);
while (!q.empty()) {
    auto v = q.front(); q.pop();
    for (auto next : graph[v]) if (!visited[next]) {
        visited[next] = true; q.push(next);
    }
}