[코딩테스트] 스택, 큐, 덱, 우선순위 큐 자료구조 정리

오늘의 핵심 주제는 네 가지 자료구조입니다.

스택 (Stack)
큐 (Queue)
덱 (Deque)
우선순위 큐(Priority Queue, 힙 구조)

저번 글까지는 배열, 문자열, 완전 탐색 위주로 직접 하나하나 돌려보는 연습을 했다면,

이번 글부터는 자바 자료구조를 이용해서 문제를 더 깔끔하게 푸는 패턴을 익혀보려고 합니다.

각 자료구조의 개념과 자바 코드 사용법, 코딩테스트에서 자주 나오는 활용 패턴까지 정리해보겠습니다.

 

---

 

Ⅰ. 목표

자바의 스텍, 큐, 덱, 우선순위 큐를 자유롭게 사용할 수 있고,
어떤 문제에 어떤 자료구조를 써야 할지 감이 오는 상태 만들기

 

구체적인 목표는 다음과 같습니다.

• 스택으로 괄호 검사, 되돌리기(Undo) 등 LIFO 패턴 구현
• 큐로 순서대로 처리하는 FIFO 문제 구현
• 덱으로 양쪽에서 넣고 빼는 시뮬레이션 문제 해결
• 우선순위 큐로 항상 가장 작은/큰 값을 빠르게 꺼내는 패턴 익히기

 

---

 

Ⅱ. 스택 (Stack)

- 개념

스택은 Last In, First Out (LIFO) 구조입니다.

• 예시
  • 브라우저 뒤로 가기
  • 되돌리기(Undo)
  • 괄호 짝 맞추기
• 특징
  • 가장 나중에 들어간 데이터가 먼저 나온다.
• 메서드
  • push(item): 스택 맨 위에 값 추가
  • pop(): 스택 맨 위의 값을 꺼내면서 제거
  • peak(): 스택 맨 위의 값을 조회(제거 X)
  • isEmpty(): 스택이 비어 있는지 확인
  • size(): 현재 스택에 들어있는 원소 개수

 

---

 

- 자바에서 사용법

자바에서는 Stack 클래스를 그대로 사용하거나, Deque를 스택처럼 사용할 수 있습니다.

가장  단순한 Stack 사용 예시는 다음과 같습니다.

import java.util.Stack;

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

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

int top = stack.pop();		// 3. 스택에서 삭제됨
int peek = stack.peek();	// 2. 삭제는 안 됨
boolean empty = stack.isEmpty();

 

실전 코딩테스트에서는 Stack 또는 ArrayDeque 둘 다 사용 가능하지만,

성능과 권장사항 측면에서는 ArrayDeque를 스택처럼 쓰는 방식도 많이 쓰입니다.

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

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

stack.push(1);			// 스택 상단에 삽입
int x = stack.pop();	// x == 1, 스택 상단에서 제거

 

---

 

- 대표 문제: 괄호 검사

가장 전형적인 스택 문제는 괄호의 짝이 올바른지 확인하는 문제입니다.

접근 방식은 다음과 같습니다.

1. 문자열을 왼쪽부터 한 글자씩 본다.
2. 여는 괄호 '('가 나오면 스택에 push
3. 닫는 괄호 ')'가 나오면
   • 스택이 비어 있으면 잘못된 문자열
   • 스택에서 pop해서 짝을 맞추기
4. 문자열을 끝까지 처리했을 때
   • 스택이 비어 있으면 올바른 괄호 문자열
   • 비어 있지 않으면 잘못된 문자열

코드는 다음과 같이 작성할 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        
        for (int i=0; i<s.length(); i++) {
        	char c = s.charAt(i);
            
            if (c == '(') {
            	stack.push(c);
            } else if (c == ')') {
            	if (stack.isEmpty()) {
                	valid = false;
                    break;
                }
                stack.pop();
            }
        }
        
        if (!stack.isEmpty()) {
        	valid = false;
        }
        
        System.out.println(valid ? "YES" : "NO");
    }
}

이런 패턴은 중괄호, 대괄호, 태그 검사 등으로 확장해서 자주 등장합니다.

 

---

 

Ⅲ. 큐(Queue)

- 개념

큐는 First In, First Out (FIFO) 구조입니다.

• 예시
  • 줄 서기
  • 프린터 작업 대기열
  • BFS(너비 우선 탐색)에서 사용
• 특징
  • 먼저 들어온 데이터가 먼저 처리된다.
