[자료구조] 큐(Queue)

큐(Queue)

• 선입선출(First-In-First-Out, FIFO) 원칙에 따라 데이터를 저장하는 자료구조
• 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조
• 한쪽 끝에서만 삽입이 이루어지고, 다른 한쪽 끝에서는 삭제 연산만 이루어지는 유한 순서 리스트
• 일상생활에서 줄을 서서 기다리는 것과 유사
• 대기열이나 작업 스케줄링 등에서 유용하게 사용
• 삽입 및 삭제에 O(1), 탐색에 O(n) 의 시간 복잡도를 가짐

큐(Queue)의 구현

• 큐는 대개 배열이나 연결 리스트를 이용해 구현
• 배열을 이용하는 경우, front와 rear라는 두 개의 인덱스 변수를 사용하여 큐의 시작과 끝을 가리킴 
  • 데이터를 삽입할 때에는 rear 변수를 증가시켜 새로운 데이터를 마지막에 추가
  • 데이터를 추출할 때에는 front 변수를 증가시켜 가장 처음에 있는 데이터를 추출
• 연결 리스트를 이용하는 경우에는, 각 노드가 다음 노드를 가리키는 포인터를 가지고 있으며, front와 rear는 각각 첫 번째 노드와 마지막 노드를 가리킴

 

큐(Queue)의 주요 동작들

• enQueue(): 큐에 데이터를 삽입
• deQueue(): 큐에서 데이터를 삭제
• isEmpty(): 큐가 비어있는지 확인
• isFull(): 큐가 꽉 차 있는지 확인
• peek(): 앞에 있는 원소를 삭제하지 않고 반환

큐(Queue)의 사용 사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 너비 우선 탐색(BFS, Breadth-First Search) 구현
  
  • 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장
  • 노드를 접근한 순서대로 처리할 수 있음
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리

데크(Deque)

• Double-ended Queue
• 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
• 큐를 일반화한 형태의 추상 자료형(ADT)