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 items and keep track of where the line starts and ends.

Analogy: Imagine a line of people waiting to buy tickets. The first person to get in line is the first to be served and leave. The array holds the people, and two markers show who is first and last in line.

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

Dry Run Walkthrough

Input: Create queue with size 5, enqueue 10, enqueue 20, enqueue 30, dequeue once, enqueue 40

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

Step 1: enqueue 10: move rear to 0 and place 10

front=0, rear=0, array: [10] [ ] [ ] [ ] [ ]

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

Step 2: enqueue 20: move rear to 1 and place 20

front=0, rear=1, array: [10] [20] [ ] [ ] [ ]

Why: Add next element at next rear position

Step 3: enqueue 30: move rear to 2 and place 30

front=0, rear=2, array: [10] [20] [30] [ ] [ ]

Why: Add next element at next rear position

Step 4: dequeue: remove element at front (index 0), move front to 1

front=1, rear=2, array: [ ] [20] [30] [ ] [ ]

Why: Remove first element and move front forward

Step 5: enqueue 40: move rear to 3 and place 40

front=1, rear=3, array: [ ] [20] [30] [40] [ ]

Why: Add new element at next rear position

Result:

front=1, rear=3, array: [ ] [20] [30] [40] [ ]
Queue elements in order: 20 -> 30 -> 40 -> null

Annotated Code

DSA C#

using System;

class QueueUsingArray
{
    private int[] arr;
    private int front;
    private int rear;
    private int size;

    public QueueUsingArray(int capacity)
    {
        arr = new int[capacity];
        front = -1;
        rear = -1;
        size = capacity;
    }

    public bool IsEmpty()
    {
        return front == -1;
    }

    public bool IsFull()
    {
        return rear == size - 1;
    }

    public void Enqueue(int value)
    {
        if (IsFull())
        {
            Console.WriteLine("Queue is full. Cannot enqueue " + value);
            return;
        }
        if (IsEmpty())
        {
            front = 0; // first element added
        }
        rear++;
        arr[rear] = value; // place value at rear
    }

    public int Dequeue()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is empty. Cannot dequeue.");
            return -1;
        }
        int result = arr[front]; // get front element
        if (front == rear)
        {
            front = -1; // queue becomes empty
            rear = -1;
        }
        else
        {
            front++; // move front forward
        }
        return result;
    }

    public void PrintQueue()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is empty.");
            return;
        }
        for (int i = front; i <= rear; i++)
        {
            Console.Write(arr[i]);
            if (i < rear)
                Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }
}

class Program
{
    static void Main()
    {
        QueueUsingArray queue = new QueueUsingArray(5);
        queue.Enqueue(10);
        queue.Enqueue(20);
        queue.Enqueue(30);
        queue.PrintQueue();
        int removed = queue.Dequeue();
        Console.WriteLine("Dequeued: " + removed);
        queue.PrintQueue();
        queue.Enqueue(40);
        queue.PrintQueue();
    }
}

if (IsEmpty()) { front = 0; }

Set front to 0 when first element is added

rear++; arr[rear] = value;

Advance rear and insert new element

int result = arr[front];

Store front element to return

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

If last element removed, reset queue; else move front forward

for (int i = front; i <= rear; i++) { ... }

Print elements from front to rear

Output

10 -> 20 -> 30 -> null

Dequeued: 10

20 -> 30 -> null

20 -> 30 -> 40 -> 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 an array of fixed size n to store elements

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

Edge Cases

enqueue when queue is full

Prints message and does not add element

DSA C#

if (IsFull()) { Console.WriteLine("Queue is full. Cannot enqueue " + value); return; }

dequeue when queue is empty

Prints message and returns -1

DSA C#

if (IsEmpty()) { Console.WriteLine("Queue is empty. Cannot dequeue."); return -1; }

dequeue last element

Resets front and rear to -1 to mark empty queue

DSA C#

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

When to Use This Pattern

When you need a first-in-first-out order with fixed size and fast operations, use a queue with array implementation for simple and efficient management.

Common Mistakes

Mistake: Not resetting front and rear to -1 after removing the last element
Fix: Add condition to reset front and rear when front equals rear after dequeue

Mistake: Incrementing rear before checking if queue is full
Fix: Check IsFull() before incrementing rear to avoid overflow

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 update front and rear carefully to track the queue's start and end.

Practice

1. What is the main characteristic of a queue implemented using an array?

easy

A. It removes elements from the end only.

B. It allows random access to elements.

C. It stores elements in sorted order automatically.

D. It follows First-In-First-Out (FIFO) order.

Solution

1. Step 1: Understand queue behavior

   A queue adds elements at the rear and removes from the front, following FIFO order.

2. Step 2: Compare options with queue properties

   Only It follows First-In-First-Out (FIFO) order. correctly describes FIFO behavior; others describe different data structures or incorrect behavior.

