큐

큐 (Queue)

Queue(큐)는 데이터를 저장하는 선형 자료구조로, 선입선출(FIFO, First In First Out) 방식으로 동작

 

큐의 기본 연산

연산	설명
enqueue()	큐의 뒤(rear)에 데이터를 추가
dequeue()	큐의 앞(front)에서 데이터를 꺼냄

Java에서 큐 사용하기

1. LinkedList 기반 큐

• java.util.LinkedList는 큐 인터페이스를 구현한 대표적인 클래스
• 내부적으로 이중 연결 리스트(Doubly Linked List) 구조로 구현되어 있음.

import java.util.*;

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

2. ArrayDeque 기반 큐

• java.util.ArrayDeque는 동적 배열로 구현된 큐
• 일반적으로 LinkedList보다 더 나은 성능을 제공
• 큐뿐만 아니라 덱(Deque, 양방향 큐) 기능도 함께 제공

import java.util.*;

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

 

일반적인 상황에서는 ArrayDeque를 사용하는 것이 더 빠르고 효율적이다.

안에 지정해주면....

 

Queue 인터페이스 - 기본 사용법

1. 큐 선언

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

 

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

 

2. 원소 추가 (enqueue)

queue.add(1);
queue.add(2);
queue.add(3);  // queue: [1, 2, 3]

 

3. 원소 제거 (dequeue)

queue.remove();  // 반환값: 1, queue: [2, 3]

 

4. 맨 앞 원소 확인 (peek)

int front = queue.peek();  // front = 2

 

5. 큐가 비었는지 확인

boolean isEmpty = queue.isEmpty();

 

코딩 테스트 유형

1. BFS (너비 우선 탐색)

• 그래프 탐색 알고리즘의 하나인 BFS에서는 큐가 핵심 도구
• 현재 노드와 인접한 노드들을 큐에 넣고, 큐에서 꺼내며 탐색을 진행

Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[n];

q.add(start);
visited[start] = true;

while (!q.isEmpty()) {
    int curr = q.remove();

    for (int next : graph[curr]) {
        if (!visited[next]) {
            visited[next] = true;
            q.add(next);
        }
    }
}

 

2. 투 포인터 문제와 큐

• 투 포인터(Two Pointer) 알고리즘에서 큐는 슬라이딩 윈도우를 구현하는 데 유용

Queue<Integer> q1 = new LinkedList<>();
Queue<Integer> q2 = new LinkedList<>();

// 두 큐를 번갈아가며 dequeue + enqueue 하며 합을 맞춰 나감