C언어 원형 큐(circular queues in C)

• 나중에 들어온 데이터가 먼저 나가는 스택 자료구조와 달리 큐는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다.
  선입선출(FIFO: First-In First-Out) 큐를 사용하는 방식에는 선형 큐, 원형 큐, 덱이 있습니다.

선형 큐

배열을 선형으로 사용하여 구현된 큐이며, 삽입을 계속하기 위해서는 요소들을 이동시켜야 합니다.

데이터를 넣을때마다 번거로움이 있다는 문제점이 있는 방식입니다.

또한 인덱스를 감소하지는 않고 증가만 하면서 사용하는 방식이기에, 실제로 앞부분에는 데이터가 없을 때에도 비어있는 공간을 활용할 수 없기 때문에 비효율적인 부분이 있습니다.

원형 큐

선형 큐의 대안으로 나온 것이 원형 큐입니다. 큐의 전단과 후단을 관리하기 위한 2개의 변수가 필요합니다.

• front 첫번째 요소 바로 앞의 인덱스

• rear 마지막 요소의 인덱스

공백상태는 front == rear 인 상태이며 포화상태는 front == (rear+1) % MAX_QUEUE_SIZE 의 값으로 판단합니다.

위 그림에서 큐의 맥스 크기는 8입니다. 만약 front가 2에 있을 때 포화상태라면 rear가 1에 있어야 하겠죠. 그 값을 우변에서 계산하면 (1+1) % 8 = 2가 되므로 front와 rear값이 같아 포화상태인 것을 알립니다. 공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둡니다.

📌while(1) 무한 루프로 계속해서 원형 큐 실행시키는 코드