3. Final Answer:

   It follows First-In-First-Out (FIFO) order. -> Option D

4. Quick Check:

   Queue = FIFO order [OK]

Hint: Remember queue = first in, first out [OK]

Common Mistakes:

• Confusing queue with stack (LIFO)
• Thinking queue allows random access
• Assuming queue sorts elements automatically

2. Which of the following is the correct way to declare a queue array of size 5 in C#?

easy

A. int queue = new int[5];

B. int queue[] = new int(5);

C. int[] queue = new int[5];

D. int[] queue = int[5];

Solution

1. Step 1: Recall C# array declaration syntax

   In C#, arrays are declared as type[] name = new type[size];

2. Step 2: Check each option

   int[] queue = new int[5]; matches correct syntax; others have syntax errors or wrong usage.

3. Final Answer:

   int[] queue = new int[5]; -> Option C

4. Quick Check:

   C# array declaration = int[] name = new int[size] [OK]

Hint: Use type[] name = new type[size] for arrays [OK]

Common Mistakes:

• Missing [] after type
• Using parentheses instead of brackets
• Assigning array without new keyword

3. Consider this C# code for a queue using an array of size 3:

int[] queue = new int[3];
int front = -1, rear = -1;

// Enqueue 10
rear++;
queue[rear] = 10;
if(front == -1) front = 0;

// Enqueue 20
rear++;
queue[rear] = 20;

// Dequeue
int val = queue[front];
front++;

// Enqueue 30
rear++;
queue[rear] = 30;

// Current queue elements from front to rear?

medium

A. [10, 20, 30]

B. [20, 30]

C. [30]

D. [10, 30]

Solution

1. Step 1: Trace enqueue and dequeue operations

   Enqueue 10: rear=0, front=0, queue=[10,_,_] Enqueue 20: rear=1, queue=[10,20,_] Dequeue: val=queue[front]=10, front=1 Enqueue 30: rear=2, queue=[10,20,30]

2. Step 2: Identify current queue elements

   Front=1, rear=2, so elements are queue[1]=20 and queue[2]=30

3. Final Answer:

   [20, 30] -> Option B

4. Quick Check:

   After dequeue front=1, queue elements = [20, 30] [OK]

Hint: Track front and rear indexes carefully [OK]

Common Mistakes:

• Not updating front after dequeue
• Including dequeued elements in output
• Confusing front and rear positions

4. What is the error in this queue enqueue method using array?

void Enqueue(int[] queue, ref int rear, int value, int size) {
  if (rear == size) {
    Console.WriteLine("Queue is full");
    return;
  }
  rear++;
  queue[rear] = value;
}

medium

A. rear should be checked against size - 1, not size.

B. rear should be incremented after assigning value.

C. The method should check if rear is less than zero.

D. The queue array should be resized inside the method.

Solution

1. Step 1: Analyze boundary check for full queue

   Array indices go from 0 to size-1, so rear == size means out of bounds.

2. Step 2: Correct condition for full queue

   Check if rear == size - 1 before enqueue to avoid overflow.

3. Final Answer:

   rear should be checked against size - 1, not size. -> Option A

4. Quick Check:

   Array max index = size - 1 [OK]

Hint: Array max index = size - 1, check accordingly [OK]

Common Mistakes:

• Checking rear == size causes index out of range
• Incrementing rear before check
• Ignoring array bounds in enqueue

5. You want to implement a circular queue using an array of size 4. Initially, front = -1 and rear = -1. After these operations:

Enqueue(5)
Enqueue(10)
Enqueue(15)
Dequeue()
Enqueue(20)
Enqueue(25)

What will be the state of the queue array and the values of front and rear?

hard

A. Queue: [25, 10, 15, 20], front=1, rear=0

B. Queue: [5, 10, 15, 20], front=0, rear=3

C. Queue: [20, 25, 15, 10], front=2, rear=1

D. Queue: [10, 15, 20, 25], front=0, rear=3

Solution

1. Step 1: Perform each operation with circular logic

   Enqueue 5: front=0, rear=0, queue=[5,_,_,_] Enqueue 10: rear=1, queue=[5,10,_,_] Enqueue 15: rear=2, queue=[5,10,15,_] Dequeue: front=1 (removed 5) Enqueue 20: rear=3, queue=[5,10,15,20] Enqueue 25: rear wraps to 0, queue=[25,10,15,20]

2. Step 2: Final front and rear positions

   front=1, rear=0, queue array = [25,10,15,20]

3. Final Answer:

   Queue: [25, 10, 15, 20], front=1, rear=0 -> Option A

4. Quick Check:

   Circular queue wraps rear index [OK]

Hint: Remember rear wraps to 0 in circular queue [OK]

Common Mistakes:

• Not wrapping rear index after reaching end
• Not updating front after dequeue
• Assuming linear queue behavior