[C] 원형큐 구조 정리

해당 글에서는 동작 구조를 중심으로 작성하였기 때문에 포화상태 및 공백 상태를 확인하는 코드는 작성하지 않았다는 점 참고 바랍니다.

기본 구조

(element는 저장할 데이터 타입입니다.)

typedef struct {
    int front;
    int rear;
    element data[SIZE];
} QueueType;

front: 현재 위치를 나타냅니다.

rear: 현재 저장되어 있는 아이템 갯수를 나타냅니다.

data: 아이템이 저장되는 위치를 나타냅니다.

원형큐는 초기 값으로 front, rear는 -1값으로 시작하며 선형큐의 재사용이 불가능한 문제를 해결하기 위해서 한번 추출되어 빈 공간을 재사용하여 데이터가 저장되는 구조가 됩니다.

데이터 추가

선형큐에서 SIZE의 나머지의 값을 이용하여 용량을 넘으면 앞쪽으로 다시 할당되도록 구조가 이루어져 있습니다.

void enqueue(QueueType *q, element item) {
    q->data[(q->rear = (q->rear + 1) % SIZE)] = item;
}

 

데이터 추출

추출은 선형큐와 동일하게 가장 마지막 데이터를 꺼내오는 것은 동일하지만 위치(front)가 SIZE를 넘기었을때 위치를 초기화해주도록 SIZE의 나머지를 저장되도록 구현되어 있습니다.

element dequeue(QueueType *q) {
    return q->data[(q->front = (q->front + 1) % SIZE)];
}

 

데이터 조회

데이터 상태는 건드리지 않고 다음에 추출할 데이터가 무엇인지 조회하는 코드입니다.

element peek(QueueType *q) {
    return q->data[(q->front + 1) % SIZE];
}