알고리즘
Queue
다른 이름: 큐 , FIFO
정의
First-In-First-Out (FIFO) 자료구조. 먼저 넣은 것이 먼저 나옴. enqueue(삽입), dequeue(제거) O(1). 원형 버퍼 또는 연결 리스트 구현. BFS, 프린터 대기열, 작업 스케줄링, 메시지 큐에 사용
상세 설명
기술 스펙
- enqueue: 뒤에 삽입 O(1)
- dequeue: 앞에서 제거 O(1)
- peek/front: 앞 조회 (제거 안 함) O(1)
- 구현: 원형 버퍼 (배열 + 두 포인터) 또는 연결 리스트
- Python: collections.deque (양방향 큐)
- C++: std::queue, Java: Queue, JavaScript: Array (비효율)
실무 활용
- BFS: 너비 우선 탐색 (레벨 순회)
- 작업 대기열: 프린터, CPU 스케줄링
- 메시지 큐: RabbitMQ, Kafka (분산 시스템)
- 캐시: LRU Cache (큐 + 해시맵)
- 네트워크: 패킷 버퍼
장점
- 빠른 연산: enqueue/dequeue O(1)
- 순서 보장: FIFO 특성
- 공평성: 먼저 온 것부터 처리
- BFS 최적: 최단 경로 보장
단점 및 제약
- 순차 접근만: 중간 요소 접근 불가
- 고정 크기: 원형 버퍼는 오버플로우
- 메모리 단편화: 연결 리스트 포인터 오버헤드
호환성
C++ std::queue, Python collections.deque, Java Queue, JavaScript Array
표준 정보
표준화 기구: 자료구조 교과서 표준
출시 연도: 1946년