TIL - Queue (09.22)

📚 오늘 공부한 내용 - Queue 자료구조

🎯 큐(Queue)란?

큐는 FIFO(First In First Out) 원칙을 따르는 자료구조입니다. 스택과는 정반대로, 가장 먼저 넣은 것이 가장 먼저 나오는 구조입니다.

🚶‍♂️ 큐의 동작 원리

데이터 넣기: 1 → 2 → 3

입구 ←─ [3] [2] [1] ─→ 출구
      (offer)     (poll)

데이터 빼기: 1 → 2 → 3

핵심: 넣는 곳(뒤쪽)과 빼는 곳(앞쪽)이 다르며, 먼저 온 순서대로 처리됩니다.

---

🔧 큐의 주요 연산

기본 연산

• offer: 큐에 값을 넣는 연산 (뒤쪽으로 추가)
• poll: 큐에서 값을 꺼내는 연산 (앞쪽에서 제거)
• peek: 다음에 꺼낼 요소를 확인 (꺼내지 않고 조회만)

코드 예시

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

// offer 연산 - 데이터 추가
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue); // [1, 2, 3]

// peek 연산 - 다음 요소 조회
System.out.println("다음 요소: " + queue.peek()); // 1

// poll 연산 - 데이터 꺼내기
System.out.println("꺼낸 요소: " + queue.poll()); // 1
System.out.println("꺼낸 요소: " + queue.poll()); // 2
System.out.println("꺼낸 요소: " + queue.poll()); // 3

---

🏗️ Queue 인터페이스와 구현체

상속 구조

Collection
    ↓
  Queue
    ↓
  Deque

• Queue는 Collection의 자식 인터페이스
• List, Set과 같은 레벨에 위치

주요 구현체

1. ArrayDeque (권장 ⭐)

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

• 성능: 매우 빠름
• 메모리: 효율적인 배열 기반
• 추천: 일반적인 큐 용도로 가장 적합

2. LinkedList

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

• 다중 인터페이스: List와 Deque 모두 구현
• 구조: 연결 리스트 기반
• 특징: 양방향 접근 가능

// LinkedList 클래스 정의
public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

---

⚡ Stack vs Queue 비교

구분 Stack Queue

원칙	LIFO (후입선출)	FIFO (선입선출)
넣기	push (위쪽)	offer (뒤쪽)
빼기	pop (위쪽)	poll (앞쪽)
조회	peek (위쪽)	peek (앞쪽)
예시	함수 호출, 뒤로가기	작업 대기열, 프린터 큐

---

💡 실무에서의 큐 활용

언제 큐를 사용할까?

1. 작업 대기열 (Task Queue)
2. 프린터 인쇄 대기열
3. BFS(너비 우선 탐색) 구현
4. CPU 스케줄링
5. 캐시 구현 (LRU Cache)
6. 스트리밍 데이터 처리

큐의 특징

• 삽입: O(1) - 뒤쪽에 추가
• 삭제: O(1) - 앞쪽에서 제거
• 순서: 공정한 처리 (먼저 온 순서대로)

---

🎯 오늘의 핵심 포인트

1. FIFO 원칙: 먼저 들어간 것이 먼저 나온다
2. 주요 연산: offer(넣기), poll(빼기), peek(조회)
3. 구현체 선택: ArrayDeque 권장
4. 스택과 반대: 공정한 순서 처리가 특징
5. 실무 활용: 대기열, BFS, 스케줄링 등