Unit 2.4 — Queue (FIFO 자료구조)

F-LAB JAVA · 3주차 · Phase 2 · 컬렉션 프레임워크 전체 지도

---

📌 학습 목표

이 Unit을 끝내면 다음을 답할 수 있어야 한다.

• Queue 의 정확한 의미 (FIFO) 와 사용 시나리오는?
• offer() vs add(), poll() vs remove(), peek() vs element() 메서드 페어의 차이는?
• ArrayDeque 가 LinkedList 보다 권장되는 이유는?
• PriorityQueue 의 동작 (우선순위 힙) 은?
• BlockingQueue 의 의미와 멀티스레드 환경에서의 역할은?
• Deque (양방향 큐) 와 Stack 의 관계는?
• ILIC 에서 작업 큐 / 이벤트 큐를 어떻게 구현하나?
• 박승제씨가 메시지 큐 (MQ) 와 자바 Queue 를 어떻게 연결하나?

---

🎯 핵심 한 문장

Queue 는 "처리 대기 줄" 이라는 의미의 FIFO (First In First Out) 자료구조다.
자바의 Queue 인터페이스는 두 가지 메서드 페어 (안전 vs 강제) 를 제공해서 큐가 비었거나 가득 찼을 때의 대응을 선택 가능.
ArrayDeque 가 LinkedList 보다 빠르고 일반적 큐 사용의 정답.
PriorityQueue 는 우선순위 힙, BlockingQueue 는 멀티스레드 환경의 안전한 큐.
박승제씨가 ILIC 에서 이벤트 처리, 작업 큐, 메시지 큐 클라이언트 등으로 매일 만남.

비유 — 식당의 대기 줄

시스템	비유
Queue	식당 입구 대기 줄 (먼저 온 사람 먼저 입장)
offer()	새 손님 줄에 합류 (자리 없으면 대기)
poll()	손님 한 명 입장 (다음 손님 차례)
peek()	다음 손님 확인 (들여보내지 않음)
PriorityQueue	VIP 우선 입장 (예약/등급 순)
BlockingQueue	무한 줄 (가득 차면 신규 대기, 비면 점원 대기)
Deque	양쪽 출입 가능한 줄

---

🧭 9개 섹션 로드맵

1. Queue 인터페이스의 본질 (FIFO)
2. 두 가지 메서드 페어
3. ArrayDeque vs LinkedList — 일반 큐의 정답
4. PriorityQueue — 우선순위 힙
5. Deque (양방향 큐) 와 Stack
6. BlockingQueue (멀티스레드)
7. ILIC 실무 — 작업 큐와 이벤트 큐
8. 흔한 실수 + 안티패턴
9. 면접 + 자기 점검

---

1️⃣ Queue 인터페이스의 본질 (FIFO)

1.1 FIFO 의 정확한 의미

FIFO = First In First Out
       먼저 들어온 것이 먼저 나간다

대조:
  LIFO = Last In First Out (Stack)
       나중에 들어온 것이 먼저 나간다

시각화:

Queue (FIFO):
  
  뒤(tail) → [C] [B] [A] → 앞(head)
              새로     먼저 입장
              
  offer: tail 에 추가
  poll:  head 에서 제거

Stack (LIFO):
  
  위(top) → [C]
            [B]
            [A] ← 맨 아래
            
  push: 위에 추가
  pop:  위에서 제거

1.2 Queue 인터페이스 정의

public interface Queue<E> extends Collection<E> {
    
    // 삽입
    boolean add(E e);              // 가득 차면 예외
    boolean offer(E e);            // 가득 차면 false
    
    // 제거
    E remove();                    // 비어있으면 예외
    E poll();                      // 비어있으면 null
    
    // 조회 (제거하지 않음)
    E element();                   // 비어있으면 예외
    E peek();                      // 비어있으면 null
}

핵심:

• 두 가지 메서드 페어:
  • 강제 (실패 시 예외): add, remove, element
  • 안전 (실패 시 false/null): offer, poll, peek
• 각 동작마다 2개의 메서드

1.3 Queue 의 자연스러운 사용처

대표적 사용처:

1. 작업 처리 큐
   - 들어온 작업 순서대로 처리
   - 백그라운드 워커

2. 이벤트 큐
   - 발생한 이벤트를 순서대로 처리
   - GUI 의 이벤트 디스패치

3. 메시지 큐
   - 비동기 메시지 전달
   - 마이크로서비스 통신 (Kafka, RabbitMQ)

4. BFS (너비 우선 탐색)
   - 그래프 탐색 알고리즘

5. 버퍼링
   - 생산자-소비자 패턴
   - I/O 버퍼

6. 요청 큐
   - HTTP 요청 처리 (Tomcat, Netty)
   - DB 커넥션 풀

1.4 ILIC 에서의 Queue 사용

@Service
public class ShipmentEventProcessor {
    
    // 이벤트 큐
    private final Queue<ShipmentEvent> eventQueue = new ConcurrentLinkedQueue<>();
    
    // 작업 큐
    private final BlockingQueue<TrackingTask> taskQueue = 
        new LinkedBlockingQueue<>(1000);
    
    // 알림 큐
    private final BlockingQueue<NotificationEvent> notificationQueue = 
        new ArrayBlockingQueue<>(500);
    
    public void onShipmentCreated(ShipmentEvent event) {
        eventQueue.offer(event);
    }
    
    public void queueTask(TrackingTask task) throws InterruptedException {
        taskQueue.put(task);   // 가득 차면 대기
    }
}

→ ILIC 의 비동기/이벤트 처리에 Queue 가 핵심.

1.5 자기 점검 답변

