Queue Concept and FIFO Principle in DSA C#

Mental Model

A queue is a line where the first person to get in is the first to get out. It works on the First In, First Out (FIFO) rule.

Analogy: Imagine waiting in line at a ticket counter. The first person who joins the line is the first one served and leaves the line first.

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

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 into empty queue

front -> [1] -> null ← rear
↑front and rear point to 1

Why: First element sets both front and rear pointers

Step 2: enqueue 2 at rear

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

Why: New element added at rear, rear pointer moves to new element

Step 3: enqueue 3 at rear

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

Why: Add another element at rear, rear pointer updates

Step 4: dequeue element from front

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

Why: Remove element from front, front pointer moves to next element

Result:

front -> [2] -> [3] -> null ← rear
Queue after dequeue: 2 -> 3 -> null

Annotated Code

DSA C#

using System;

public class QueueNode
{
    public int Value;
    public QueueNode Next;
    public QueueNode(int value) { Value = value; Next = null; }
}

public class Queue
{
    private QueueNode front;
    private QueueNode rear;

    public Queue() { front = null; rear = null; }

    public void Enqueue(int value)
    {
        QueueNode newNode = new QueueNode(value);
        if (rear == null) // queue empty
        {
            front = newNode;
            rear = newNode;
            return;
        }
        rear.Next = newNode; // link new node at rear
        rear = newNode; // move rear pointer
    }

    public int Dequeue()
    {
        if (front == null) throw new InvalidOperationException("Queue is empty");
        int val = front.Value;
        front = front.Next; // move front pointer
        if (front == null) rear = null; // queue empty after dequeue
        return val;
    }

    public override string ToString()
    {
        QueueNode current = front;
        string result = "";
        while (current != null)
        {
            result += current.Value + " -> ";
            current = current.Next;
        }
        result += "null";
        return result;
    }
}

public class Program
{
    public static void Main()
    {
        Queue q = new Queue();
        q.Enqueue(1);
        q.Enqueue(2);
        q.Enqueue(3);
        Console.WriteLine("Queue before dequeue: " + q);
        int removed = q.Dequeue();
        Console.WriteLine("Dequeued element: " + removed);
        Console.WriteLine("Queue after dequeue: " + q);
    }
}

if (rear == null) // queue empty

check if queue is empty to set front and rear to new node

rear.Next = newNode; // link new node at rear

attach new node at the end of queue

rear = newNode; // move rear pointer

update rear pointer to new last node

if (front == null) rear = null; // queue empty after dequeue

if queue becomes empty after removing front, reset rear pointer

front = front.Next; // move front pointer

remove front element by moving front pointer forward

Output

Queue before dequeue: 1 -> 2 -> 3 -> null

Dequeued element: 1

Queue after dequeue: 2 -> 3 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we only update pointers without traversing the queue

Space: O(n) because we store n elements in the queue nodes

vs Alternative: Compared to using arrays where dequeue can be O(n) due to shifting elements, linked queue operations are faster and constant time

Edge Cases

dequeue from empty queue

throws InvalidOperationException to prevent invalid removal

DSA C#

if (front == null) throw new InvalidOperationException("Queue is empty");

enqueue first element into empty queue

front and rear both point to the new node

DSA C#

if (rear == null) { front = newNode; rear = newNode; return; }

dequeue last element leaving queue empty

rear pointer is set to null to mark empty queue

DSA C#

if (front == null) rear = null;

When to Use This Pattern

When you see a problem requiring processing items in the order they arrive, use the queue pattern because it naturally follows the FIFO principle.

Common Mistakes

Mistake: Not updating rear pointer after enqueue, causing new elements to be lost
Fix: Always move rear pointer to the newly added node after enqueue

Mistake: Not handling empty queue case in dequeue, causing null reference errors
Fix: Check if front is null before dequeue and throw exception or handle gracefully

Summary

A queue stores items so the first added is the first removed, following FIFO.

Use a queue when order of processing matters, like task scheduling or buffering.

Remember to add at rear and remove from front to keep the FIFO order.

Practice

1. What does the FIFO principle mean in the context of a Queue data structure?

easy

A. Last In, Last Out - the last element added is the last removed

B. First In, First Out - the first element added is the first removed

C. Last In, First Out - the last element added is the first removed

D. First In, Last Out - the first element added is the last removed

Solution

1. Step 1: Understand FIFO meaning

   FIFO stands for First In, First Out, meaning the first element added to the queue is the first one to be removed.

