C Queue: Enqueue, Dequeue, Circular Array

A queue is FIFO — first in, first out. Enqueue adds to the rear; dequeue removes from the front. The circular array trick lets fixed-size queues reuse slots cleanly.

Stacks (last episode) are LIFO. Queues are FIFO. Used wherever order matters: print spoolers, message queues, BFS, request handling.

The basic shape

#include <stdio.h>

#define MAX 5

typedef struct {
  int items[MAX];
  int front;
  int rear;
  int count;
} Queue;

void init(Queue *q) {
  q->front = 0;
  q->rear = -1;
  q->count = 0;
}

int is_empty(Queue *q) { return q->count == 0; }
int is_full(Queue *q) { return q->count == MAX; }

void enqueue(Queue *q, int value) {
  if (is_full(q)) return;
  q->rear = (q->rear + 1) % MAX;
  q->items[q->rear] = value;
  q->count++;
}

int dequeue(Queue *q) {
  if (is_empty(q)) return -1;
  int value = q->items[q->front];
  q->front = (q->front + 1) % MAX;
  q->count--;
  return value;
}

The circular array trick

q->rear = (q->rear + 1) % MAX;
q->front = (q->front + 1) % MAX;

The % MAX wraps the index back to 0 when it reaches MAX. Visualised:

Slots:    [0] [1] [2] [3] [4]
            ^               ^
            front           rear

After enqueueing 5 items and dequeueing 2, the layout might be:

Slots:    [empty] [empty] [3] [4] [5]
            ^              ^
            front (was 0)  rear
            now 2

Without the modulo trick, dequeueing leaves dead slots at the front while rear hits the array end. Wrap with modulo to reuse them.

Why three trackers (front, rear, count)?

Two would suffice in theory:

• Empty: front == rear.
• Full: (rear + 1) % MAX == front.

But this loses one slot — there's no way to distinguish "full" from "empty" using just front and rear. To save the slot, track count separately.

Some implementations omit count and reserve one slot. Either works.

init

void init(Queue *q) {
  q->front = 0;
  q->rear = -1;
  q->count = 0;
}

rear = -1 because the first enqueue does rear = (rear + 1) % MAX = 0 — landing at index 0.

enqueue

void enqueue(Queue *q, int value) {
  if (is_full(q)) return;
  q->rear = (q->rear + 1) % MAX;
  q->items[q->rear] = value;
  q->count++;
}

Increment rear (wrapping), write the value, bump count. O(1).

dequeue

int dequeue(Queue *q) {
  if (is_empty(q)) return -1;
  int value = q->items[q->front];
  q->front = (q->front + 1) % MAX;
  q->count--;
  return value;
}

Read front, increment front (wrapping), decrement count. O(1).

peek

int peek(Queue *q) {
  if (is_empty(q)) return -1;
  return q->items[q->front];
}

Look at the front without removing. Standard "examine before consuming" pattern.

Iterating the queue contents

void print_queue(Queue *q) {
  printf("Queue: ");
  for (int i = 0; i < q->count; i++) {
    int idx = (q->front + i) % MAX;
    printf("%d ", q->items[idx]);
  }
  printf("\n");
}

(front + i) % MAX walks from front to rear, wrapping. Prints items in their FIFO order.

Linked-list queue

For dynamic size:

typedef struct QNode {
  int data;
  struct QNode *next;
} QNode;

typedef struct {
  QNode *front;
  QNode *rear;
  int count;
} Queue;

void enqueue(Queue *q, int value) {
  QNode *n = malloc(sizeof(QNode));
  n->data = value;
  n->next = NULL;
  if (q->rear == NULL) {
    q->front = q->rear = n;
  } else {
    q->rear->next = n;
    q->rear = n;
  }
  q->count++;
}

int dequeue(Queue *q) {
  if (q->front == NULL) return -1;
  QNode *n = q->front;
  int value = n->data;
  q->front = n->next;
  if (q->front == NULL) q->rear = NULL;
  free(n);
  q->count--;
  return value;
}

Front and rear pointers; enqueue at rear, dequeue from front. No size limit. Cost: malloc/free per item.

Dynamic-size circular array

To resize when full:

void enqueue(Queue *q, int value) {
  if (q->count == q->capacity) {
    int new_cap = q->capacity * 2;
    int *new_items = malloc(new_cap * sizeof(int));
    for (int i = 0; i < q->count; i++) {
      new_items[i] = q->items[(q->front + i) % q->capacity];
    }
    free(q->items);
    q->items = new_items;
    q->front = 0;
    q->rear = q->count - 1;
    q->capacity = new_cap;
  }
  q->rear = (q->rear + 1) % q->capacity;
  q->items[q->rear] = value;
  q->count++;
}

When full, allocate double, copy in FIFO order, update front/rear. Amortized O(1).

Use cases

• Breadth-first search. Visit neighbors in order.
• Print queues. Documents print in submission order.
• Network packet buffers. Process in arrival order.
• Producer-consumer. One thread enqueues, another dequeues.
• Event loops. Process events in order received.

For multi-threaded use, you'd add locking — see pthread_mutex_t or use lock-free queues.

Priority queue: a different beast

A priority queue dequeues the highest-priority element, not the oldest. Implemented with a heap (binary tree where parent ≥ children for max-heap).

// Insert
void enqueue(PQ *pq, int value) { ... bubble up ... }

// Remove max
int dequeue(PQ *pq) { ... swap and bubble down ... }

Standard implementation: array storing the heap, with parent at i/2 and children at 2i, 2i+1. O(log n) ops.

Different from a regular FIFO queue.

Common mistakes

Forgetting % MAX. Index walks off the array end.

Using only front and rear. Can't distinguish full from empty without count or reserving a slot.

Confusing rear's pre/post-increment with front's. Rear is "where the next item will go" or "where the last item is." Pick a convention; document it.

Leaks in linked-list version. Forgetting to free the dequeued node.

Mixing FIFO and LIFO behavior. Queue should never let you push to the front. If your code pushes both ends, that's a deque (double-ended queue).

What's next

Episode 48: hash tables — concept, hash function, collisions. Maps with average O(1) lookup.

Recap

Queue = FIFO. Three trackers: front, rear, count. Circular array uses % MAX to wrap indices, reusing slots cleanly. enqueue puts at rear; dequeue reads at front; both O(1). For dynamic size, linked list (one malloc per item) or growing array. Use cases: BFS, print spoolers, packet buffers, event loops. Priority queues are a different structure (heap-based).

Next episode: hash tables — concept.