자료구조: Stack, Queue, Deque, PriorityQueue

자료구조: Stack, Queue, Deque, PriorityQueue

자료구조의 핵심은 하나다.

데이터를 어떤 순서로 꺼내야 하는가?

상황	떠올릴 자료구조
가장 최근에 넣은 값을 먼저 꺼내야 한다	Stack
먼저 들어온 값을 먼저 꺼내야 한다	Queue
앞뒤 모두에서 넣고 빼야 한다	Deque
최솟값/최댓값을 계속 꺼내야 한다	PriorityQueue

---

1. Stack

핵심 개념

Stack은 나중에 들어온 값이 먼저 나가는 구조이다.

LIFO
Last In First Out

예시:

push(1)
push(2)
push(3)

pop() → 3

---

Java에서 Stack 사용

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

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

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

하지만 코딩테스트에서는 Stack보다 Deque를 스택처럼 많이 사용한다.

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

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

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

 

 

---

Stack 주요 메서드

메서드	의미
push()	값 넣기
pop()	값 꺼내기
peek()	맨 위 값 확인
isEmpty()	비어 있는지 확인
size()	크기 확인

---

Stack을 떠올릴 문제

문제 유형	이유
괄호 검사	최근에 들어온 여는 괄호와 닫는 괄호를 비교
뒤로가기	최근 방문 기록부터 돌아감
문자열 폭발	최근에 쌓인 문자열을 확인
충돌 문제	직전 값과 현재 값을 비교

---

괄호 검사 흐름

1. 여는 괄호면 stack에 넣는다.
2. 닫는 괄호면 stack에서 하나 꺼낸다.
3. 꺼낸 값과 현재 닫는 괄호가 짝이 맞는지 확인한다.
4. 끝까지 봤을 때 stack이 비어 있으면 올바른 괄호다.

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

for (char ch : s.toCharArray()) {
    if (ch == '(' || ch == '{' || ch == '[') {
        stack.push(ch);
    } else {
        if (stack.isEmpty()) return false;

        char open = stack.pop();

        if (ch == ')' && open != '(') return false;
        if (ch == '}' && open != '{') return false;
        if (ch == ']' && open != '[') return false;
    }
}

return stack.isEmpty();

---

2. Queue

핵심 개념

Queue는 먼저 들어온 값이 먼저 나가는 구조이다.

FIFO
First In First Out

예시:

offer(1)
offer(2)
offer(3)

poll() → 1

---

Java에서 Queue 사용

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

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

System.out.println(queue.poll()); // 1
System.out.println(queue.peek()); // 2

---

Queue 주요 메서드

메서드	의미
offer()	값 넣기
poll()	앞에서 값 꺼내기
peek()	앞의 값 확인
isEmpty()	비어 있는지 확인
size()	크기 확인

---

Queue를 떠올릴 문제

문제 유형	이유
카드 문제	앞에서 꺼내고 뒤로 보내는 동작
프린터 큐	순서를 유지하면서 조건에 따라 뒤로 보냄
BFS	먼저 발견한 노드부터 탐색
프로세스 처리	요청 순서대로 처리

---

프린터 큐 유형 흐름

1. 큐에서 맨 앞 작업을 꺼낸다.
2. 뒤에 더 높은 우선순위가 있는지 확인한다.
3. 있으면 다시 뒤로 보낸다.
4. 없으면 처리한다.
5. 내가 찾는 작업이 몇 번째로 처리되는지 센다.

인덱스와 우선순위를 함께 저장하는 경우가 많다.

Queue<int[]> queue = new ArrayDeque<>();

queue.offer(new int[]{0, 2}); // index, priority
queue.offer(new int[]{1, 1});
queue.offer(new int[]{2, 3});

---

3. Deque

핵심 개념

Deque는 앞과 뒤에서 모두 넣고 뺄 수 있는 자료구조이다.

Double Ended Queue

Deque는 상황에 따라 Stack처럼도, Queue처럼도 사용할 수 있다.

---

