[자료구조] 5. 큐(Queue)

5. 큐(Queue)

큐의 구조

 

 

정의

• FIFO(First In First Out) 구조를 가진 자료구조
• 먼저 들어온 데이터가 먼저 나가는 방식(줄을 서는 것처럼 순서대로 처리)

 

종류

1. 기본 큐 : 선형적으로 데이터를 삽입하고 삭제하는 방식
2. 원형 큐(Circular Queue) : 배열의 끝과 시작이 연결된 형태로, 배열의 공간을 지속적으로 재활용
3. 우선순위 큐(Priority Queue) : 각 요소에 우선순위가 부여되어 우선순위가 높은 요소부터 삭제됨

 

기본 구조

• 요소
• 앞(Front, Head), 뒤(Back, Rear, Tail)

 

특징

Circular Queue(효율적인 메모리 사용을 위해 자주 사용)

 

• FIFO(First In First Out) 구조
• 동적 크기 변화 : 큐는 동적으로 크기가 변할 수 있으며
• 단 방향 데이터 흐름 : 데이터는 한 방향으로만 흐르고, 삽입은 뒤에서, 삭제는 앞에서 발생
• 효율적인 메모리 사용 : 원형 큐(Circular Queue)에서는 메모리 재활용이 가능

 

활용 예시

• 프로세스 스케줄링 : 운영 체제에서 프로세스들을 순차적으로 처리
• 네트워크 패킷 관리 : 데이터 패킷들이 순차적으로 처리되도록 관리
• 멀티스레딩 시스템 : 스레드 간 작업 큐나 메시지 큐를 사용하여 데이터 처리
• 게임 행동 큐 : 게임에서 캐릭터의 행동을 순차적으로 처리하는 데 사용

 

장단점

 

장점

• FIFO 구조 : 데이터가 들어온 순서대로 처리되어 직관적인 데이터 흐름을 보장
• 단방향 데이터 처리 : 데이터를 한 방향에서만 처리하여 연산이 직관적이고 관리가 용이
• 메모리 효율성(Circular Queue) : 원형 큐를 사용하면 메모리를 재활용하여 효율적인 공간 활용 가능
• 프로세스 간 통신 : 멀티스레드 시스템에서 메시지 큐를 통해 프로세스 간 데이터 전달이 가능

단점

• 탐색 시간 소모 : 큐 내에서 특정 데이터를 찾기 위해 전체 큐를 탐색해야 하므로 O(n) 시간 소모
• 임의의 데이터 삭제 불가 : FIFO 방식으로만 데이터를 삭제 할 수 있어서 임의의 데이터 삭제 불가

 

연산과 시간 복잡도

연산	설명	연산 절차	시간 복잡도
Enqueue	큐의 뒤(Rear) 부분에 데이터를 추가하는 연산	1. 데이터를 큐의 뒤(Rear)에 추가 2. rear 포인터를 업데이트하여 새로운 데이터 위치를 가리킴	O(1)
Dequeue	큐의 앞(Front) 부분에서 데이터를 제거하는 연산	1. front 포인터가 가리키는 데이터를 제거 2. front 포인터를 한 칸 아래로 이동	O(1)
Front	큐의 앞(Front) 부분의 데이터를 확인하는 연산	1. front 포인터가 가리키는 데이터를 반환	O(1)
Rear	큐의 뒤(Rear) 부분의 데이터를 확인하는 연산	1. rear 포인터가 가리키는 데이터를 반환	O(1)
isEmpty	큐가 비었는지 확인하는 연산	1. front 포인터가 rear와 같은지 확인하여 큐가 비었는지 판단	O(1)
isFull	큐가 가득 찼는지 확인하는 연산 (배열 기반 큐에서만 사용)	1. 큐의 크기와 rear 포인터를 비교하여 큐가 가득 찼는지 판단	O(1)