Queue Concept and FIFO Principle in DSA C

Mental Model

A queue is a line where the first person in is the first person out. It works like waiting in line for a bus.

Analogy: Imagine a line at a ticket counter. The first person who gets in line is the first to get the ticket and leave the line. New people join at the end of the line.

front -> [1] -> [2] -> [3] -> rear
null

Dry Run Walkthrough

Input: Start with an empty queue, enqueue 1, enqueue 2, enqueue 3, then dequeue one element

Goal: Show how elements enter at the rear and leave from the front following FIFO

Step 1: enqueue 1 at rear

front -> [1] -> rear
null

Why: First element added becomes both front and rear

Step 2: enqueue 2 at rear

front -> [1] -> [2] -> rear
null

Why: New element added at rear, after existing elements

Step 3: enqueue 3 at rear

front -> [1] -> [2] -> [3] -> rear
null

Why: Keep adding elements at rear to maintain order

Step 4: dequeue element from front

front -> [2] -> [3] -> rear
null

Why: Remove element from front to follow FIFO

Result:

front -> [2] -> [3] -> rear
null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX 5

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

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

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

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

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front++;
    }
    return item;
}

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

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

    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printQueue(&q);

    int removed = dequeue(&q);
    printf("Dequeued: %d\n", removed);
    printQueue(&q);

    return 0;
}

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

set front to 0 when first element is enqueued

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

add new element at rear and move rear pointer

int item = q->items[q->front];

store front element to return it

if (q->front == q->rear) { q->front = -1; q->rear = -1; } else { q->front++; }

move front pointer forward or reset if queue becomes empty

Output

front -> [1] -> [2] -> [3] -> rear

Dequeued: 1

front -> [2] -> [3] -> rear

Complexity Analysis

Time: O(1) because enqueue and dequeue only move pointers without loops

Space: O(n) where n is the max size of the queue, fixed by array size

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

Edge Cases

empty queue dequeue

prints 'Queue is empty' and returns -1

DSA C

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

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 last element

resets front and rear to -1 to mark empty queue

DSA C

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

When to Use This Pattern

When you see a problem requiring first-in-first-out order, think of the queue pattern because it models waiting lines perfectly.

Common Mistakes

Mistake: Not resetting front and rear when queue becomes empty after dequeue
Fix: Reset front and rear to -1 when last element is removed to mark empty queue

Mistake: Adding new elements at front instead of rear
Fix: Always add new elements at rear to maintain FIFO order

Summary

A queue stores items so the first added is the first removed (FIFO).

Use a queue when order matters and you want to process items in the order they arrive.

The key is to add at the rear and remove from the front to keep the order correct.