[자료구조] 큐(Queue)

📌큐 : 선입선출(First In First Out, FIFO)의 자료구조로, 가장 먼저 삽입된 데이터가 먼저 처리된다.

 

큐 구현

 

Java에서 큐는 주로 Queue<E> 인터페이스를 사용하고, LinkedList<E> / ArrayDeque<E> / PriorityQueue<E> 클래스를 사용해서 구현할 수 있다.

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

 

 

기본 메서드

• offer(E e) : 큐의 맨 뒤에 요소를 추가한다. 
  • 성공하면 true, 실패하면 false 반환
• poll() : 큐의 맨 앞에 있는 요소를 제거하고 반환한다. 
  • 큐가 비어있으면 null 반환
• peek() : 큐의 맨 앞에 있는 요소를 제거하지 않고 반환한다.
  • 큐가 비어있으면 null 반환
• isEmpty() : 큐가 비어 있는지 여부 확인
• size() : 큐 안의 요소 개수 반환

 

 

코딩 테스트 빈출 유형

 

1. 너비 우선 탐색 (BFS)

*BFS : 그래프나 트리의 모든 노드를 방문할 때 사용하는 알고리즘으로, 가까운 노드들부터 탐색하는 구조

***후에 DFS/BFS 게시글에서 자세히 다룰 예정***

 

 

2. 프린터 문제 (우선순위 큐)

*우선순위 큐 : 각 요소에 우선순위를 부여하여 우선순위가 높은 요소를 먼저 처리하는 자료구조

 

📄 유형 이해 코드 📄

//reverseOrder() 메서드 사용으로 우선순위가 역순으로 적용되어, 가장 큰 값이 먼저나오도록 동작
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(1);
pq.offer(3);
pq.offer(2);
System.out.println(pq.poll());   
// 출력: 3

 

 

3. 카드 문제 (원형 큐 / 회전 큐) 

: 카드를 차례대로 버리고, 남은 카드를 찾는 문제

*회전 큐 : 큐에서 요소를 꺼낸 후 다시 삽입하는 방식

 

📄 유형 이해 코드 📄

Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(1);
deque.offerLast(2);
deque.offerLast(3);

deque.pollFirst();  // 첫 번째 요소 제거
deque.offerLast(2); // 큐의 끝에 다시 추가

 

 

큐 사용 시 유의 사항

• 구현 방식 선택 : 큐에서 사용되는 클래스들은 서로 다른 특징을 지녀, 상황에 맞는 클래스를 사용하는 것이 중요하다.
  
  • LinkedList: 노드 기반으로 구현되어 삽입 및 삭제 연산에서 일정한 성능을 유지한다.
  • ArrayDeque: 배열 기반으로 메모리 효율성이 좋고 성능이 빠르다.
• 메모리 관리 : 큐가 계속 커지는 시나리오에서는 메모리 소모가 커질 수 있기에, 원형 큐와 같은 자료구조를 유연하게 사용해야한다.