Queue 와 Stack 의 결정적 차이는?

답:

• Queue (FIFO):

  • 먼저 들어온 것 먼저 나감
  • 양 끝에서 작업 (tail 에 추가, head 에서 제거)
  • "대기 줄" 의미

• Stack (LIFO):

  • 나중에 들어온 것 먼저 나감
  • 한 끝에서만 작업 (top 에 push/pop)
  • "쌓아 올린 더미" 의미

→ 자바의 Stack 클래스는 Legacy, ArrayDeque 권장.

---

2️⃣ 두 가지 메서드 페어

2.1 페어의 의미

자바 Queue 는 같은 동작에 두 가지 선택지 를 제공:

삽입:
  add(e)    — 가득 차면 예외 (IllegalStateException)
  offer(e)  — 가득 차면 false 반환

제거:
  remove()  — 비어있으면 예외 (NoSuchElementException)
  poll()    — 비어있으면 null 반환

조회:
  element() — 비어있으면 예외 (NoSuchElementException)
  peek()    — 비어있으면 null 반환

→ 예외 vs 안전한 반환값 선택.

2.2 각 페어 상세

삽입 페어

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

// add — 가득 차면 예외
boolean result = queue.add("A");   // true (성공)
// 만약 가득 찬 BlockingQueue 라면 IllegalStateException

// offer — 가득 차면 false
boolean result = queue.offer("A");  // true (성공)
// 만약 가득 차면 false 반환 (예외 X)

언제 어느 것을:

• add: 큐가 절대 가득 안 차야 함 (예외로 버그 감지)
• offer: 가득 찰 가능성 처리 필요 (정상 흐름)

제거 페어

// remove — 비어있으면 예외
String s = queue.remove();   // "A" 반환
// 만약 비어있으면 NoSuchElementException

// poll — 비어있으면 null
String s = queue.poll();   // "A" 또는 null
if (s != null) {
    // 처리
}

언제 어느 것을:

• remove: 큐에 요소가 있다는 게 보장 (계약)
• poll: 비었을 수 있음 (일반 사용)

조회 페어

// element — 비어있으면 예외
String s = queue.element();   // "A" (제거 안 함)

// peek — 비어있으면 null
String s = queue.peek();   // "A" 또는 null

peek 와 poll 의 차이:

• peek: 다음 요소 보기만 (큐 그대로)
• poll: 다음 요소 가져오고 제거

2.3 ILIC 패턴 — 어느 것을 쓸까

// 패턴 1: 작업 큐에서 작업 가져오기
while (!Thread.currentThread().isInterrupted()) {
    Task task = taskQueue.poll();   // 안전
    if (task == null) {
        // 큐 비었음 — 대기 또는 종료
        Thread.sleep(100);
        continue;
    }
    process(task);
}

// 패턴 2: 이벤트 처리
ShipmentEvent event = eventQueue.poll();   // 안전
if (event != null) {
    handle(event);
}

// 패턴 3: 큐가 비면 안 되는 계약
public void processNext() {
    if (queue.isEmpty()) {
        throw new IllegalStateException("Queue is empty");
    }
    Task t = queue.remove();   // 보장됨
    // ...
}

→ 보통 offer/poll/peek (안전한 페어) 사용.

2.4 메서드 페어 표

동작	강제 (예외)	안전 (false/null)
삽입	add(e)	offer(e)
제거	remove()	poll()
조회	element()	peek()

암기 도움:

강제 페어: A, R, E (add, remove, element)
안전 페어: O, P, P (offer, poll, peek)

→ 박승제씨는 보통 OPP 세트만 쓰면 됨

2.5 자기 점검 답변

빈 큐에 remove() 와 poll() 호출 시 차이는?

답:

• remove(): NoSuchElementException 발생
• poll(): null 반환

선택:

• 큐가 비었으면 안 되는 상황: remove() (예외로 버그 감지)
• 큐가 비었을 수도 있는 정상 흐름: poll() (null 체크)

→ ILIC 에선 대부분 poll().

---

3️⃣ ArrayDeque vs LinkedList — 일반 큐의 정답

3.1 두 가지 일반 Queue 구현

// 방법 1: LinkedList
Queue<Task> queue1 = new LinkedList<>();

// 방법 2: ArrayDeque (권장)
Queue<Task> queue2 = new ArrayDeque<>();

둘 다 Queue 인터페이스 구현.
→ 어느 것이 더 좋은가?

3.2 ArrayDeque 의 내부

public class ArrayDeque<E> implements Deque<E>, ... {
    
    Object[] elements;   // 원형 배열!
    int head;
    int tail;
}

원형 배열 (Circular Array):

• 배열의 끝에 도달하면 처음으로 돌아감
• head 와 tail 포인터로 양 끝 추적
• 배열 기반 → 캐시 효율 ↑
• 가득 차면 2배 확장

3.3 원형 배열 동작

초기: capacity 8
  [_, _, _, _, _, _, _, _]
   ↑
  head = tail = 0 (빈 큐)

offer("A"):
  [A, _, _, _, _, _, _, _]
   ↑
  head = 0, tail = 1

offer("B"); offer("C"):
  [A, B, C, _, _, _, _, _]
   ↑        ↑
  head=0  tail=3

poll() → "A":
  [_, B, C, _, _, _, _, _]
      ↑     ↑
   head=1  tail=3

offer("D"); offer("E"); offer("F"); offer("G"):
  [_, B, C, D, E, F, G, _]
      ↑                 ↑
   head=1            tail=7

offer("H"); offer("I"):  ← 배열 끝 도달, 처음으로 wrap
  [I, B, C, D, E, F, G, H]
   ↑↑
   tail=1, head=1   ← 가득 참 (다음 offer 면 확장)
   
  ↑ 이 시점이 가득 참

