[큐] 배열 기반 큐와 연결리스트 기반 큐

생활 속 큐의 예시

• 은행 대기열: 고객들이 차례로 도착하고, 도착한 순서대로 서비스를 받습니다.
• 프린터 작업: 문서들이 프린터 대기열에 차례로 추가되며, 추가된 순서대로 인쇄됩니다.
• 콜센터 전화 대기열: 전화가 순서대로 대기열에 들어가고, 차례로 연결됩니다.
• 온라인 티켓 예매: 사용자들이 서버에 접속해 대기열에 들어가고, 순서에 따라 티켓을 구매할 수 있습니다.

 

 

큐 자료구조의 ADT(추상 데이터 타입)

Enqueue: 큐의 끝에 새로운 요소를 추가합니다.
Dequeue: 큐의 시작에서 요소를 제거하고 반환합니다.
Peek / Front: 큐의 시작에 있는 요소를 조회하지만 제거하지 않습니다.
IsEmpty: 큐가 비어있는지 확인합니다.
Size: 큐에 저장된 요소의 개수를 반환합니다.

 

 

배열 기반 큐(원형)

구성요소

• 배열: 요소들을 저장하는 정적 배열입니다.
• Front 포인터: 큐의 시작을 가리킵니다.
• Rear 포인터: 큐의 끝을 가리킵니다. = 큐.length - 1
• Size/Capacity: 배열의 최대 크기입니다.

 

작동 원리

• Enqueue: Rear 포인터 위치에 요소를 추가하고 Rear를 증가시킵니다.
• Dequeue: Front 포인터 위치의 요소를 제거하고 Front를 증가시킵니다.
• Wrap Around: 순환 큐(circular queue)의 경우, 포인터가 배열 끝에 도달하면 처음으로 돌아갑니다.
• 배열의 경계를 넘어가는 경우를 감안해서 rear++ 대신에 rear = ( rear+1 )%queue.length 나머지 연산을 이용합니다.

 

주요 메서드

• offer(E e) / add(E e) : 큐의 끝에 요소를 추가. offer는 큐가 가득 찼을 때 false를 반환하고, add는 IllegalStateException을 던짐
• poll() / remove() : 큐의 시작에서 요소를 제거하고 반환. poll은 큐가 비어있을 때 null을 반환하고, remove는 NoSuchElementException을 던짐
• peek() / element() :큐의 시작에 있는 요소를 조회하지만, 제거하지 않음. peek은 큐가 비어있을 때 null을 반환하고, element는 NoSuchElementException을 던짐.
• size() : 큐에 저장된 요소의 수를 반환
• isEmpty() :큐가 비어있는지 여부를 반환

 

 

 

연결 리스트 기반 큐

구성요소

• 노드: 각 요소는 노드로 표현됩니다.
• 헤드 포인터: 큐의 시작을 가리킵니다.
• 테일 포인터: 큐의 끝을 가리킵니다.

 

작동 원리

• Enqueue: 테일에 요소를 추가하고, 테일 포인터를 업데이트합니다.
• Dequeue: 헤드에 있는 요소를 제거하고, 헤드 포인터를 업데이트합니다.

 

주요 메서드

• offer(E e) / add(E e) : 큐의 끝에 요소를 추가. offer와 add는 기능적으로 동일하지만, add는 IllegalStateException을 던짐
• poll() / remove() : 큐의 시작에서 요소를 제거하고 반환. poll은 큐가 비어있을 때 null을 반환하고, remove는 NoSuchElementException을 던짐,
• peek() / element() : 큐의 시작에 있는 요소를 조회하지만, 제거하지 않음. peek은 큐가 비어있을 때 null을 반환하고, element는 NoSuchElementException을 던짐
• size() : 큐에 저장된 요소의 수를 반환
• isEmpty() : 큐가 비어있는지 여부를 반환

 

 

큐의 장점과 단점

장점

• 공정성: FIFO(First In, First Out) 원칙에 따라 요소들이 순서대로 처리됩니다.
• 간단함: 큐의 연산들은 구현하기 쉽고 이해하기 쉽습니다.

단점

• 비효율성: 배열 기반 큐에서 공간이 고정되어 있어 크기 조정이 어렵습니다. 연결 리스트 기반 큐는 포인터를 위한 추가 공간이 필요합니다.
• 속도: 연결 리스트 기반 큐에서는 요소 접근이 느릴 수 있습니다.

 

 

큐의 확장

• 우선순위 큐(Priority Queue): 요소들이 우선순위에 따라 정렬되고, 가장 높은 우선순위를 가진 요소가 먼저 나옵니다.
• 순환 큐(Circular Queue): 배열을 사용하여 효율적으로 공간을 재사용합니다.
• 덱(Deque): 양쪽 끝에서 삽입과 삭제가 가능한 큐의 일반화된 형태입니다.

 

1. LinkedList:
   • LinkedList 클래스는 List와 Deque 인터페이스를 모두 구현합니다.
   • 연결 리스트 기반으로, 큐의 모든 기능을 제공합니다.
   • 동적으로 요소를 추가하고 제거할 수 있으며, 추가 및 제거 작업이 O(1)의 시간 복잡도를 가집니다.
2. ArrayDeque:
   • ArrayDeque는 원형 배열을 사용하여 구현된 더블 엔드 큐(Deque)입니다.
   • 큐와 스택의 기능을 모두 제공하며, 선형 배열 기반 큐에 비해 공간 효율성이 더 높습니다.
   • 추가 및 제거 작업이 O(1)의 시간 복잡도를 가집니다.
3. PriorityQueue:
   • PriorityQueue는 우선 순위 큐를 구현합니다.
   • 요소들은 자연 순서 또는 비교자(comparator)에 따라 정렬됩니다.
   • 요소의 추가와 제거는 O(logn)의 시간 복잡도를 가집니다.
4. ConcurrentLinkedQueue:
   • 멀티스레드 환경에서 사용하기 위한 비차단(non-blocking) 연결 리스트 기반 큐입니다.
   • 동시성(concurrency)에 강하며, 높은 동시 접근에서 성능이 뛰어납니다.
5. LinkedBlockingQueue:
   • 멀티스레드 환경에서 사용되는 차단(blocking) 연결 리스트 기반 큐입니다.
   • 스레드 안전(thread-safe)하며, 추가 및 제거 작업 시 빈 큐나 가득 찬 큐에서 스레드를 차단(대기 상태로 만듦)할 수 있습니다.

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」