Deque 주요 메서드

메서드	의미
addFirst()	앞에 넣기
addLast()	뒤에 넣기
pollFirst()	앞에서 꺼내기
pollLast()	뒤에서 꺼내기
peekFirst()	앞 값 확인
peekLast()	뒤 값 확인
push()	앞에 넣기
pop()	앞에서 꺼내기
poll()	앞에서 꺼내기

---

4. Stack과 Deque 방향 비교

이번에 제일 헷갈렸던 부분이다.

Deque에서도 push()를 사용할 수 있다.

정리하면 다음과 같다.

Deque의 push는 앞에 넣는다.
Deque의 pop은 앞에서 꺼낸다.
Deque의 poll도 기본적으로 앞에서 꺼낸다.

---

Stack의 push/pop

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

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

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

흐름:

push(1) → [1]
push(2) → [1, 2]
push(3) → [1, 2, 3]

pop() → 3

---

Deque의 push/pop

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

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

System.out.println(deque.pop()); // 3

흐름:

push(1) → [1]
push(2) → [2, 1]
push(3) → [3, 2, 1]

pop() → 3

내부 순서는 Stack과 다르게 보이지만,
마지막에 넣은 값이 먼저 나오므로 Stack처럼 동작한다.

---

Deque 메서드 방향 정리

메서드	방향	같은 의미
push(e)	앞에 넣기	addFirst(e)
pop()	앞에서 꺼내기	removeFirst()
poll()	앞에서 꺼내기	pollFirst()
addLast(e)	뒤에 넣기
pollLast()	뒤에서 꺼내기

---

Deque를 Stack처럼 쓰는 방법

방식	넣기	꺼내기	결과
앞쪽을 top으로 사용	push()	pop()	마지막 값
앞쪽을 top으로 사용	addFirst()	pollFirst()	마지막 값
뒤쪽을 top으로 사용	addLast()	pollLast()	마지막 값

예시:

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

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

System.out.println(stack.pollLast()); // 3

---

Deque를 Queue처럼 쓰는 방법

뒤에 넣고 앞에서 꺼내면 Queue처럼 동작한다.

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

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

System.out.println(queue.pollFirst()); // 1

정리하면 이렇게 기억하면 된다.

앞에 넣고 앞에서 꺼내면 Stack
뒤에 넣고 뒤에서 꺼내도 Stack
뒤에 넣고 앞에서 꺼내면 Queue

---

5. PriorityQueue

핵심 개념

PriorityQueue는 우선순위가 높은 값이 먼저 나오는 큐이다.

일반 Queue는 먼저 들어온 값이 먼저 나오지만,
PriorityQueue는 들어온 순서가 아니라 우선순위 기준으로 값이 나온다.

Java의 PriorityQueue는 기본적으로 작은 값이 먼저 나오는 최소 힙이다.

---

최소 힙

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(5);
pq.offer(1);
pq.offer(3);

System.out.println(pq.poll()); // 1
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // 5

---

최대 힙

큰 값이 먼저 나오게 하려면 다음처럼 작성한다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

pq.offer(5);
pq.offer(1);
pq.offer(3);

System.out.println(pq.poll()); // 5
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // 1

또는 Comparator를 사용할 수도 있다.

PriorityQueue<Integer> pq =
        new PriorityQueue<>((a, b) -> Integer.compare(b, a));

b - a처럼 뺄셈으로 비교할 수도 있지만, 값이 클 경우 오버플로우가 날 수 있어서 Integer.compare()를 쓰는 것이 안전하다.

---

PriorityQueue 주요 메서드

메서드	의미
offer()	값 넣기
poll()	우선순위가 가장 높은 값 꺼내기
peek()	우선순위가 가장 높은 값 확인
isEmpty()	비어 있는지 확인
size()	크기 확인

---

배열을 PriorityQueue에 넣기

우선순위 큐 문제에서는 숫자 하나만 넣는 것보다, 여러 정보를 함께 저장하는 경우가 많다.

