[JAVA/자료구조] 선형구조 - 큐(Queue)

Queue

• 선형 구조의 형태이며 먼저 들어온 데이터가 먼저 나가는 자료구조이며 선입선출(FIFO, First-In-First-Out)의 특성을 가진다

큐의 동작 과정

Enqueue : 데이터 추가

• 새로운 데이터가 큐의 입구로 들어가는 과정
• rear의 위치는 다음 데이터가 삽입될 위치로 이동

rear & front : 입구와 출구

• rear : 큐의 맨 뒤 / 데이터가 들어오는(추가되는) 곳
• front : 큐의 맨 앞 / 데이터가 나가는(삭제되는) 곳

Dequeue : 데이터 꺼내기

• 맨 앞에 있는 데이터만 큐의 출구로 나갈 수 있음
• front의 위치는 다음 데이터가 추출될 위치로 이동

• 데이터 추가 : add() vs offer()
  • add() - 큐가 꽉 차서 못 넣으면 IllegalStateException 에러 발생
  • offer() - 큐가 꽉 차면 false 반환 (실무나 코딩테스트에서는 에러가 안터지는 offer 자주 사용)

• 데이터 꺼내기 : remove() vs poll()
  • remove() - 큐가 비어있는데 꺼내라고 하면 NoSuchElementException 에러 발생
  • poll() - 큐의 맨 앞 데이터를 제거 하고 반환 / 큐가 비어있으면 null 반환

• 데이터 확인하기 : element() vs peek()
  • element() - 큐가 비어있으면 에러 발생
  • peek() - 큐가 비어있으면 null 반환 (데이터가 삭제되지 않음)

• 모든 데이터 제거 - clear()

---

큐 예시

Queue<자료형> queue = new LinkedList<>();

// 큐의 데이터 추가
queue.offer("Apple");
queue.offer("Orange");
queue.offer("Banana");

// 큐의 데이터 꺼내기 - 첫번째 데이터 제거(Apple 삭제)
queue.poll();

---

큐 사용 에시

• 먼저 온 순서대로 업무를 처리할 때
• BFS(너비 우선 탐색) - 인접한 노드를 우선으로 방문해야 하는 경우

---

큐 장단점

• 장점
  • 데이터의 순서가 중요한 작업에 적합
• 단점
  • 큐의 크기가 고정되어 있으면 데이터가 가득 차면 더 이상 삽입이 불가능