큐(Queue)

선입선출(First In First Out—FIFO)형 자료구조

 

https://commons.wikimedia.org/wiki/File:Data_Queue.svg

용어

• Enqueue: 큐 맨 뒤에 데이터를 추가
• Dequeue: 큐 맨 앞의 데이터를 제거
• Front: 맨 앞 데이터
• Rear: 맨 뒤 데이터

활용

• OS 작업 스케쥴링
• 인쇄작업 대기 등 순서대로 작업 처리 시

원형 큐

• 큐의 문제점: 고정된 크기의 배열에서 큐를 사용할 경우 Dequeue시 전체 배열을 앞으로 당겨야 하는 문제가 있음
• 원형 큐의 작동방식:
  1. rear과 front는 0 인덱스를 가지고 시작
  2. Enqueue시 rear의 포인터를 1증가 시키고 그 위치에 데이터 삽입
  3. Dequeue시 front의 포인터를 1증가 시키고 그 위치의 데이터 제거
  4. rear === front 일 때 빈 큐, Dequeue 불가
  5. (rear + 1) % (큐 용량) === front 일 때(rear의 다음 위치가 front일 때) 포화 상태, Enqueue 불가