PriorityQueue<int[]> pq = new PriorityQueue<>(
    (a, b) -> Integer.compare(a[1], b[1])
);

위 코드는 int[]의 두 번째 값 기준으로 작은 값이 먼저 나온다.

pq.offer(new int[]{0, 3});
pq.offer(new int[]{1, 9});
pq.offer(new int[]{2, 6});

System.out.println(Arrays.toString(pq.poll())); // [0, 3]
System.out.println(Arrays.toString(pq.poll())); // [2, 6]
System.out.println(Arrays.toString(pq.poll())); // [1, 9]

---

PriorityQueue를 떠올릴 문제

문제 유형	이유
가장 작은 값부터 처리	최소 힙
가장 큰 값부터 처리	최대 힙
작업 스케줄링	짧은 작업부터 처리
더 맵게	가장 작은 음식 2개를 계속 꺼냄
다익스트라	비용이 가장 작은 노드부터 처리

---

6. 자료구조 한눈에 정리

자료구조	꺼내는 기준	Java 사용 예시	대표 유형
Stack	가장 나중에 들어온 값	Deque<Integer> stack = new ArrayDeque<>();	괄호 검사
Queue	가장 먼저 들어온 값	Queue<Integer> queue = new ArrayDeque<>();	카드, 프린터 큐, BFS
Deque	앞뒤 모두 가능	Deque<Integer> deque = new ArrayDeque<>();	스택/큐 대체
PriorityQueue	우선순위가 높은 값	PriorityQueue<Integer> pq = new PriorityQueue<>();	힙, 작업 스케줄링

---

7. 자주 헷갈리는 메서드 정리

Queue 계열

메서드	의미	비어 있을 때
offer()	값 넣기	실패 시 false
poll()	값 꺼내기	null 반환
peek()	값 확인	null 반환
add()	값 넣기	실패 시 예외
remove()	값 꺼내기	예외 발생
element()	값 확인	예외 발생

코딩테스트에서는 보통 add()보다 offer(),
remove()보다 poll()을 더 많이 사용하는 것 같다.

---

Deque 방향 정리

메서드	방향
push()	앞에 넣기
pop()	앞에서 꺼내기
poll()	앞에서 꺼내기
addFirst()	앞에 넣기
pollFirst()	앞에서 꺼내기
addLast()	뒤에 넣기
pollLast()	뒤에서 꺼내기

---

8. 문제를 볼 때 떠올릴 기준

문제 키워드	떠올릴 자료구조
짝이 맞는가? 최근 값과 비교해야 하는가?	Stack
앞에서 꺼내고 뒤로 보내는가? 순서를 유지해야 하는가?	Queue
앞뒤 모두에서 꺼내야 하는가?	Deque
최솟값 또는 최댓값을 계속 꺼내야 하는가?	PriorityQueue

---

자료구조별 시간복잡도와 공간복잡도

자료구조를 사용할 때는 메서드 사용법뿐만 아니라,
각 연산이 얼마나 빠른지도 같이 알아두는 것이 좋다.

코딩테스트에서는 보통 입력 크기가 커지면 시간복잡도가 중요해진다.
특히 Stack, Queue, Deque, PriorityQueue는 자주 쓰이지만, 내부 동작 방식에 따라 연산 비용이 조금씩 다르다.

---

1. Stack 시간복잡도

Stack은 가장 마지막에 넣은 값을 먼저 꺼내는 구조이다.

Java에서는 Stack 클래스를 사용할 수도 있지만, 코딩테스트에서는 보통 Deque를 스택처럼 많이 사용한다.

연산	메서드	시간복잡도
값 넣기	push()	O(1)
값 꺼내기	pop()	O(1)
맨 위 값 확인	peek()	O(1)
비어 있는지 확인	isEmpty()	O(1)
크기 확인	size()	O(1)

스택은 한쪽 끝에서만 값을 넣고 빼기 때문에 대부분의 주요 연산이 O(1)이다.

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