→ 양 끝 작업이 모두 O(1).

3.4 ArrayDeque vs LinkedList 비교

항목	ArrayDeque	LinkedList
내부 구조	원형 배열	이중 연결 노드
add (끝)	O(1)	O(1)
poll (앞)	O(1)	O(1)
메모리	배열 (연속)	Node 객체들 (분산)
캐시 효율	★★★	★
Node 객체	없음	매 요소마다
size	O(1)	O(1)
null 허용	❌ NullPointerException	✓

→ ArrayDeque 가 거의 모든 면에서 우수.

3.5 실제 벤치마크 (가상)

1,000,000 회 offer + poll:
  ArrayDeque:    50 ms
  LinkedList:    200 ms (Node 객체 생성/GC)

순회 1바퀴:
  ArrayDeque:    매우 빠름 (캐시 친화)
  LinkedList:    ArrayDeque 의 2-3배 느림

메모리 사용:
  ArrayDeque:    n × 4 bytes (참조)
  LinkedList:    n × ~40 bytes (Node 객체)
  → LinkedList 가 10배 더 사용

→ ArrayDeque 가 일반 큐의 정답.

3.6 ArrayDeque 의 추가 기능

ArrayDeque 는 Queue 보다 더 강력한 Deque (양방향 큐) 인터페이스 구현:

ArrayDeque<Task> deque = new ArrayDeque<>();

// Queue 처럼 (FIFO)
deque.offer(task1);
deque.poll();

// 앞쪽 작업도 가능
deque.offerFirst(task);   // 앞에 추가
deque.pollFirst();        // 앞에서 제거 (= poll)
deque.offerLast(task);    // 뒤에 추가 (= offer)
deque.pollLast();         // 뒤에서 제거

// Stack 처럼 (LIFO)
deque.push(task);
deque.pop();
deque.peek();

→ 하나의 ArrayDeque 가 Queue, Deque, Stack 모두.

3.7 LinkedList 가 Queue 로 쓰이는 일

// 자주 보이는 패턴
Queue<Task> queue = new LinkedList<>();

이유:

• 역사적: Java 1.5 에서 LinkedList 가 Queue 구현 (ArrayDeque 는 1.6)
• 코드 검색 결과 많아 보임
• 박승제씨가 1주차에 본 패턴

현대적 정답:

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

박승제씨가 ILIC 코드 리뷰 시 LinkedList Queue 보이면 ArrayDeque 로 교체 권장.

3.8 자기 점검 답변

Queue 가 필요할 때 LinkedList 가 아니라 ArrayDeque 를 쓰는 이유는?

답:
1. 캐시 효율 — 배열 기반, 연속 메모리
2. 메모리 효율 — Node 객체 없음 (LinkedList 의 1/10)
3. GC 부담 적음 — Node 객체 안 만듦
4. 더 다양한 동작 — Stack, Deque 도 가능
5. 공식 권장 — LinkedList JavaDoc 도 ArrayDeque 권장

→ 거의 모든 경우 ArrayDeque.

---

4️⃣ PriorityQueue — 우선순위 힙

4.1 PriorityQueue 의 개념

일반 Queue (FIFO):
  들어온 순서대로 나감
  
PriorityQueue:
  우선순위 높은 것 먼저 나감
  순서와 무관

4.2 PriorityQueue 의 내부

public class PriorityQueue<E> implements Queue<E>, ... {
    
    transient Object[] queue;   // 배열 기반 힙!
    
    private final Comparator<? super E> comparator;
}

Binary Heap (이진 힙):

• 완전 이진 트리
• 부모가 자식보다 우선순위 높음 (최소/최대 힙)
• 배열로 표현 (인덱스 i 의 자식은 2i+1, 2i+2)

4.3 Binary Heap 시각화

최소 힙 (Min Heap):

  배열: [1, 3, 2, 7, 5, 4, 6]
  
  트리 표현:
            [0]=1
           /     \
         [1]=3   [2]=2
         /  \    /  \
       [3]=7 [4]=5 [5]=4 [6]=6
  
  특징:
    - 부모 < 자식 (모든 경로)
    - 루트 = 최소값
    - poll() → 루트 반환 → 재정렬

4.4 PriorityQueue 동작

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(3);
pq.offer(8);
pq.offer(1);

while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}
// 출력:
// 1
// 3
// 5
// 8
// → 자동 정렬!

Integer 의 자연 순서 (오름차순) 로 우선순위 매김.

4.5 Comparator 로 우선순위 지정

// 큰 값이 먼저 (max heap)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(3);
maxHeap.offer(8);
maxHeap.poll();   // 8 (가장 큰 값)

// 객체 우선순위
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparing(Task::getPriority).reversed()
);

→ Phase 6 (Comparator) 와 연결.

4.6 시간 복잡도

PriorityQueue 시간 복잡도:
  - offer:   O(log n)   - 힙 재정렬
  - poll:    O(log n)   - 힙 재정렬
  - peek:    O(1)        - 루트만 확인
  - contains: O(n)
  - remove(obj): O(n)

→ O(log n) — 일반 Queue (O(1)) 보다 느리지만 자동 정렬.

4.7 ILIC 사용 사례

사례 1 — 우선순위 작업 큐

public class TaskScheduler {
    
    // 우선순위 높은 작업이 먼저
    private final PriorityQueue<Task> queue = new PriorityQueue<>(
        Comparator.comparing(Task::getPriority).reversed()
            .thenComparing(Task::getCreatedAt)
    );
    
