Fixed-capacity circular queue

Challenge

Build a fixed-capacity FIFO queue backed by a ring buffer.

Task

Implement the following int queue. The backing buffer is allocated once at creation and never resized; indices wrap around with modulo arithmetic.

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);

Input

• capacity: the maximum number of items (capacity > 0).
• v: the value to enqueue.
• out: where cq_dequeue writes the removed value.

Output

• cq_enqueue: 0 on success, -1 if the queue is full.
• cq_dequeue: 0 on success (writing the front value through out), -1 if empty.
• cq_size: the current number of items.

Example

cq_create(3)
cq_enqueue 1, 2, 3       (queue full)
cq_enqueue(4)   ->   -1  (full)
cq_dequeue(&v)  ->   0, v == 1
cq_enqueue(4)   ->   0   (reuses the freed slot, wrapping)
cq_dequeue(&v)  ->   0, v == 2   (FIFO order preserved)

Edge cases

• Dequeue from an empty queue returns -1.
• Enqueue into a full queue returns -1.
• Indices wrap from the end of the buffer back to the front.

Rules

• O(1) per operation. Do not realloc; the buffer is allocated once at create.

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; v to enqueue; out receives the dequeued value.

Output format

enqueue/dequeue return 0 on success or -1 (full/empty); dequeue writes through out; size returns the count.

Constraints

No realloc. The buffer is allocated once at create. O(1) per op.

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