• 메서드
  • offer(item): 큐의 맨 뒤에 원소 추가. 실패 시 false
  • add(item) : 큐의 맨 뒤에 원소 추가. 실패 시 예외
  • poll(): 큐의 맨 앞 원소를 꺼내면서 제거. 비어 있으면 null
  • remove(): 큐의 맨 앞 원소 제거 후 반환. 비어 있으면 예외
  • peek(): 맨 앞 원소를 보기만 함(제거 X). 비어 있으면 null
  • element() : 맨 앞 원소를 보기만 함(제거 X). 비어 있으면 예외
  • isEmpty(): 큐가 비어있는지 확인
  • size(): 큐의 원소 개수

 

---

 

- 자바에서 큐 사용법

일반적으로 Queue 인터페이스와 LinkedList 또는 ArrayDeque를 함께 사용합니다.

import java.util.LinkedList;
import java.util.Queue;

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

queue.offer(1);		// 삽입
queue.offer(2);
queue.offer(3);

int x = queue.poll();	// 1 (가장 먼저 들어온 값)
int y = queue.peek();
boolean empty = queue.isEmpty();

 

---

 

- 대표 문제 패턴: 카드 게임 시뮬레이션

1부터 N까지 번호가 적힌 카드가 순서대로 있을 때

• 맨 위 카드를 버리고
• 그 다음 맨 위 카드를 맨 아래로 보내는 행동을 반복했을 때
• 마지막에 남는 카드 번호를 구하기

이 문제는 큐를 이용해 자연스럽게 해결할 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

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());
        
        Queue<Integer> q = new LinkedList<>();
        for (int i=1; i<=n; i++) {
        	q.offer(i);
        }
        
        while (q.size() > 1) {
        	q.poll();			// 맨 위 카드 버리기
            q.offer(q.poll());	// 그 다음 카드를 맨 뒤로 보내기
        }
        
        System.out.println(q.poll());
    }
}

이런 식의 순서대로 작업 처리 시뮬레이션은 큐로 구현하면 코드가 매우 깔끔해집니다.

 

---

 

Ⅳ. 덱 (Deque)

- 개념