    public void schedule(Task task) {
        queue.offer(task);
    }
    
    public Task next() {
        return queue.poll();
    }
}

public enum TaskPriority {
    URGENT(100),
    HIGH(50),
    NORMAL(10),
    LOW(1);
    
    final int weight;
    TaskPriority(int weight) { this.weight = weight; }
}

→ 긴급 작업이 먼저 처리됨.

사례 2 — Top K 검색

// 가장 무거운 N 개 운송 찾기
public List<Shipment> topNByWeight(List<Shipment> shipments, int n) {
    PriorityQueue<Shipment> minHeap = new PriorityQueue<>(
        Comparator.comparing(Shipment::getWeight)
    );
    
    for (Shipment s : shipments) {
        minHeap.offer(s);
        if (minHeap.size() > n) {
            minHeap.poll();   // 가장 작은 것 제거
        }
    }
    
    return new ArrayList<>(minHeap);
}

→ O(n log k) 효율적 알고리즘.

사례 3 — Dijkstra 알고리즘

// 그래프 최단 경로
public Map<Node, Integer> dijkstra(Graph g, Node start) {
    PriorityQueue<Node> pq = new PriorityQueue<>(
        Comparator.comparing(g::getDistance)
    );
    // ... 알고리즘 구현
}

→ 자료구조 + 알고리즘 결합.

4.8 PriorityQueue 의 함정

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(3);
pq.offer(8);

// ❌ 순회는 정렬 순서 보장 X!
for (Integer i : pq) {
    System.out.println(i);
}
// 출력 (예시): 3, 5, 8 또는 다른 순서
// → 힙의 배열 순서 (정렬된 순서 아님)

// ✓ 정렬 순서로 순회하려면
while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}
// 출력: 3, 5, 8 (정렬 순서)

→ poll() 만 우선순위 보장.
→ 순회는 임의 순서.

4.9 자기 점검 답변

PriorityQueue 의 순회가 정렬 순서가 아닌 이유는?

답:

• PriorityQueue 는 Binary Heap 으로 구현
• 힙의 배열 순서는 정렬 순서가 아님 (부분 순서)
• poll() 시 루트 반환 + 재정렬 → 그때만 우선순위 보장
• 정렬된 순회 원하면 poll() 반복 또는 Collections.sort(new ArrayList<>(pq))

---

5️⃣ Deque (양방향 큐) 와 Stack

5.1 Deque 인터페이스

Deque = Double-Ended Queue
        양 끝에서 작업 가능한 큐

Queue 의 확장:
  Queue:   한쪽 끝 추가 + 다른 끝 제거 (FIFO)
  Deque:   양쪽 끝 모두 추가/제거 가능

5.2 Deque 메서드

public interface Deque<E> extends Queue<E> {
    
    // 앞쪽 작업
    void addFirst(E e);
    boolean offerFirst(E e);
    E removeFirst();
    E pollFirst();
    E getFirst();
    E peekFirst();
    
    // 뒤쪽 작업
    void addLast(E e);
    boolean offerLast(E e);
    E removeLast();
    E pollLast();
    E getLast();
    E peekLast();
    
    // Stack 인터페이스
    void push(E e);    // = addFirst
    E pop();           // = removeFirst
    E peek();          // = peekFirst
}

→ 양 끝의 모든 동작 + Stack 메서드.

5.3 Deque 가 Stack 을 대체

자바의 Stack 클래스는 Legacy:

// ❌ Stack 클래스 (Legacy)
Stack<Frame> stack = new Stack<>();
stack.push(frame);
Frame top = stack.pop();

// ✓ ArrayDeque (권장)
Deque<Frame> stack = new ArrayDeque<>();
stack.push(frame);   // = offerFirst
Frame top = stack.pop();   // = pollFirst

Stack 클래스의 문제:

• Java 1.0 Legacy
• Vector 상속 → synchronized 비용
• API 일관성 부족

해결: ArrayDeque 의 push/pop 사용.

5.4 ArrayDeque 의 3가지 역할

ArrayDeque<Task> deque = new ArrayDeque<>();

// 역할 1: Queue (FIFO)
Queue<Task> queue = deque;
queue.offer(task);   // = offerLast
queue.poll();        // = pollFirst

// 역할 2: Stack (LIFO)
Deque<Task> stack = deque;
stack.push(task);    // = offerFirst
stack.pop();         // = pollFirst

// 역할 3: Deque (양방향)
deque.offerFirst(task);
deque.offerLast(task);
deque.pollFirst();
deque.pollLast();

→ 하나의 클래스가 3가지 역할.

5.5 Stack 패턴 사용 예

public class CallStack {
    private final Deque<Frame> stack = new ArrayDeque<>();
    
    public void enter(Method m) {
        Frame frame = new Frame(m);
        stack.push(frame);
    }
    
    public Frame exit() {
        return stack.pop();
    }
    
    public Frame current() {
        return stack.peek();
    }
    
    public int depth() {
        return stack.size();
    }
}

→ 박승제씨가 2주차에서 본 JVM Stack 개념.

5.6 BFS / DFS 알고리즘

// BFS — Queue
public List<Node> bfs(Node start) {
    Queue<Node> queue = new ArrayDeque<>();
    Set<Node> visited = new HashSet<>();
    
    queue.offer(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        Node n = queue.poll();
        for (Node next : n.getNeighbors()) {
            if (visited.add(next)) {
                queue.offer(next);
            }
        }
    }
    return new ArrayList<>(visited);
}