2. Step 2: Apply FIFO to Queue

   In a queue, elements are processed in the order they arrive, so the earliest added element leaves first.

3. Final Answer:

   First In, First Out - the first element added is the first removed -> Option B

4. Quick Check:

   FIFO = First In, First Out [OK]

Hint: Remember queue = line; first come, first served [OK]

Common Mistakes:

• Confusing FIFO with stack behavior (LIFO)
• Thinking last added element is removed first
• Mixing up terms In and Out order

2. Which of the following is the correct way to add an element to a Queue<int> named q in C#?

easy

A. q.Insert(5);

B. q.Push(5);

C. q.Add(5);

D. q.Enqueue(5);

Solution

1. Step 1: Recall Queue method to add elements

   The method to add elements to a Queue in C# is Enqueue.

2. Step 2: Check each option

   Only q.Enqueue(5); is valid syntax to add 5 to the queue.

3. Final Answer:

   q.Enqueue(5); -> Option D

4. Quick Check:

   Use Enqueue to add in Queue [OK]

Hint: Use Enqueue to add, Dequeue to remove [OK]

Common Mistakes:

• Using Push which is for stacks
• Using Add or Insert which are not Queue methods
• Confusing method names with List

3. What will be the output of the following C# code?

Queue<string> q = new Queue<string>();
q.Enqueue("apple");
q.Enqueue("banana");
q.Enqueue("cherry");
string first = q.Dequeue();
q.Enqueue("date");
Console.WriteLine(string.Join(", ", q));

medium

A. "banana, cherry, date"

B. "apple, banana, cherry, date"

C. "date, apple, banana, cherry"

D. "cherry, date, banana"

Solution

1. Step 1: Trace Enqueue and Dequeue operations

   Initially queue: [apple, banana, cherry]. Dequeue removes "apple" (first in). Queue now: [banana, cherry]. Then Enqueue "date" adds it to the end: [banana, cherry, date].

2. Step 2: Output the queue contents

   Printing queue elements joined by comma results in "banana, cherry, date".

3. Final Answer:

   "banana, cherry, date" -> Option A

4. Quick Check:

   Dequeue removes first, Enqueue adds last [OK]

Hint: Dequeue removes front, Enqueue adds back [OK]

Common Mistakes:

• Forgetting Dequeue removes first element
• Assuming Enqueue adds to front
• Printing queue before Dequeue

4. Identify the error in the following C# code that uses a Queue<int>:

Queue<int> q = new Queue<int>();
q.Enqueue(10);
q.Enqueue(20);
int x = q.Pop();
Console.WriteLine(x);

medium

A. Pop() method does not exist for Queue

B. Enqueue should be Add

C. Queue cannot store integers

D. Missing using System.Collections.Generic;

Solution

1. Step 1: Check Queue methods

   Queue in C# does not have a Pop() method; it uses Dequeue() to remove elements.

2. Step 2: Validate other parts

   Enqueue is correct to add elements; Queue can store integers; using System.Collections.Generic; is needed but not an error here.

3. Final Answer:

   Pop() method does not exist for Queue -> Option A

4. Quick Check:

   Use Dequeue, not Pop, for Queue removal [OK]

Hint: Queue uses Dequeue, not Pop [OK]

Common Mistakes:

• Using Pop() from stack on queue
• Confusing Enqueue with Add
• Ignoring missing namespace errors

5. You have a queue of customer names: ["Anna", "Bob", "Cara"]. You want to process the first two customers and then add "Dave" and "Eva" to the queue. What will be the final queue order after these operations?

hard

A. ["Anna", "Bob", "Dave", "Eva"]

B. ["Dave", "Eva", "Cara"]

C. ["Cara", "Dave", "Eva"]

D. ["Bob", "Cara", "Dave", "Eva"]

Solution

1. Step 1: Remove first two customers using Dequeue

   Removing "Anna" and "Bob" leaves the queue with ["Cara"].

2. Step 2: Add "Dave" and "Eva" using Enqueue

   Adding "Dave" and "Eva" to the end results in ["Cara", "Dave", "Eva"].

3. Final Answer:

   ["Cara", "Dave", "Eva"] -> Option C

4. Quick Check:

   Dequeue twice, then Enqueue twice [OK]

Hint: Dequeue removes front, Enqueue adds back [OK]

Common Mistakes:

• Not removing both customers before adding
• Adding new customers to front instead of back
• Confusing order of elements after operations