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.

Practice

1. What does FIFO stand for in the context of a queue?

easy

A. First Input, First Operation

B. First In, Final Out

C. Fast Input, Fast Output

D. First In, First Out

Solution

1. Step 1: Understand FIFO meaning

   FIFO means the first element added to the queue is the first one to be removed.

2. Step 2: Match the acronym

   First In, First Out exactly describes this behavior.

3. Final Answer:

   First In, First Out -> Option D

4. Quick Check:

   FIFO = First In, First Out [OK]

Hint: Remember queue removes oldest item first [OK]

Common Mistakes:

• Confusing FIFO with LIFO
• Thinking FIFO means last added first removed
• Mixing up acronym letters

2. Which of the following is the correct syntax to enqueue an element `x` into a queue named `q` in C?

easy

A. push(q, x);

B. enqueue(q, x);

C. q.enqueue(x);

D. q.add(x);

Solution

1. Step 1: Identify common C queue operation

   In C, queue operations are usually functions like enqueue(queue, element).

2. Step 2: Check options for C style

   enqueue(q, x); uses function call syntax typical in C. Others use object-oriented syntax not common in C.

3. Final Answer:

   enqueue(q, x); -> Option B

4. Quick Check:

   C queue enqueue = enqueue(q, x); [OK]

Hint: C uses function calls, not dot notation [OK]

Common Mistakes:

• Using object-oriented syntax in C
• Confusing push with enqueue
• Using wrong function names

3. Consider the following C code snippet using a queue:

enqueue(q, 10);
enqueue(q, 20);
dequeue(q);
enqueue(q, 30);
dequeue(q);

What is the next element to be dequeued?

medium

A. 30

B. 10

C. 20

D. Queue is empty

Solution

1. Step 1: Trace enqueue and dequeue operations

   Queue after enqueue 10 and 20: [10, 20]. Dequeue removes 10, queue: [20]. Enqueue 30: [20, 30]. Dequeue removes 20, queue: [30].

2. Step 2: Identify next element to dequeue

   Next element is the front of queue, which is 30.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Queue front after operations = 30 [OK]

Hint: Follow FIFO order step-by-step [OK]

Common Mistakes:

• Assuming last enqueued is dequeued next
• Forgetting previous dequeues
• Mixing enqueue and dequeue order

4. Identify the error in the following C code snippet for queue operations:

enqueue(q, 5);
dequeue(q);
dequeue(q);

Assuming the queue was initially empty.

medium

A. Second dequeue causes underflow error

B. No error, code runs fine

C. First enqueue is incorrect syntax

D. Queue overflow error occurs

Solution

1. Step 1: Analyze queue state after operations

   Initially empty queue. Enqueue 5 adds one element. First dequeue removes it, queue empty again.

2. Step 2: Check second dequeue

   Second dequeue tries to remove from empty queue, causing underflow error.

3. Final Answer:

   Second dequeue causes underflow error -> Option A

4. Quick Check:

   Dequeue empty queue = underflow error [OK]

Hint: Check if queue is empty before dequeue [OK]

Common Mistakes:

• Ignoring empty queue before dequeue
• Confusing overflow with underflow
• Assuming enqueue syntax error

5. You have a queue that can hold a maximum of 3 elements. The following operations are performed:

enqueue(q, 1);
enqueue(q, 2);
enqueue(q, 3);
dequeue(q);
enqueue(q, 4);
dequeue(q);
dequeue(q);

What is the state of the queue after these operations?

hard

A. Queue is empty

B. 3 -> 4 -> null

C. 4 -> null

D. 2 -> 3 -> 4 -> null

Solution

1. Step 1: Track queue after each operation

   Enqueue 1,2,3: queue = [1,2,3]. Dequeue removes 1: queue = [2,3]. Enqueue 4: queue = [2,3,4]. Dequeue removes 2: queue = [3,4]. Dequeue removes 3: queue = [4].

2. Step 2: Final queue state

   Only element left is 4, so queue is 4 -> null.

3. Final Answer:

   4 -> null -> Option C

4. Quick Check:

   Final queue front = 4 [OK]

Hint: Follow enqueue and dequeue stepwise, watch max size [OK]

Common Mistakes:

• Forgetting max size limit
• Miscounting dequeues
• Assuming queue empty incorrectly