원형 큐

원형 큐란?

• 크기가 MAX_QUEUE_SIZE인 1차원 배열을 사용하면서 배열의 처음과 끝을 연결하여 논리적으로 원형 구조다.
• 오버플로우가 발생했을 때 큐의 구조가 원형으로 구성되어 있으므로 데이터의 삽입 시에 rear 포인터 값을 증가시켜 계속 새로운 가용공간을 확보할 수 있어서 원소들을 이동시킬 필요가 없게 된다.

원형 큐의 형태

원형 큐 특징

• 선형 큐의 단점인 front와 rear값의 계속되는 증가로 ‘배열의 끝’에 도달하는것을 방지하는 큐 형태다.
• 원형 큐에서는 front와 rear의 초기 값은 -1이 아닌 0이다.
  • 처음에는 front와 rear가 모두 0이다.
  • front는 첫 번째 요소 하나 앞의 인덱스를 저장한다.
  • rear는 마지막 요소의 인덱스를 저장한다.

front와 rear

원형큐의 구조

• 큐의 전단과 후단을 관리하기 위한 2개의 변수 필요하다.
• front: 첫번째 요소 하나 앞의 인덱스다.
• rear: 마지막 요소의 인덱스다.

원형 큐

원형큐의 공백상태, 포화상태

• 공백상태: front == rear / rear와 front의 값이 같다면 공백 상태다.
• 포화상태: front % M==(rear+1) % M (M = MAX_QUEUE_SIZE) / front의 위치를 큐 최대크기로 나눈 나머지가 rear값을 큐 최대크기로 나눈 나머지와 같다면 포화상태다.
• 공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둔다.
  •