// DFS — Stack
public List<Node> dfs(Node start) {
    Deque<Node> stack = new ArrayDeque<>();
    Set<Node> visited = new HashSet<>();
    
    stack.push(start);
    visited.add(start);
    
    while (!stack.isEmpty()) {
        Node n = stack.pop();
        for (Node next : n.getNeighbors()) {
            if (visited.add(next)) {
                stack.push(next);
            }
        }
    }
    return new ArrayList<>(visited);
}

→ 같은 ArrayDeque, 다른 메서드.

5.7 ILIC 사용 — 운송 경유지 처리

public class RouteProcessor {
    
    public List<Port> calculateRoute(Port start, Port end) {
        // BFS 로 경로 찾기
        Queue<Port> queue = new ArrayDeque<>();
        Map<Port, Port> previous = new HashMap<>();
        Set<Port> visited = new HashSet<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            Port current = queue.poll();
            
            if (current.equals(end)) {
                // 경로 재구성
                return reconstruct(previous, end);
            }
            
            for (Port next : current.getConnectedPorts()) {
                if (visited.add(next)) {
                    previous.put(next, current);
                    queue.offer(next);
                }
            }
        }
        return Collections.emptyList();
    }
}

5.8 자기 점검 답변

Stack 클래스를 안 쓰고 ArrayDeque 를 쓰는 이유는?

답:
1. Stack 은 Vector 상속 → synchronized 비용
2. Stack 은 Java 1.0 Legacy
3. ArrayDeque 는 lock-free + 빠름
4. ArrayDeque 는 Queue + Stack + Deque 모두 지원
5. JavaDoc 도 ArrayDeque 권장

---

6️⃣ BlockingQueue (멀티스레드)

6.1 BlockingQueue 의 의미

일반 Queue:
  - 가득 차면 offer false
  - 비었으면 poll null
  - 호출자가 직접 처리

BlockingQueue:
  - 가득 차면 호출자 차단 (대기)
  - 비었으면 호출자 차단 (대기)
  - 멀티스레드 안전

→ 생산자-소비자 패턴 의 표준 도구.

6.2 BlockingQueue 메서드

public interface BlockingQueue<E> extends Queue<E> {
    
    // 차단 (blocking) 메서드
    void put(E e) throws InterruptedException;   // 가득 차면 대기
    E take() throws InterruptedException;        // 비면 대기
    
    // 타임아웃 메서드
    boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;
    E poll(long timeout, TimeUnit unit) throws InterruptedException;
}

핵심:

• put: 가득 차면 대기 (블로킹)
• take: 비면 대기
• 타임아웃: 일정 시간만 대기

6.3 메서드 페어 종합 (BlockingQueue)

동작	강제	안전	차단	타임아웃
삽입	add(e)	offer(e)	put(e)	offer(e, t, u)
제거	remove()	poll()	take()	poll(t, u)
조회	element()	peek()	—	—

→ 4가지 선택지!

6.4 BlockingQueue 구현체

ArrayBlockingQueue:
  - 고정 크기 배열
  - 가장 단순
  - 생성 시 크기 지정 필요

LinkedBlockingQueue:
  - 노드 사슬 (Optional 한 최대 크기)
  - 무제한 (또는 지정 크기)

PriorityBlockingQueue:
  - 우선순위 + 블로킹
  - 무제한 (poll/take 만 우선순위)

DelayQueue:
  - 지연 시간 후 가져갈 수 있는 큐
  - 스케줄링에 유용

SynchronousQueue:
  - 크기 0 (! 직접 전달)
  - 생산자 ↔ 소비자 핸드오프

LinkedTransferQueue:
  - SynchronousQueue + LinkedBlockingQueue

6.5 생산자-소비자 패턴

public class ShipmentProcessor {
    
    private final BlockingQueue<Shipment> queue = 
        new LinkedBlockingQueue<>(1000);   // 최대 1000개
    
    // 생산자
    public void receive(Shipment s) throws InterruptedException {
        queue.put(s);   // 가득 차면 대기
    }
    
    // 소비자 (별도 스레드)
    public void start() {
        new Thread(() -> {
            while (!Thread.currentThread().isInterrupted()) {
                try {
                    Shipment s = queue.take();   // 비면 대기
                    process(s);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    break;
                }
            }
        }).start();
    }
}

→ 생산자/소비자 분리 + 자동 동기화.

6.6 BlockingQueue 의 가치

일반 Queue + 직접 동기화:
  - 락 직접 관리
  - 대기 로직 직접
  - 깨우기 직접
  - 복잡 + 버그 위험

BlockingQueue:
  - 모든 동기화 자동
  - 차단/깨우기 자동
  - 단순 코드
  - 안전성 보장

6.7 ILIC 사용 사례

사례 1 — 알림 발송 큐

@Service
public class NotificationService {
    
    private final BlockingQueue<NotificationTask> queue = 
        new LinkedBlockingQueue<>();
    
    @PostConstruct
    public void start() {
        Executors.newFixedThreadPool(4).submit(() -> {
            while (true) {
                try {
                    NotificationTask task = queue.take();
                    send(task);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    return;
                }
            }
        });
    }
    
    public void enqueue(NotificationTask task) {
        queue.offer(task);   // 가득 차면 즉시 false 반환
    }
}

사례 2 — 배치 처리 파이프라인

public class ShipmentBatchProcessor {
    
    private final BlockingQueue<Shipment> stage1Queue = new LinkedBlockingQueue<>(100);
    private final BlockingQueue<EnrichedShipment> stage2Queue = new LinkedBlockingQueue<>(100);
    private final BlockingQueue<ValidatedShipment> stage3Queue = new LinkedBlockingQueue<>(100);
    
