큐 (Queue)

큐 (Queue)

선입선출(FIFO, First In First Out) 원칙을 따르는 선형 자료구조로, 한쪽 끝(rear)에서 삽입하고 다른 쪽 끝(front)에서 삭제가 이루어지는 대기열 구조

목적: FIFO 순서 유지, 순차 처리, 버퍼링, 작업 스케줄링

특징: FIFO, 양쪽 접근(front/rear), 순차 처리, 공정성

연산

• •enqueue(item): rear에 삽입, O(1)
• •dequeue(): front 제거 및 반환, O(1)
• •front()/peek(): front 조회(제거 없음), O(1)
• •isEmpty(): 비어있는지 확인, O(1)
• •size(): 요소 개수, O(1)

구현

• •배열(선형 큐): front 이동 시 공간 낭비
• •원형 큐(Circular Queue): 인덱스 순환, 공간 효율
• •연결 리스트: 동적 크기, front/rear 포인터

원형 큐: (rear+1) % capacity, (front+1) % capacity, 공간 재사용

시간 복잡도: enqueue/dequeue/front 모두 O(1)

공간 복잡도: O(n)

장점: FIFO 보장, 빠른 연산(O(1)), 순차 처리, 공정한 순서

단점: 제한적 접근(front/rear만), 중간 요소 접근 불가, 선형큐는 공간 낭비

적용사례

• •BFS(너비우선탐색)
• •프로세스 스케줄링
• •프린터 대기열
• •네트워크 패킷 버퍼
• •캐시(FIFO 교체)
• •메시지 큐
• •이벤트 처리

비교: 큐(FIFO/양쪽/순차) vs 스택(LIFO/한쪽/역순)

연관: 스택, 덱, 원형 큐, BFS, 우선순위 큐