동블

그래프 뷰

16. 자료구조-Stack-Queue-Deque

5 min read

자료구조 - Stack / Queue / Deque

Summary

직전 값 비교는 스택, 먼저 들어온 것부터 처리하면 큐, 양쪽을 직접 조작하면 덱이다.
Java 메서드 방향표는 문법/A_필수/ArrayDeque.md를 대표 문서로 본다.

언제 쓰는가

문제 신호자료구조핵심
최소 이동 횟수, 레벨 순회QueueFIFO, offer/poll
괄호, 인접 제거, 직전 값 비교StackLIFO, push/pop/peek
오큰수, 이전보다 큰/작은 값Monotonic Stack인덱스를 저장
0-1 BFSDeque비용 0은 앞, 비용 1은 뒤
슬라이딩 윈도우 최댓값/최솟값Deque후보 인덱스를 단조 유지

문제 신호

먼저 들어온 순서대로 처리한다 → Queue
가장 최근에 넣은 것부터 확인한다 → Stack
양쪽에서 넣고 빼야 한다 → Deque
현재 값보다 작거나 큰 이전 값들을 제거한다 → 단조 스택/단조 덱
윈도우가 한 칸씩 이동하며 최댓값/최솟값이 필요하다 → 단조 덱

Queue BFS 기본

Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
visited[start] = true;
 
while (!q.isEmpty()) {
    int cur = q.poll();
 
    for (int next : graph[cur]) {
        if (visited[next]) continue;
        visited[next] = true;
        q.offer(next);
    }
}
실수주의
push() 사용큐가 아니라 스택 방향이 됨
visited를 poll 때 체크중복 삽입이 많아질 수 있음
poll() 결과 언박싱비어 있으면 null. while 조건 유지

Stack 기본

Deque<Integer> st = new ArrayDeque<>();
 
for (int x : arr) {
    while (!st.isEmpty() && st.peek() < x) {
        st.pop();
    }
    st.push(x);
}

스택 문제는 다음 조합으로 통일한다.

Deque<Integer> st = new ArrayDeque<>();
push / pop / peek

단조 스택 - 오큰수 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
 
        StringTokenizer stInput = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(stInput.nextToken());
 
        Deque<Integer> st = new ArrayDeque<>(); // 인덱스 저장
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && arr[st.peek()] < arr[i]) {
                ans[st.pop()] = arr[i];
            }
            st.push(i);
        }
 
        StringBuilder sb = new StringBuilder();
        for (int x : ans) sb.append(x).append(' ');
        System.out.println(sb);
    }
}

복잡도: 각 인덱스가 한 번 push, 한 번 pop되므로 O(N).

Deque - 슬라이딩 윈도우 최댓값

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stInput = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stInput.nextToken());
        int k = Integer.parseInt(stInput.nextToken());
 
        int[] arr = new int[n];
        stInput = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(stInput.nextToken());
 
        Deque<Integer> dq = new ArrayDeque<>(); // 후보 인덱스, 값은 내림차순 유지
        StringBuilder sb = new StringBuilder();
 
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
            while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i]) dq.pollLast();
 
            dq.offerLast(i);
 
            if (i >= k - 1) sb.append(arr[dq.peekFirst()]).append(' ');
        }
 
        System.out.println(sb);
    }
}

복잡도: 각 인덱스가 한 번 들어가고 한 번 빠지므로 O(N).

자주 하는 실수

실수수정
큐처럼 쓰면서 push()offer() 또는 offerLast() 사용
스택처럼 쓰면서 offer()push() 사용
덱 문제에서 방향 없는 메서드 혼용offerFirst/offerLast/pollFirst/pollLast로 명시
단조 스택에 값 저장 후 답 인덱스 잃음대부분 인덱스를 저장
슬라이딩 윈도우에서 만료 인덱스 제거 누락peekFirst() <= i - k 제거

백지 복원 질문

1. BFS 큐의 Java 선언과 세 메서드는?
2. 스택 문제의 Java 선언과 세 메서드는?
3. 단조 스택에서 보통 값이 아니라 인덱스를 저장하는 이유는?
4. 슬라이딩 윈도우 최댓값에서 앞/뒤에서 각각 무엇을 제거하는가?
5. 0-1 BFS에서 비용 0 간선은 어느 쪽에 넣는가?

관련 문서