    public void start() {
        // Stage 1: 데이터 보강
        startWorker(stage1Queue, stage2Queue, this::enrich);
        // Stage 2: 검증
        startWorker(stage2Queue, stage3Queue, this::validate);
        // Stage 3: 저장
        startWorker(stage3Queue, null, this::persist);
    }
}

→ 파이프라인 처리.

6.8 자기 점검 답변

LinkedBlockingQueue 와 ArrayBlockingQueue 의 차이는?

답:

• ArrayBlockingQueue:

  • 고정 크기 배열
  • 생성 시 크기 지정 필요
  • 메모리 효율 (예측 가능)
  • 락 1개 (생산자/소비자 공유)

• LinkedBlockingQueue:

  • 노드 기반
  • 무제한 또는 크기 지정 가능
  • 락 2개 (생산자/소비자 분리) → 동시성 ↑
  • 메모리 더 사용

→ 큐 크기가 명확하면 ArrayBlockingQueue, 가변이면 LinkedBlockingQueue.

---

7️⃣ ILIC 실무 — 작업 큐와 이벤트 큐

7.1 시나리오별 Queue 선택

시나리오 1 — 단순 단일 스레드 큐

public class EventBuffer {
    private final Queue<Event> queue = new ArrayDeque<>();
    
    public void add(Event e) {
        queue.offer(e);
    }
    
    public Event next() {
        return queue.poll();
    }
}

→ ArrayDeque (단순, 빠름).

시나리오 2 — 멀티스레드 큐 (락-프리)

public class EventBus {
    private final Queue<Event> queue = new ConcurrentLinkedQueue<>();
    
    public void publish(Event e) {
        queue.offer(e);
    }
    
    public Event poll() {
        return queue.poll();
    }
}

→ ConcurrentLinkedQueue (락 없음, 멀티스레드 안전).

시나리오 3 — 멀티스레드 + 대기

public class TaskQueue {
    private final BlockingQueue<Task> queue = new LinkedBlockingQueue<>(1000);
    
    public void submit(Task task) throws InterruptedException {
        queue.put(task);   // 가득 차면 대기
    }
    
    public Task take() throws InterruptedException {
        return queue.take();   // 비면 대기
    }
}

→ LinkedBlockingQueue (대기 자동 처리).

시나리오 4 — 우선순위 작업 큐

public class PriorityTaskQueue {
    private final PriorityBlockingQueue<Task> queue = 
        new PriorityBlockingQueue<>(100, Comparator.comparing(Task::getPriority).reversed());
    
    public void submit(Task task) {
        queue.offer(task);
    }
    
    public Task take() throws InterruptedException {
        return queue.take();
    }
}

→ PriorityBlockingQueue (우선순위 + 멀티스레드).

시나리오 5 — 지연 작업

public class DelayedTaskQueue {
    private final DelayQueue<DelayedTask> queue = new DelayQueue<>();
    
    public void schedule(Runnable task, long delayMs) {
        queue.offer(new DelayedTask(task, delayMs));
    }
}

class DelayedTask implements Delayed {
    private final Runnable task;
    private final long executeAt;
    
    public DelayedTask(Runnable task, long delayMs) {
        this.task = task;
        this.executeAt = System.currentTimeMillis() + delayMs;
    }
    
    @Override
    public long getDelay(TimeUnit unit) {
        return unit.convert(executeAt - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
    }
    
    @Override
    public int compareTo(Delayed o) {
        return Long.compare(getDelay(TimeUnit.MILLISECONDS), o.getDelay(TimeUnit.MILLISECONDS));
    }
}

→ DelayQueue (스케줄링).

7.2 메시지 큐 (Kafka, RabbitMQ) 와의 관계

박승제씨가 ILIC 에서 만나는 외부 MQ:

// Kafka Producer 패턴
@Service
public class ShipmentEventPublisher {
    
    private final KafkaTemplate<String, ShipmentEvent> kafkaTemplate;
    
    public void publish(ShipmentEvent event) {
        kafkaTemplate.send("shipment-events", event.getId(), event);
        // Kafka 가 내부적으로 Queue 사용
    }
}

// 내부 버퍼 패턴
@Service
public class ShipmentEventBuffer {
    
    // 메모리 큐 (네트워크 실패 시 임시 보관)
    private final BlockingQueue<ShipmentEvent> bufferQueue = 
        new LinkedBlockingQueue<>(10000);
    
    @Async
    public void send(ShipmentEvent event) {
        try {
            kafkaTemplate.send("topic", event);
        } catch (Exception e) {
            bufferQueue.offer(event);   // 실패 시 버퍼
        }
    }
}

→ 외부 MQ + 내부 Queue 의 조합.

7.3 작업 처리 패턴

@Service
public class AsyncShipmentProcessor {
    
    private final BlockingQueue<ProcessingTask> taskQueue = 
        new LinkedBlockingQueue<>(1000);
    
    private final ExecutorService workers = Executors.newFixedThreadPool(4);
    
    @PostConstruct
    public void start() {
        for (int i = 0; i < 4; i++) {
            workers.submit(() -> {
                while (!Thread.currentThread().isInterrupted()) {
                    try {
                        ProcessingTask task = taskQueue.take();
                        task.execute();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                        return;
                    }
                }
            });
        }
    }
    
    public void submit(ProcessingTask task) {
        taskQueue.offer(task);
    }
    
