1. Queue의 정의 및 핵심 원리
- FIFO (First In First Out): 시간 순서상 먼저 삽입된 데이터가 먼저 출력되는 선입선출 방식의 자료구조.
- 특징: 데이터의 한쪽 끝에서는 삽입이, 반대쪽 끝에서는 삭제가 일어나는 논리적 구조.
2. 주요 연산 및 시간 복잡도
큐의 양 끝에서 데이터 작업이 이루어지므로 연산 속도가 매우 빠름.
| 연산 (Operation) | 설명 | 시간 복잡도 |
|---|---|---|
| Enqueue | 큐의 맨 뒤(Rear)에 새로운 데이터를 추가하는 작업. | O(1) |
| Dequeue | 큐의 맨 앞(Front)에서 데이터를 추출 및 삭제하는 작업. | O(1) |
3. 구현 방식에 따른 차이점
메모리 활용 및 성능 특성에 따라 두 가지 방식으로 구현 가능.
Array-Based Queue (배열 기반)
- 특징: 연속된 메모리 공간을 사용하며 주로 원형 큐(Circular Queue) 형태로 구현.
- 장점: 데이터 접근 성능이 전반적으로 우수함.
- 단점: 고정된 크기 문제로 리사이징(Resize) 발생 시 일시적인 성능 저하 가능성 존재.
List-Based Queue (연결 리스트 기반)
- 특징: 싱글 연결 리스트(Singly-Linked List)를 사용하여 구현.
- 장점: 데이터 추가 시마다 메모리를 할당하므로 크기 제한 및 메모리 낭비가 적음.
- 단점: 매번 메모리 할당/해제 과정이 필요하여 전반적인 런타임 속도가 상대적으로 느릴 수 있음.
4. 확장 및 실제 활용 사례
확장된 자료구조
- Deque (Double-Ended Queue): 양쪽 끝에서 삽입과 삭제가 모두 가능한 구조.
- Priority Queue (우선순위 큐): 시간 순서가 아닌 데이터의 우선순위에 따라 출력 순서가 결정되는 구조.
활용 예시
- 시스템 관리: CPU 스케줄링, 프린터 인쇄 대기열, 프로세스 관리.
- 네트워크/캐시: 캐시(Cache) 구현, 데이터 패킷 전송 대기열.
- 알고리즘: 그래프의 너비 우선 탐색(BFS) 구현.
5. 추가 정리
Q. Array-Base와 List-Base 중 어느 것이 더 효율적인가?
- Array-Base: 전반적인 성능은 더 좋으나, 배열 크기 초과 시 Dynamic Array처럼 리사이징이 필요하며 이때 Amortized O(1)의 복잡도를 가짐.
- List-Base: 삽입 시마다 동적 할당을 수행하므로 리사이징 걱정은 없으나 성능상 오버헤드가 발생함.
정리
- Queue: 선입선출(FIFO)을 원칙으로 하며 Enqueue와 Dequeue 모두 O(1)의 높은 효율을 보임.
- 원형 큐: 배열 기반 큐의 메모리 낭비(중간 삭제 시 발생하는 빈 공간)를 해결하기 위한 효율적인 구현 방식.
- 포인트: 스택(LIFO)과의 차이점을 명확히 인지하고, BFS나 스케줄링 등 실제 큐가 활용되는 기술적 사례를 연관 지어 설명하는 것이 중요함.
출처
- Pat Morin, Open Data Structures - Array-Based Lists https://opendatastructures.org/versions/edition-0.1e/ods-java/2_Array_Based_Lists.html
- Pat Morin, Open Data Structures - Linked Lists https://opendatastructures.org/versions/edition-0.1e/ods-java/3_Linked_Lists.html
- Python Documentation, collections.deque https://docs.python.org/3/library/collections.html#collections.deque