Dequeue Operation in DSA C#

Mental Model

A dequeue operation removes an item from the front of a queue, like taking the first person out of a line.

Analogy: Imagine a line of people waiting to buy tickets. The person at the front leaves the line first when served. Dequeue is like that: removing the front person.

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

Dry Run Walkthrough

Input: queue: 1 -> 2 -> 3, perform dequeue

Goal: Remove the front element (1) from the queue and update the front pointer

Step 1: Check if queue is empty

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

Why: We must ensure there is something to remove

Step 2: Remove front node (1) and move front pointer to next node

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

Why: Removing the first element means front now points to the second

Step 3: Return removed value 1

front -> 2 -> 3 -> null

Why: We return the value that was dequeued

Result:

front -> 2 -> 3 -> null
Dequeued value: 1

Annotated Code

DSA C#

using System;

public class Node
{
    public int Data;
    public Node Next;
    public Node(int data) { Data = data; Next = null; }
}

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

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

    public void Enqueue(int data)
    {
        Node newNode = new Node(data);
        if (rear == null)
        {
            front = rear = newNode;
            return;
        }
        rear.Next = newNode;
        rear = newNode;
    }

    public int Dequeue()
    {
        if (front == null) throw new InvalidOperationException("Queue is empty");
        int value = front.Data; // store front value
        front = front.Next; // move front to next node
        if (front == null) rear = null; // if queue became empty, update rear
        return value;
    }

    public void PrintQueue()
    {
        Node current = front;
        while (current != null)
        {
            Console.Write(current.Data);
            if (current.Next != null) Console.Write(" -> ");
            current = current.Next;
        }
        Console.WriteLine(" -> null");
    }
}

public class Program
{
    public static void Main()
    {
        Queue q = new Queue();
        q.Enqueue(1);
        q.Enqueue(2);
        q.Enqueue(3);
        q.PrintQueue();
        int removed = q.Dequeue();
        q.PrintQueue();
        Console.WriteLine($"Dequeued value: {removed}");
    }
}

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

check if queue is empty before dequeue

int value = front.Data; // store front value

save the value at front to return later

front = front.Next; // move front to next node

advance front pointer to next node to remove current front

if (front == null) rear = null; // if queue became empty, update rear

if queue is empty after removal, reset rear pointer

return value;

return the dequeued value

Output

1 -> 2 -> 3 -> null

2 -> 3 -> null

Dequeued value: 1

Complexity Analysis

Time: O(1) because dequeue removes the front element directly without traversal

Space: O(1) because no extra space is needed for dequeue operation

vs Alternative: Compared to array-based queue where dequeue may require shifting elements O(n), linked list dequeue is faster O(1)

Edge Cases

empty queue

throws InvalidOperationException to indicate no elements to dequeue

DSA C#

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

queue with one element

after dequeue, both front and rear become null indicating empty queue

DSA C#

if (front == null) rear = null;

When to Use This Pattern

When you see a problem asking to remove the first element from a line or list efficiently, reach for the dequeue operation because it removes from front in constant time.

Common Mistakes

Mistake: Not updating rear pointer when the last element is dequeued, causing rear to point to a removed node
Fix: After moving front, check if front is null and set rear to null to keep queue consistent

Mistake: Trying to dequeue from an empty queue without checking, causing runtime errors
Fix: Always check if front is null before dequeue and handle empty queue case

Summary

Removes the front element from a queue and returns its value.

Use when you need to process elements in the order they arrived, removing from the front.

The key insight is that dequeue moves the front pointer forward, removing the first element in constant time.

Practice

1. What does the Dequeue operation do in a queue data structure?

easy

A. Returns the number of elements in the queue

B. Adds an element to the end of the queue

C. Checks if the queue is empty

D. Removes and returns the element at the front of the queue

Solution

1. Step 1: Understand the queue structure

   A queue works like a line where the first person in line is served first (FIFO).

2. Step 2: Define the Dequeue operation

   Dequeue removes and returns the first element in the queue, following FIFO.

3. Final Answer:

   Removes and returns the element at the front of the queue -> Option D