    @PreDestroy
    public void shutdown() {
        workers.shutdown();
    }
}

→ 작업 큐 + 워커 풀 패턴.

7.4 ILIC Queue 사용 결정 표

시나리오	선택	이유
단일 스레드 큐	ArrayDeque	빠름, 효율
멀티스레드 큐 (락-프리)	ConcurrentLinkedQueue	빠른 동시성
멀티스레드 + 대기	LinkedBlockingQueue	자동 동기화
우선순위 처리	PriorityQueue / PriorityBlockingQueue	자동 정렬
지연 작업	DelayQueue	시간 기반
핸드오프	SynchronousQueue	직접 전달
Stack 필요	ArrayDeque (push/pop)	빠른 LIFO
외부 MQ 클라이언트	Kafka / RabbitMQ	분산 시스템

7.5 박승제씨의 ILIC 표준 패턴

// 패턴 1: 단순 Queue
Queue<Event> queue = new ArrayDeque<>();

// 패턴 2: 멀티스레드 큐
Queue<Event> sharedQueue = new ConcurrentLinkedQueue<>();

// 패턴 3: 작업 처리 큐
BlockingQueue<Task> workQueue = new LinkedBlockingQueue<>(1000);

// 패턴 4: 우선순위 작업
PriorityBlockingQueue<Task> priorityQueue = new PriorityBlockingQueue<>(
    100, Comparator.comparing(Task::getPriority).reversed()
);

// 패턴 5: ArrayDeque 다용도
ArrayDeque<Frame> stack = new ArrayDeque<>();   // Stack
stack.push(frame);
stack.pop();

7.6 ILIC 코드 리뷰 체크리스트

Queue 사용 검토:

선택:
  - LinkedList Queue → ArrayDeque
  - Stack 클래스 → ArrayDeque
  - 멀티스레드인데 일반 Queue → Concurrent 또는 Blocking
  - 우선순위 무시한 큐 → PriorityQueue

용량:
  - BlockingQueue 무한 → 크기 제한 검토
  - 메모리 폭발 위험 의식
  
인터럽트:
  - put/take 의 InterruptedException 처리?
  - Thread.currentThread().interrupt() 호출?

성능:
  - 빈번 호출인데 BlockingQueue → 락-프리 검토
  - 작은 큐는 ArrayBlockingQueue (메모리 효율)

7.7 자기 점검 답변

박승제씨가 ILIC 에서 Queue 가 가장 자주 등장하는 시나리오는?

답:
1. 이벤트 처리 큐 — 비동기 처리 (ConcurrentLinkedQueue 또는 LinkedBlockingQueue)
2. 알림 발송 큐 — LinkedBlockingQueue + 워커 스레드
3. 메시지 큐 (Kafka) 클라이언트 — 내부적으로 Queue 사용
4. 요청 처리 — Tomcat 의 요청 큐
5. 그래프 탐색 (BFS) — ArrayDeque

→ 대부분 ILIC 코드에서 Queue 가 직접 사용보다 숨겨진 형태 로 등장.

---

8️⃣ 흔한 실수 + 안티패턴

8.1 실수 1 — LinkedList 를 Queue 로

// △ 동작하지만 권장 X
Queue<Task> queue = new LinkedList<>();

// ✓ ArrayDeque
Queue<Task> queue = new ArrayDeque<>();

이유:

• 캐시 효율 ★★★
• 메모리 효율 ★★★
• Node 객체 안 만듦

8.2 실수 2 — Stack 클래스 사용

// ❌ Legacy
Stack<Frame> stack = new Stack<>();

// ✓ ArrayDeque
Deque<Frame> stack = new ArrayDeque<>();
stack.push(frame);
stack.pop();

8.3 실수 3 — BlockingQueue 의 InterruptedException 무시

// ❌ 인터럽트 무시
try {
    Task task = queue.take();
} catch (InterruptedException e) {
    // 그냥 무시
    e.printStackTrace();
}

문제:

• 스레드 중단 신호 무시
• Graceful shutdown 안 됨

해결:

// ✓ 인터럽트 다시 설정
try {
    Task task = queue.take();
} catch (InterruptedException e) {
    Thread.currentThread().interrupt();   // 신호 복원
    return;   // 또는 정리 후 종료
}

8.4 실수 4 — BlockingQueue 무한 사용

// ❌ 무한 큐
BlockingQueue<Event> queue = new LinkedBlockingQueue<>();   // 무한!

// 시나리오: 생산자가 소비자보다 빠르면?
while (true) {
    queue.put(event);   // 영원히 안 막힘
}
// → 메모리 누수 → OOM

해결:

// ✓ 크기 제한
BlockingQueue<Event> queue = new LinkedBlockingQueue<>(10000);
// 또는
BlockingQueue<Event> queue = new ArrayBlockingQueue<>(10000);

// 가득 차면:
queue.put(event);                    // 대기
queue.offer(event);                  // 즉시 false
queue.offer(event, 1, SECONDS);      // 1초 대기

8.5 실수 5 — PriorityQueue 순회 가정

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(3); pq.offer(8);

// ❌ 정렬 순서 가정
for (Integer i : pq) {
    // 정렬 순서 보장 X!
}

// ✓ 정렬 순서로 순회
while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

8.6 실수 6 — Queue 에 null 추가

ArrayDeque<String> deque = new ArrayDeque<>();
deque.offer(null);   // ❌ NullPointerException

ArrayDeque 는 null 거부.
→ Optional 또는 명시적 null 처리.

8.7 실수 7 — Concurrent 컬렉션 size 의 비정확성

ConcurrentLinkedQueue<Event> queue = new ConcurrentLinkedQueue<>();

int size = queue.size();   // O(n)! + 비정확

ConcurrentLinkedQueue.size():

• O(n) (전체 순회)
• 부정확 (멀티스레드 변경 중)
• 사용 권장 X

해결:

• 별도 카운터 (AtomicInteger)
• 또는 BlockingQueue 사용 (size 정확)

8.8 실수 8 — Queue 매개변수의 변경

public void process(Queue<Task> queue) {
    while (!queue.isEmpty()) {
        process(queue.poll());   // 호출자의 큐 비움!
    }
}

→ Phase 1 의 매개변수 안전 패턴.
→ 큐 매개변수 변경은 부작용 (side effect).

해결:

• 메서드명에 의도 명시 (drainAndProcess)
• 또는 사본 사용

8.9 ILIC Queue 안티패턴 체크리스트

박승제씨가 ILIC 에서 피할 것:

레거시:
  - Stack 클래스 → ArrayDeque
  - LinkedList Queue → ArrayDeque

멀티스레드:
  - 일반 Queue 멀티스레드 공유 → ConcurrentLinkedQueue
  - InterruptedException 무시 → 인터럽트 복원
  - 무한 BlockingQueue → 크기 제한

성능:
  - ConcurrentLinkedQueue.size() 호출 → 카운터 별도
  - PriorityQueue 순회 정렬 가정 → poll 반복

안전:
  - null 추가 시도 → Optional 사용
  - Queue 매개변수 변경 → 명시적 의도

---

9️⃣ 면접 + 자기 점검

9.1 면접 단골 질문 매핑

Q	핵심 답변
Queue 의 FIFO 의미?	First In First Out, 먼저 들어온 것 먼저 나감
offer vs add 차이?	offer 가득 차면 false, add 는 예외
poll vs remove 차이?	poll 비면 null, remove 는 예외
ArrayDeque vs LinkedList	배열 기반 vs 노드, ArrayDeque 가 거의 모든 면에서 우수
Stack 클래스 사용?	Legacy, ArrayDeque 권장
PriorityQueue 내부?	Binary Heap (배열 기반)
BlockingQueue 의미?	멀티스레드 + 자동 차단/대기
ConcurrentLinkedQueue?	락-프리 멀티스레드 Queue
Deque 의 역할?	양방향 큐, Stack + Queue 통합
LinkedBlockingQueue vs ArrayBlockingQueue?	노드 vs 배열, 락 2개 vs 1개
DelayQueue 사용처?	지연 작업, 스케줄링

9.2 자기 점검 체크리스트

기본 이해

• Queue 의 FIFO 의미를 안다
• 두 가지 메서드 페어 (강제/안전) 를 외운다
• ArrayDeque 의 원형 배열 구조를 안다
• PriorityQueue 의 Binary Heap 구조를 안다
• Deque 가 Queue + Stack 임을 안다

구현체 선택

• 일반 큐 → ArrayDeque
• 멀티스레드 락-프리 → ConcurrentLinkedQueue
• 멀티스레드 + 대기 → LinkedBlockingQueue
• 우선순위 → PriorityQueue
• 지연 → DelayQueue
• Stack → ArrayDeque (push/pop)

실전 적용

• LinkedList Queue 안 씀
• Stack 클래스 안 씀
• InterruptedException 처리
• BlockingQueue 크기 제한
• PriorityQueue 순회 가정 안 함

면접 대비

• 메서드 페어 4가지 (강제/안전/차단/타임아웃) 설명
• ArrayDeque 의 원형 배열 시각화
• Binary Heap 의 시간 복잡도
• 생산자-소비자 패턴 코드 작성
• ILIC 실무 사용 사례

---

🎯 핵심 요약 — 3줄 정리

1. Queue = FIFO + 두 가지 메서드 페어

• 강제 (예외): add, remove, element
• 안전 (false/null): offer, poll, peek
• BlockingQueue 는 추가: 차단 (put, take), 타임아웃

2. 구현체 선택

• 일반: ArrayDeque (LinkedList 대신)
• 멀티스레드 락-프리: ConcurrentLinkedQueue
• 멀티스레드 + 대기: LinkedBlockingQueue
• 우선순위: PriorityQueue (Binary Heap)
• Stack: ArrayDeque (Stack 클래스 대신)
• 양방향: Deque (ArrayDeque)

3. ILIC 실무

• 이벤트 처리, 작업 큐, 메시지 큐 클라이언트
• ArrayDeque (단일) / ConcurrentLinkedQueue (멀티) / LinkedBlockingQueue (대기)
• InterruptedException 항상 처리
• 무한 BlockingQueue 회피

---

📚 다음으로...

Unit 2.5 — Map 5형제 (HashMap / LinkedHashMap / TreeMap / Hashtable / ConcurrentHashMap)

이번 Unit에서 Queue 를 봤다면, 다음은 Map 의 5가지 구현체.

박승제씨가 1주차에 만든 HashMap PPT 의 토대 위에:

• HashMap 의 내부 (해시 테이블)
• LinkedHashMap (LRU 캐시 구현 가능)
• TreeMap (Red-Black Tree)
• Hashtable (legacy)
• ConcurrentHashMap (멀티스레드 + 최적화)

→ 1주차 HashMap PPT 학습이 응집되는 정점.

Phase 2 진행 상황

🚀 Phase 2 — 컬렉션 프레임워크 전체 지도
  ✅ Unit 2.1 배열의 한계와 컬렉션의 등장
  ✅ Unit 2.2 Set 3형제
  ✅ Unit 2.3 List 3형제
  ✅ Unit 2.4 Queue ← 여기
  ⏭ Unit 2.5 Map 5형제
  ⏭ Unit 2.6 컬렉션 전체 지도 정리

3주차 누적 진행

✅ Phase 1 — Pass by Value (1.1 ~ 1.3 완주)
🚀 Phase 2 — 컬렉션 프레임워크 (4/6 진행)

총: 7/43 Unit 작성 (약 16%)