📍 특수한 형태의 큐?
일반 큐에 관한 글은
https://velog.io/@hyong/data-structure-Queue
일반 큐는 FIFO(First-In, First-Out) 방식이다.
하지만 특정 요구사항에 따라 큐의 동작 방식을 변형하여
- 원형 큐
- 우선순위 큐
- 덱
과 같은 특수한 형태의 큐를 사용할 수 있다.
1. 원형 큐 Circular Queue
: 마지막 위치가 첫 번째 위치와 연결된 구조이다.
주로, 배열을 사용하여 큐를 구현할 때 사용된다.
기존의 선형 큐는 배열을 사용하면 메모리 낭비가 발생할 수 있지만, 원형 큐는 이를 해결한다.
- 공간 재사용: 배열의 맨 뒤를 사용한 후 배열의 맨 앞으로 돌아올 수 있다.
- front와 rear 포인터로 데이터 삽입/삭제 위치를 관리한다.
- 큐가 가득 찬 상태와 비어 있는 상태를 구별하기 위해 추가 조건이 필요하다.
2. 우선순위 큐 Priority Queue
: 데이터의 우선순위에 따라 큐에서 먼저 처리될 데이터가 결정된다.
일반 큐와 같이 들어오는 순서와 상관없이 우선순위에 따라 가장 높은 우선순위를 가진 데이터가 먼저 처리된다.
- 우선순위 기준: 데이터 삽입 시 우선순위를 기준으로 정렬한다.
- 힙(Heap) 자료구조로 구현하는 경우가 많다.
최소 힙: 우선순위가 낮은 값이 먼저 처리.
최대 힙: 우선순위가 높은 값이 먼저 처리. - 다익스트라 알고리즘에서 많이 사용한다.
3. 덱 Deque: Double-Ended Queue
: 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐이다.
덱은 스택과 큐의 기능을 모두 포함하고 있다.
- 양쪽에서 삽입/삭제 가능하다.
- 배열 기반: 원형 큐처럼 공간 활용할 수 있다.
- linked list 기반: 동적 메모리 할당으로 구현할 수 있다.