4. Quick Check:

   Dequeue = Remove front element [OK]

Hint: Dequeue always removes from the front [OK]

Common Mistakes:

• Confusing Dequeue with Enqueue (adding element)
• Thinking Dequeue checks queue size
• Assuming Dequeue removes from the end

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

easy

A. q.Remove()

B. q.Pop()

C. q.Dequeue()

D. q.Delete()

Solution

1. Step 1: Recall C# Queue methods

   The method to remove and return the front element in C# Queue is Dequeue().

2. Step 2: Check each option

   Only q.Dequeue() matches the correct method name and syntax.

3. Final Answer:

   q.Dequeue() -> Option C

4. Quick Check:

   Queue removal method = Dequeue() [OK]

Hint: Use Dequeue() to remove front element in C# Queue [OK]

Common Mistakes:

• Using Remove() which does not exist for Queue
• Using Pop() which is for stacks
• Using Delete() which is invalid

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();
Console.WriteLine(first);
Console.WriteLine(q.Peek());

medium

A. apple\nbanana

B. banana\ncherry

C. apple\ncherry

D. cherry\napple

Solution

1. Step 1: Trace Enqueue operations

   Queue after enqueues: front -> apple, banana, cherry -> rear.

2. Step 2: Dequeue removes 'apple'

   Dequeue returns 'apple' and removes it from queue.

3. Step 3: Peek returns new front 'banana'

   After dequeue, front is 'banana', so Peek returns 'banana'.

4. Final Answer:

   apple banana -> Option A

5. Quick Check:

   Dequeue = apple, Peek = banana [OK]

Hint: Dequeue returns front; Peek shows new front [OK]

Common Mistakes:

• Confusing Peek with Dequeue
• Assuming Dequeue removes from rear
• Mixing order of elements

4. Identify the error in the following C# code that uses a queue:

Queue<int> q = new Queue<int>();
q.Enqueue(10);
q.Enqueue(20);
int x = q.Dequeue();
int y = q.Dequeue();
int z = q.Dequeue(); // Error here
Console.WriteLine(z);

medium

A. Queue does not support Dequeue method

B. Dequeue called on empty queue causes InvalidOperationException

C. Enqueue method is used incorrectly

D. Console.WriteLine cannot print integers

Solution

1. Step 1: Count elements and Dequeue calls

   Queue has 2 elements; 3 Dequeue calls are made.

2. Step 2: Third Dequeue on empty queue causes error

   Calling Dequeue on empty queue throws InvalidOperationException.

3. Final Answer:

   Dequeue called on empty queue causes InvalidOperationException -> Option B

4. Quick Check:

   Empty queue Dequeue = Exception [OK]

Hint: Dequeue on empty queue throws exception [OK]

Common Mistakes:

• Assuming Dequeue returns default value on empty
• Thinking Enqueue is incorrect
• Believing Console.WriteLine can't print int

5. You have a queue with elements [5, 10, 15, 20] (front to rear). You perform these operations:
1. Dequeue
2. Enqueue(25)
3. Dequeue
4. Enqueue(30)
What is the final state of the queue (front to rear)?

hard

A. [15, 20, 25, 30]

B. [10, 15, 20, 25]

C. [20, 25, 30]

D. [5, 10, 15, 20, 25, 30]

Solution

1. Step 1: Initial queue and first Dequeue

   Queue: 5(front),10,15,20(rear). Dequeue removes 5. Queue now: 10,15,20.

2. Step 2: Enqueue 25

   Add 25 at rear. Queue: 10,15,20,25.

3. Step 3: Second Dequeue

   Remove front 10. Queue: 15,20,25.

4. Step 4: Enqueue 30

   Add 30 at rear. Queue: 15,20,25,30.

5. Final Answer:

   [15, 20, 25, 30] -> Option A

6. Quick Check:

   After ops queue front to rear = [15,20,25,30] [OK]

Hint: Track front and rear after each operation [OK]

Common Mistakes:

• Forgetting to remove elements on Dequeue
• Adding new elements at front instead of rear
• Mixing order of elements after operations