Queue Implementation Using Array in DSA C

Mental Model

A queue is like a line where the first person in is the first person out. We use an array to hold the line and two markers to track the front and back.

Analogy: Imagine a queue at a ticket counter. People join at the end and leave from the front. The array is the waiting area, front is the person served next, rear is the last person who joined.

front -> [ ] [ ] [ ] [ ] [ ] ← rear
indexes  0   1   2   3   4
Initially: front = -1, rear = -1, array empty

Dry Run Walkthrough

Input: Queue with size 5, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements enter and leave the queue using array indexes front and rear

Step 1: enqueue 10: move rear forward and add 10

front = 0, rear = 0
10 -> null

Why: First element added, front and rear both point to index 0

Step 2: enqueue 20: move rear forward and add 20

front = 0, rear = 1
10 -> 20 -> null

Why: Add element at next position, rear moves to index 1

Step 3: dequeue: remove element at front and move front forward

front = 1, rear = 1
20 -> null

Why: Remove first element (10), front moves to index 1

Step 4: enqueue 30: move rear forward and add 30

front = 1, rear = 2
20 -> 30 -> null

Why: Add new element at index 2, rear moves forward

Result:

front = 1, rear = 2
20 -> 30 -> null

Annotated Code

DSA C

#include <stdio.h>
#define SIZE 5

typedef struct {
    int arr[SIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(Queue* q) {
    return q->rear == SIZE - 1;
}

int isEmpty(Queue* q) {
    return q->front == -1 || q->front > q->rear;
}

void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0; // set front to first element
    }
    q->rear++;
    q->arr[q->rear] = value; // add value at rear
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int value = q->arr[q->front];
    q->front++; // move front forward
    return value;
}

void printQueue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d", q->arr[i]);
        if (i < q->rear) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    printQueue(&q);

    dequeue(&q);
    printQueue(&q);

    enqueue(&q, 30);
    printQueue(&q);

    return 0;
}

if (q->front == -1) { q->front = 0; }

initialize front when first element is enqueued

q->rear++; q->arr[q->rear] = value;

advance rear and insert new element

if (isEmpty(q)) { return -1; }

check if queue is empty before dequeue

int value = q->arr[q->front]; q->front++;

remove element at front and move front forward

for (int i = q->front; i <= q->rear; i++) { print elements }

print all elements from front to rear

Output

10 -> 20 -> null

20 -> null

20 -> 30 -> null

Complexity Analysis

Time: O(1) for enqueue and dequeue because we only move front or rear pointers once per operation

Space: O(n) because we use a fixed size array of size n to store elements

vs Alternative: Compared to linked list queue, array queue is simpler but fixed size; linked list can grow dynamically but uses extra memory for pointers

Edge Cases

enqueue when queue is full

prints 'Queue is full' and does not add element

DSA C

if (isFull(q)) { printf("Queue is full\n"); return; }

dequeue when queue is empty

prints 'Queue is empty' and returns -1

DSA C

if (isEmpty(q)) { printf("Queue is empty\n"); return -1; }

dequeue last element makes queue empty

front moves beyond rear, isEmpty returns true

DSA C

return q->front == -1 || q->front > q->rear;

When to Use This Pattern

When you need a first-in-first-out order with fixed size and fast access, use array queue pattern because it uses two pointers to track front and rear efficiently.

Common Mistakes

Mistake: Not initializing front to 0 on first enqueue, causing incorrect empty checks
Fix: Set front to 0 when first element is enqueued (front == -1 case)

Mistake: Not checking if queue is full before enqueue, causing overflow
Fix: Add isFull check before adding new element

Mistake: Not updating front after dequeue, causing stale front pointer
Fix: Increment front after removing element

Summary

Implements a queue using a fixed size array with front and rear pointers.

Use when you want a simple queue with known maximum size and fast enqueue/dequeue.

Remember to move front and rear pointers correctly and handle empty/full states.