덱(Deque, Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐입니다.

• 앞/뒤 양쪽에서 push, pop이 가능
• 예시
  • 슬라이딩 윈도우
  • 회전하는 큐
  • 양쪽에서 요소를 넣고 빼는 시뮬레이션
• 삽입/삭제 메서드
  • addFirst(item): 덱의 앞쪽에 원소 추가. 실패 시 예외
  • addLast(item): 덱의 뒤쪽에 원소 추가. 실패 시 예외
  • offerFirst(item): 덱의 앞쪽에 원소 추가. 실패 시 false
  • offerLast(item): 덱의 뒤쪽에 원소 추가. 실패 시 false
  • removeFirst(): 앞쪽 원소 제거 후 반환. 비어있으면 예외
  • removeLast(): 뒤쪽 원소 제거 후 반환. 비어있으면 예외
  • pollFirst(): 앞쪽 원소 제거 후 반환. 비어있으면 null
  • pollLast(): 뒤쪽 원소 제거 후 반환. 비어있으면 null
  • getFirst(): 앞쪽 원소 조회. 비어 있으면 예외
  • getLast(): 뒤쪽 원소 조회. 비어 있으면 예외
  • peekFirst(): 앞쪽 원소 조회. 비어 있으면 null
  • peekLast(): 뒤쪽 원소 조회. 비어 있으면 null
• ArrayDeque를 스택처럼 사용할 때 메서드
  • push(item): 스택처럼 상단에 추가 (실제로는 addFirst)
  • pop(): 스택 상단에서 꺼내면서 제거 (removeFirst와 유사)
  • peek(): 스택 상단 원소 조회 (peekFirst와 유사)

 

---

 

- 자바에서 덱 사용법

자바에서는 ArrayDeque를 가장 많이 사용합니다.

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

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

// 앞쪽에 삽입/삭제
deque.addFirst(1);
deque.addFirst(2);
int x = deque.removeFirst();

// 뒤쪽에 삽입/삭제
deque.addLast(3);
deque.addLast(4);
int y = deque.removeLast();

// 확인만
int front = deque.peekFirst();
int back = deque.peekLast();

 

---

 

- 대표 패턴: 회전하는 큐

예시로, 덱을 이용하여 양쪽으로 회전하는 큐 문제를 해결할 수 있습니다.

• 특정 값을 뽑기 위해
  • 왼쪽으로 한 칸 회전 (앞의 요소를 뒤로)
  • 오른쪽으로 한 칸 회전 (뒤의 요소를 앞으로)
• 두 동작 중 더 적은 회전 횟수를 선택하는 문제에서
  • 덱을 이용하면 앞뒤를 자유롭게 움직일 수 있어 구현이 쉽습니다.

덱을 양쪽에서 삽입, 삭제를 동시에 지원하는 큐로 이해하고,

기본 메서드(addFirst, addLast, removeFirst, removeLast)를 직접 써보는 정도까지 연습하면 충분합니다.

 

---

 

Ⅴ. 우선순위 큐 (Priority Queue)

- 개념

우선순위 큐(Priority Queue)는 값의 크기(또는 우선순위)에 따라 먼저 나오는 요소가 정해지는 자료구조입니다.

• 기본 PriorityQueue는 최소 힙(min-heap) → 가장 작은 값이 먼저 나옴
• 응용
  • 가장 작은/큰 값을 자주 꺼내야 하는 문제
  • 힙 정렬, K번째 수, 합치기 비용 최소화 등
• 메서드
  • offer(item)
  • add(item)
  • poll()
  • remove()
  • peek()
  • element()
  • isEmpty()
  • size()
  • clear(): 모든 원소 제거

 

---

 

- 자바에서 PriorityQueue  기본 사용법

최소 힙 (기본)

import java.util.PriorityQueue;

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

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

int x = pq.poll();	// 1 (가장 작은 값부터)
int x = pq.poll();	// 3

---

최대 힙

import java.util.Collections;
import java.util.PriorityQueue;

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

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

int x = maxPq.poll();	// 5 (가장 큰 값부터 나옴)

또는 람다식으로도 구할 수 있습니다.

PriorityQueue<Integer> maxPq = new PriorityQueue<>((a, b) -> b - a);

 

---

 

- 대표 문제 패턴: 최소 값부터 처리하기

여러 개의 숫자를 합치는 비용이 두 수의 합 만큼 들고,
계속 반복해서 하나가 될 때까지 합칠 때
전체 비용을 최소화 하는 문제

 

이런 경우, 항상 가장 작은 두 수부터 먼저 합치는 것이 최적 전략입니다.

PriorityQueue를 사용하면 매번 가장 작은 두 수를 쉽게 꺼낼 수 있습니다.

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

// 값들 추가
for (int i=0; i<n; i++) {
	pq.offer(Integer.parseInt(br.readLine()));
}

int cost = 0;

while (pq.size() > 1) {
	int a = pq.poll();
    int b = pq.poll();
    int sum = a + b;
    cost += sum;
    pq.offer(sum);
}

System.out.println(cost);

이런 가장 작은 것부터 두 개씩 꺼내서 처리하는 유형은 우선순위 큐의 전형적인 사용 예입니다.

 

---

 

Ⅵ. 어떤 문제에 어떤 자료구조를 써야 할까?

• 스택 (Stack)
  • 되돌리기, 괄호 검사, 뒤집기, 뒤로 가기
• 큐 (Queue)
  • 순서대로 처리, 대기열, 회전 없이 한 방향으로만 흐르는 시뮬레이션, BFS
• 덱 (Deque)
  • 양방향 회전, 앞뒤 양쪽에서 삽입/삭제가 필요한 시뮬레이션
• 우선순위 큐 (PriorityQueue)
  • 항상 현재 가장 작은/큰 값을 꺼내야 하는 문제, 그리디와 함께 자주 등장

 

문제를 읽으면서

입력받은 순서대로 처리해야 하나?

최근 것부터 거꾸로 꺼내야 하나?

앞뒤 양쪽에서 넣고 빼야 하나?

항상 최소/최댓값을 꺼내야 하나?

를 스스로 물어보고, 그에 따라 자료구조를 선택하는 습관을 들이면 좋습니다.

 

---

 

Ⅶ. 체크리스트

• 자바에서 Stack, Queue, Deque, PriorityQueue를 직접 선언하고 기본 메서드를 쓸 수 있다.
• 스택으로 괄호 검사(올바른 괄호 문자열)를 구현할 수 있다.
• 큐를 사용해서 카드 게임처럼 앞에서 빼고 뒤로 보내는 시뮬레이션 문제를 풀 수 있다.
• 덱을 사용해서 양끝에서 삽입, 삭제가 필요한 간단한 문제를 구현할 수 있다.
• PriorityQueue로 최소 힙/최대 힙을 만들 수 있고, 각각 어떤 상황에서 사용하는지 설명할 수 있다.
• 문제를 읽고 어떤 자료구조가 어울리는지 파악할 수 있다.

 

---

 

다음 글에서는 정렬과 이분 탐색, 누적합을 이용해 시간 복잡도를 줄이는 패턴에 들어갈 예정입니다.

• 정렬 + 그리디
• 정렬 + 이분 탐색
• 구간 합을 빠르게 구하는 누적합