stack.push(1);     // O(1)
stack.pop();       // O(1)
stack.peek();      // O(1)
stack.isEmpty();   // O(1)

---

2. Queue 시간복잡도

Queue는 먼저 들어온 값을 먼저 꺼내는 구조이다.

Java에서는 보통 다음처럼 사용한다.

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

연산	메서드	시간복잡도
값 넣기	offer()	O(1)
값 꺼내기	poll()	O(1)
앞의 값 확인	peek()	O(1)
비어 있는지 확인	isEmpty()	O(1)
크기 확인	size()	O(1)

큐도 앞과 뒤에서만 삽입/삭제가 일어나기 때문에 주요 연산은 O(1)이다.

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

queue.offer(1);    // O(1)
queue.poll();      // O(1)
queue.peek();      // O(1)

---

3. Deque 시간복잡도

Deque는 앞과 뒤에서 모두 삽입과 삭제가 가능한 자료구조이다.

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

연산	메서드	시간복잡도
앞에 넣기	addFirst() / push()	O(1)
뒤에 넣기	addLast() / offer()	O(1)
앞에서 꺼내기	pollFirst() / poll() / pop()	O(1)
뒤에서 꺼내기	pollLast()	O(1)
앞 값 확인	peekFirst() / peek()	O(1)
뒤 값 확인	peekLast()	O(1)
크기 확인	size()	O(1)

Deque는 양쪽 끝에서 작업하는 경우 매우 빠르다.

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

deque.addFirst(1);  // O(1)
deque.addLast(2);   // O(1)
deque.pollFirst();  // O(1)
deque.pollLast();   // O(1)

다만 중간에 있는 값을 찾거나 삭제하는 용도로는 적합하지 않다.
Deque는 앞과 뒤를 빠르게 처리하는 자료구조라고 이해하면 된다.

---

4. PriorityQueue 시간복잡도

PriorityQueue는 우선순위가 높은 값부터 꺼내는 자료구조이다.

Java의 PriorityQueue는 내부적으로 Heap 구조를 사용한다.

PriorityQueue<Integer> pq = new PriorityQueue<>();

연산	메서드	시간복잡도
값 넣기	offer()	O(log N)
우선순위가 가장 높은 값 꺼내기	poll()	O(log N)
우선순위가 가장 높은 값 확인	peek()	O(1)
비어 있는지 확인	isEmpty()	O(1)
크기 확인	size()	O(1)

PriorityQueue는 값을 넣거나 꺼낼 때마다 Heap 구조를 유지해야 한다.
그래서 offer()와 poll()은 O(log N)이다.

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(5);   // O(log N)
pq.offer(1);   // O(log N)
pq.poll();     // O(log N)
pq.peek();     // O(1)

반면 peek()은 루트에 있는 값을 확인만 하면 되기 때문에 O(1)이다.

---

5. 공간복잡도

자료구조에 값을 N개 저장한다면, 대부분 공간복잡도는 O(N)이다.

자료구조	공간복잡도	이유
Stack	O(N)	최대 N개의 값을 저장할 수 있음
Queue	O(N)	최대 N개의 값을 저장할 수 있음
Deque	O(N)	최대 N개의 값을 저장할 수 있음
PriorityQueue	O(N)	Heap에 최대 N개의 값을 저장할 수 있음

즉, 자료구조 자체가 데이터를 담는 공간이기 때문에, 저장되는 데이터 개수만큼 공간을 사용한다.

예를 들어 괄호 검사 문제에서 문자열 길이가 N이라면, 최악의 경우 모든 문자가 여는 괄호일 수 있다.

