기준

Deque는 스택과 큐를 모두 만들 수 있다. 그래서 타입보다 먼저 넣는 쪽과 빼는 쪽이 같은가, 다른가를 고정해야 한다.

메서드 세트 지도

의도넣기보기빼기방향
스택pushpeekpophead에서 넣고 head에서 뺌
큐offerpeekpolltail에 넣고 head에서 뺌
덱offerFirst, offerLastpeekFirst, peekLastpollFirst, pollLast양쪽을 명시
flowchart TD Problem["문제에서 꺼내야 하는 값"] --> Recent{"가장 최근 값인가"} Recent -->|예| Stack["스택: push peek pop"] Recent -->|아니오| Oldest{"가장 오래된 값인가"} Oldest -->|예| Queue["큐: offer peek poll"] Oldest -->|아니오| Both{"양쪽 모두 필요한가"} Both -->|예| Deque["덱: First Last 명시"] Both -->|아니오| Recheck["문제 조건 다시 확인"]

스택 의도인데 큐 메서드를 사용

발생 장면

BOJ3986 좋은 단어에서 가장 최근 글자와 비교해야 했는데, add / peek / poll을 써서 가장 오래된 글자와 비교했다.

Queue<String> deque = new ArrayDeque<>();

deque.add(ab);   // tail에 삽입
deque.peek();    // head 조회
deque.poll();    // head 제거

이 조합은 FIFO다. 스택이 아니라 큐다.

고치는 기준

Deque<String> stack = new ArrayDeque<>();

stack.push(ab);  // head에 삽입
stack.peek();    // head 조회
stack.pop();     // head 제거

상세: Deque의 Queue 메서드와 Stack 메서드 혼용

괄호 종류가 하나뿐인데 스택을 크게 만듦

발생 장면

PG12909 올바른 괄호에서 실제 괄호 문자를 저장하는 스택을 직접 만들었다.

괄호 종류가 (, ) 하나뿐이고 유효성만 판단하면 열린 괄호 개수만 필요하다.

int open = 0;
for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == '(') {
        open++;
    } else if (open == 0) {
        return false;
    } else {
        open--;
    }
}
return open == 0;

상세: PG12909 분석

BFS 큐에서 push()를 사용

증상

BFS를 구현했는데 탐색 순서가 DFS처럼 깊게 들어간다.

Deque<Integer> q = new ArrayDeque<>();
q.push(start); // 앞에 넣는다

BFS는 먼저 들어온 노드를 먼저 꺼내야 한다.

Deque<Integer> q = new ArrayDeque<>();
q.offer(start);

while (!q.isEmpty()) {
    int cur = q.poll();
}

빈 자료구조에서 꺼냄

메서드비어 있을 때사용 기준
pop()예외비어 있지 않음을 보장할 때
poll()null빈 상태를 값으로 처리할 때
peek()null보기만 할 때

스택 문제에서 실패 조건은 보통 pop() 전에 나온다.

if (stack.isEmpty()) {
    return false;
}
stack.pop();