[C] Circular Queue 구현

동작 방식

초기 상태

큐 size : 3
head == tail -> empty

head
 |
[ ] [ ] [ ] [ ]
 |
tail

enqueue 10, enqueue 20 을 수행한 이후 모습.

enqueue 할때 index를 늘리고 값을 저장하기 때문에 배열[0]은 비어있음.

head
 |
[ ] [10] [20] []
          |
         tail

enqueue 30 한 이후 (full)

(tail + 1) % size == head -> 가득 참.

head
 |
[ ] [10] [20] [30]
               |
              tail

dequeue 한 이후

    head
     |
[ ] [ ] [20] [30]
              |
             tail

enqueue 40 한 이후 (full)

(tail + 1) % size == head -> 가득 참.

     head
      |
[40] [ ] [20] [30]
 |
tail

initialize queue

struct queue {
    int *arr;
    int head, tail, size;
    void (*enq)(struct queue *, int);
    int (*deq)(struct queue *);
};

원하는 사이즈의 +1 만큼 배열사이즈를 잡는다.

struct queue *queue_init(int size)
{
    struct queue *q = (struct queue *)malloc(sizeof(struct queue));
    q->size = size + 1; // <-
    q->arr = (int *)calloc(q->size, sizeof(int));
    q->head = 0;
    q->tail = 0;
    q->enq = enqueue;
    q->deq = dequeue;
    return q;
}

check full and empty

큐가 비어 있다면 tail == head
큐가 가득 찼다면 tail + 1 == head
단 tail과 head값을 증가시킬때, % size 연산을 통해 인덱스 값이 size를 초과하지 못하게 한다.

bool is_empty(struct queue *q)
{
    return (q->tail == q->head);
}

bool is_full(struct queue *q)
{
    return ((q->tail + 1) % q->size == q->head);
}

enqueue

tail 을 먼저 증가시키고 값을 삽입한다.

void enqueue(struct queue *q, int val)
{
    if (is_full(q)) {
        fprintf(stdout, "queue is full\n");
        return;
    }
    q->tail = (q->tail + 1) % q->size; /* increase idx before insert */
    q->arr[q->tail] = val;
}

dequeue

head를 먼저 증가시키고, 그 index에서 값을 얻는다.

int dequeue(struct queue *q)
{
    if (is_empty(q)) {
        fprintf(stdout, "queue is empty\n");
        return -1;
    }
    q->head = (q->head + 1) % q->size; /* increase idx before pop */
    return q->arr[q->head];
}

test cases

void test_queue(void)
{
    struct queue *q = queue_init(3); /* queue size 3 */
    q->enq(q, 10);
    assert(q->arr[1] == 10);
    q->enq(q, 20);
    assert(q->arr[2] == 20);
    q->enq(q, 30); 
    assert(q->arr[3] == 30);
    q->enq(q, 40);  /* tried to full q */
    assert(q->arr[0] == 0);
    
    assert(q->deq(q) == 10);
    q->enq(q, 40);  
    assert(q->arr[0] == 40);
    assert(q->deq(q) == 20);
    q->enq(q, 50);  
    assert(q->arr[1] == 50);
    for (int i = 0; i < q->size; i++)
        printf("(%d)", q->arr[i]);
    
    assert(is_full(q) == true);
    assert(q->deq(q) == 30);
    assert(q->deq(q) == 40);
    assert(q->deq(q) == 50);
    assert(is_empty(q) == true);
    
}

int main()
{
    test_queue();
    return 0;
}