(((((((

이 경우 스택에 최대 N개의 문자가 들어갈 수 있으므로 공간복잡도는 O(N)이다.

---

6. 자료구조별 복잡도 한눈에 보기

자료구조	값 넣기	값 꺼내기	값 확인	공간복잡도
Stack	O(1)	O(1)	O(1)	O(N)
Queue	O(1)	O(1)	O(1)	O(N)
Deque	O(1)	O(1)	O(1)	O(N)
PriorityQueue	O(log N)	O(log N)	O(1)	O(N)

여기서 값 확인은 peek() 계열 메서드를 의미한다.

---

7. 왜 PriorityQueue만 O(log N)일까?

Stack, Queue, Deque는 단순히 한쪽 끝이나 양쪽 끝에서 값을 넣고 뺀다.
그래서 대부분의 연산이 O(1)이다.

반면 PriorityQueue는 값을 넣거나 꺼낸 뒤에도 우선순위 순서가 유지되도록 내부 구조를 다시 조정해야 한다.

예를 들어 최소 힙에서는 가장 작은 값이 루트에 있어야 한다.

        1
      /   \
     3     5
    / \
   7   9

새로운 값을 넣으면 Heap 조건을 만족하도록 위치를 조정해야 한다.
값을 꺼낼 때도 루트 값을 제거한 뒤 다시 Heap 구조를 맞춰야 한다.

이 과정에서 트리의 높이만큼 이동할 수 있는데, Heap의 높이는 대략 log N이다.
그래서 offer()와 poll()이 O(log N)이 된다.

---

8. 코딩테스트에서 어떻게 생각하면 좋을까?

문제를 풀 때 자료구조와 시간복잡도를 함께 생각하면 좋다.

문제 상황	적합한 자료구조	이유
최근 값만 확인하면 됨	Stack	push, pop이 O(1)
순서대로 처리하면 됨	Queue	offer, poll이 O(1)
앞뒤 모두 필요함	Deque	양쪽 삽입/삭제가 O(1)
매번 최솟값/최댓값이 필요함	PriorityQueue	poll이 O(log N)으로 효율적

정리하면 이렇게 볼 수 있다.

Stack / Queue / Deque
→ 순서만 관리하면 되는 문제에 적합
→ 대부분 O(1)

PriorityQueue
→ 우선순위가 필요한 문제에 적합
→ 삽입/삭제는 O(log N)

---

정리

이번에 Java 자료구조를 정리하면서 가장 크게 느낀 점은,
자료구조 문제에서 중요한 것은 문제를 보고 먼저 어떤 순서로 데이터를 꺼내야 할지를 질문을 하는 것이다.

그리고 목적에 맞게 아래와 같이 자료구조를 사용하면 된다.

가장 최근 값부터 확인해야 하면 Stack
먼저 들어온 값부터 처리해야 하면 Queue
앞뒤 처리가 모두 필요하면 Deque
최솟값이나 최댓값을 계속 꺼내야 하면 PriorityQueue

특히 Deque는 Stack처럼도, Queue처럼도 사용할 수 있기 때문에 방향을 정확히 이해해야 한다.

push는 앞에 넣는다.
pop은 앞에서 꺼낸다.
poll도 기본적으로 앞에서 꺼낸다.

앞에 넣고 앞에서 꺼내면 Stack
뒤에 넣고 뒤에서 꺼내도 Stack
뒤에 넣고 앞에서 꺼내면 Queue

자료구조를 공부하면서 문법뿐 아니라 시간복잡도도 같이 정리할 필요가 있었다.

특히 Stack, Queue, Deque는 주요 연산이 대부분 O(1)이라 빠르게 사용할 수 있다.
반면 PriorityQueue는 Heap 구조를 유지해야 하기 때문에 offer()와 poll()이 O(log N)이다.

그래도 매번 전체를 정렬하는 것보다, 우선순위 큐를 사용해서 필요한 값만 꺼내는 것이 훨씬 효율적일 수 있다.

Stack      → 최근 값부터 처리, O(1)
Queue      → 들어온 순서대로 처리, O(1)
Deque      → 앞뒤 모두 처리, O(1)
PriorityQueue → 우선순위대로 처리, O(log N)

앞으로 자료구조 문제를 풀 때는 단순히 어떤 자료구조를 쓸지만 생각하지 말고,
이 연산이 얼마나 자주 반복되는지, 시간복잡도는 괜찮은지도 같이 확인해야겠다.