[자료구조] 큐(Queue)

큐(Queue)란?

큐(Queue)는 한쪽에서 데이터를 삽입하고 반대쪽에서 데이터를 삭제하는 선입선출(FIFO, First In First Out) 자료구조입니다.

 

 

큐의 현실 예시: 줄 서기

식당에서 줄을 서면, 가장 먼저 도착한 사람이 가장 먼저 입장합니다. 이는 큐의 선입선출 특징과 같아 큐를 이해하는 좋은 예시가 됩니다.

 

큐의 종류

1. 원형 큐 (Circular Queue)
   • 삽입과 삭제 위치를 원형으로 연결하여 사용합니다.
   • 배열의 끝에 도달해도 공간을 재활용할 수 있는 특징이 있습니다.
   • 배열 기반 큐에서 공간 낭비를 줄이기 위해 사용됩니다.
2. 덱 (Deque: Double-Ended Queue)
   • 양쪽에서 삽입과 삭제가 가능한 큐입니다.
   • Java에서는 기존의 Queue보다 Deque를 더 권장합니다.
     • 이유: Deque는 Queue와 Stack의 기능을 모두 포함하며 유연하게 사용할 수 있기 때문입니다.
3. 우선순위 큐 (Priority Queue)
   • 저장된 순서와 관계없이 우선순위가 높은 요소가 먼저 삭제됩니다.
   • Heap 자료구조를 기반으로 구현됩니다. (Heap은 나중에 자세히 설명 예정)

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1); // 앞쪽에 삽입
deque.addLast(2);  // 뒤쪽에 삽입
deque.removeFirst(); // 앞쪽에서 삭제
deque.removeLast();  // 뒤쪽에서 삭제

정리

• 큐(Queue)는 FIFO를 따르는 기본 자료구조입니다.
• 덱(Deque)는 양쪽에서 삽입/삭제가 가능하며, Java에서는 Queue보다 Deque를 더 권장합니다.
• 우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 처리되며, Heap을 기반으로 합니다.
• 원형 큐는 배열의 끝과 시작을 연결하여 공간 효율성을 높입니다.