[Java] Stack/Deque - 코딩테스트 준비

Stack이란

Stack은 LIFO(Last In First Out, 후입선출) 자료구조다. 가장 마지막에 넣은 데이터가 가장 먼저 나온다.

자바에서는 java.util.Stack 클래스로 제공된다.

보통 편의점에서 물건을 채울 때 먼저 들어와있던 물건을 가장 맨 앞으로 꺼내고 최근에 들어온 물건을 뒤로 배치해놓는걸 선입선출이라고 하는데, 이것의 반대로 생각하면 이해가 쉬울듯 하다. (편의점에서 후입선출하면 쫓겨날지도...?)

인스턴스 생성

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
Stack<String> stack2 = new Stack<>();

자주 사용하는 메서드

메서드	동작	비었을 때
push(e)	맨 위에 추가	-
pop()	맨 위 제거 후 반환	EmptyStackException
peek()	맨 위 확인 (제거 X)	EmptyStackException
isEmpty()	비었는지 확인	-
size()	원소 개수	-
search(o)	맨 위 기준 1-based 위치, 없으면 -1	-

pop()과 peek()은 비어 있으면 예외를 던지므로, 꺼내기 전에 isEmpty()로 확인하는 습관이 필요하다.

사용 예시

Stack<Integer> stack = new Stack<>();

stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.peek()); // 3 (제거 안 함)
System.out.println(stack.pop());  // 3 (제거함)
System.out.println(stack.pop());  // 2
System.out.println(stack.size()); // 1
System.out.println(stack.isEmpty()); // false

---

Deque란

Deque(Double Ended Queue, "덱" 또는 "데크")는 양쪽 끝에서 모두 넣고 뺄 수 있는 자료구조다. 앞/뒤를 자유롭게 다룰 수 있어서 스택으로도, 큐로도 쓸 수 있다. java.util.Deque는 인터페이스이므로 실제 사용할 때는 구현체를 지정한다.

인스턴스 생성

import java.util.Deque;
import java.util.ArrayDeque;

Deque<Integer> deque = new ArrayDeque<>();   // 권장 (배열 기반, 빠름)
Deque<Integer> deque2 = new LinkedList<>();  // 노드 기반, null 허용

코테에서는 대부분 ArrayDeque를 쓴다.

자주 사용하는 메서드

Deque의 메서드는 실패했을 때 동작에 따라 두 계열로 나뉜다. 

위치	예외를 던지는 계열	값(null/false) 반환 계열
앞에 추가	addFirst(e)	offerFirst(e)
뒤에 추가	addLast(e)	offerLast(e)
앞에서 제거	removeFirst()	pollFirst()
뒤에서 제거	removeLast()	pollLast()
앞 확인	getFirst()	peekFirst()
뒤 확인	getLast()	peekLast()

코테에서는 보통 null 반환 계열(offer/poll/peek) 이 다루기 편하다.

스택처럼 쓰는 별칭 (앞쪽에서 넣고 뺌):

메서드	대응	동작
push(e)	addFirst(e)	앞에 추가
pop()	removeFirst()	앞에서 제거
peek()	peekFirst()	앞 확인

큐처럼 쓰는 메서드 (뒤로 넣고 앞에서 뺌, FIFO):

메서드	대응	동작
offer(e)	offerLast(e)	뒤에 추가
poll()	pollFirst()	앞에서 제거
peek()	peekFirst()	앞 확인

스택이든 큐든 peek()은 항상 앞쪽을 본다. 넣는 위치만 다르다(스택=앞, 큐=뒤).

사용 예시

스택으로 사용:

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

stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.peek()); // 3
System.out.println(stack.pop());  // 3
System.out.println(stack.pop());  // 2

큐로 사용:

Deque<Integer> queue = new ArrayDeque<>();

queue.offer(1);
queue.offer(2);
queue.offer(3);

System.out.println(queue.peek()); // 1 (가장 먼저 넣은 것)
System.out.println(queue.poll()); // 1
System.out.println(queue.poll()); // 2

---

Stack보다 Deque를 사용해야 하는 이유

Stack은 자바 초창기의 레거시 클래스로, Vector를 상속한다. 이 때문에 다음 문제가 있다.

• 모든 메서드가 synchronized — Vector를 상속한 탓에 매 연산마다 동기화 비용이 붙는다. 코테는 단일 스레드라 불필요한 오버헤드다.
• Vector의 메서드가 그대로 노출 — stack.get(0), stack.add(2, x)처럼 임의 인덱스 접근이 가능해 스택 추상화가 깨진다.
• 반복 순서가 반직관적 — Stack은 바닥(먼저 넣은 것)부터 순회한다. "위에서부터"를 기대하면 틀린다.

반면 ArrayDeque는:

• 동기화가 없어 더 빠르고, 배열 기반이라 캐시 지역성이 좋다.
• 하나로 스택·큐·덱을 모두 처리할 수 있다.
• 모든 연산이 amortized O(1)이다.

그래서 자바 공식 문서도 스택이 필요하면 Deque(ArrayDeque)를 쓰라고 안내한다.

주의: ArrayDeque는 null을 넣을 수 없다. poll()/peek()이 비었을 때 null을 반환하기 때문에, null을 원소로 허용하면 "비었음"과 구분이 안 된다. null을 꼭 넣어야 하면 LinkedList를 쓴다(코테에서는 드묾).

---

실전 예시

괄호 짝 맞추기 (스택)

여는 괄호는 쌓고, 닫는 괄호가 나오면 짝을 꺼낸다. 끝까지 갔을 때 스택이 비어 있어야 올바른 괄호다.

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') {
            stack.push(c);
        } else { // c == ')'
            if (stack.isEmpty()) return false; // 닫는 괄호가 먼저 나옴
            stack.pop();
        }
    }
    return stack.isEmpty(); // 안 닫힌 게 남아 있으면 false
}

여러 종류의 괄호가 섞인 경우:

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if (c == ')' && open != '(') return false;
            if (c == '}' && open != '{') return false;
            if (c == ']' && open != '[') return false;
        }
    }
    return stack.isEmpty();
}

BFS (큐)

시작 노드를 큐에 넣고, 꺼내면서 인접 노드를 방문 처리 후 다시 큐에 넣는다.

void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int cur = queue.poll();
        // cur 방문 처리 로직

        for (int next : graph.get(cur)) {
            if (!visited[next]) {
                visited[next] = true; // 큐에 넣을 때 방문 처리 (중복 방지)
                queue.offer(next);
            }
        }
    }
}

BFS에서 방문 처리는 큐에 넣는 시점에 하는 것이 핵심이다. 꺼낼 때 처리하면 같은 노드가 큐에 여러 번 들어가 비효율적이거나 무한 루프가 될 수 있다.

---

요약

상황	쓸 것
스택 (LIFO)	ArrayDeque + push/pop/peek
큐 (FIFO)	ArrayDeque + offer/poll/peek
덱 (양방향)	ArrayDeque + First/Last 계열
null을 원소로 넣어야 함	LinkedList

Stack은 굳이 쓰지 않는다. ArrayDeque 하나로 스택·큐·덱을 다 처리하고, 메서드 계열(예외 vs null 반환)만 구분하면 된다.