Fixed-capacity circular queue

Challenge

Implement a fixed-capacity int queue:

typedef struct cq cq_t;
cq_t *cq_create(int capacity);
int   cq_enqueue(cq_t *q, int v);   /* 0 on success, -1 if full */
int   cq_dequeue(cq_t *q, int *out); /* 0 on success, -1 if empty */
int   cq_size(cq_t *q);
void  cq_destroy(cq_t *q);

Why this matters

Ring buffers are everywhere: kernel device drivers, audio playback, network interface cards. The 'one slot wasted' technique distinguishes full from empty.

Input format

capacity > 0.

Output format

See API.

Constraints

No realloc. The buffer is allocated once at create.

Starter code

typedef struct cq cq_t;
cq_t *cq_create(int capacity);
int   cq_enqueue(cq_t *q, int v);
int   cq_dequeue(cq_t *q, int *out);
int   cq_size(cq_t *q);
void  cq_destroy(cq_t *q);

Common mistakes

Using head == tail to mean both 'empty' and 'full' (ambiguous — use a count, or waste one slot); forgetting to advance with modulo (size_t wraparound only saves you in a few sizes); off-by-one on capacity vs. count.

Edge cases to handle

Dequeue from empty returns -1. Enqueue when full returns -1.

Complexity

O(1) per op.

Up next

• Min-heap priority queue