Queue Implementation Using Array in DSA Typescript

Mental Model

A queue is like a line where the first person in is the first person out. We use an array to hold the line and keep track of where the front and back are.

Analogy: Imagine a line at a coffee shop. People join at the end and leave from the front. The array holds the people, and two markers show who is first and last in line.

front -> [ ] [ ] [ ] [ ] [ ] ← rear
indexes  0   1   2   3   4

Dry Run Walkthrough

Input: Start with empty queue of size 5, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements enter at rear and leave from front using array indexes

Step 1: enqueue 10 at rear index 0

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

Why: First element goes at start of array, front and rear both point here

Step 2: enqueue 20 at rear index 1

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

Why: Add new element at next rear position

Step 3: dequeue element at front index 0 (remove 10)

front=1, rear=1, array=[10, 20, _, _, _]

Why: Remove front element by moving front pointer forward

Step 4: enqueue 30 at rear index 2

front=1, rear=2, array=[10, 20, 30, _, _]

Why: Add new element at next rear position

Result:

front=1, rear=2, array=[10, 20, 30, _, _] with queue elements 20 -> 30

Annotated Code

DSA Typescript

class Queue {
  private arr: number[];
  private front: number;
  private rear: number;
  private size: number;
  private capacity: number;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.arr = new Array(capacity);
    this.front = 0;
    this.rear = -1;
    this.size = 0;
  }

  enqueue(value: number): boolean {
    if (this.size === this.capacity) {
      return false; // Queue full
    }
    this.rear = (this.rear + 1) % this.capacity; // move rear forward circularly
    this.arr[this.rear] = value;
    this.size++;
    return true;
  }

  dequeue(): number | null {
    if (this.size === 0) {
      return null; // Queue empty
    }
    const value = this.arr[this.front];
    this.front = (this.front + 1) % this.capacity; // move front forward circularly
    this.size--;
    return value;
  }

  printQueue(): void {
    let result = '';
    for (let i = 0; i < this.size; i++) {
      const index = (this.front + i) % this.capacity;
      result += this.arr[index] + (i < this.size - 1 ? ' -> ' : '');
    }
    console.log(result || 'Queue is empty');
  }
}

// Driver code
const queue = new Queue(5);
queue.enqueue(10);
queue.enqueue(20);
queue.dequeue();
queue.enqueue(30);
queue.printQueue();

if (this.size === this.capacity) { return false; }

check if queue is full before adding

this.rear = (this.rear + 1) % this.capacity;

move rear pointer forward circularly to next position

this.arr[this.rear] = value;

store new value at rear position

this.size++;

increase size count after enqueue

if (this.size === 0) { return null; }

check if queue is empty before removing

const value = this.arr[this.front];

get value at front to dequeue

this.front = (this.front + 1) % this.capacity;

move front pointer forward circularly after dequeue

this.size--;

decrease size count after dequeue

for (let i = 0; i < this.size; i++) { const index = (this.front + i) % this.capacity; result += this.arr[index] + (i < this.size - 1 ? ' -> ' : ''); }

iterate from front to rear circularly to print queue elements

Output

20 -> 30

Complexity Analysis

Time: O(1) for enqueue and dequeue because we use pointers to add or remove without shifting elements

Space: O(n) because we store up to n elements in the array

vs Alternative: Compared to a linked list queue, array queue uses fixed space but faster indexing; linked list uses dynamic space but more memory per element

Edge Cases

enqueue when queue is full

enqueue returns false and does not add element

DSA Typescript

if (this.size === this.capacity) { return false; }

dequeue when queue is empty

dequeue returns null indicating no element to remove

DSA Typescript

if (this.size === 0) { return null; }

enqueue and dequeue wrap around the array end

front and rear pointers wrap circularly using modulo to reuse array space

DSA Typescript

this.rear = (this.rear + 1) % this.capacity; and this.front = (this.front + 1) % this.capacity;

When to Use This Pattern

When you need a first-in-first-out order with fixed size and fast operations, use a circular array queue to efficiently manage elements.

Common Mistakes

Mistake: Not using modulo to wrap front and rear pointers, causing index out of bounds
Fix: Use modulo operator (%) with capacity to wrap pointers circularly

Mistake: Not checking if queue is full before enqueue, leading to overwriting elements
Fix: Check size against capacity before adding new element

Mistake: Not updating size correctly after enqueue or dequeue
Fix: Increment size after enqueue and decrement after dequeue

Summary

Implements a queue using a fixed-size array with front and rear pointers.

Use when you want a simple, fast queue with a known maximum size.

The key is to move front and rear pointers circularly to reuse array space without shifting.

Practice

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

easy

A. It stores elements in sorted order automatically

B. It follows Last-In-First-Out (LIFO) order

C. It allows random access to elements

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, so the first element added is the first removed.

2. Step 2: Compare with options

   FIFO means First-In-First-Out, which matches queue behavior. LIFO is for stacks, random access is for arrays, and sorting is unrelated.

3. Final Answer:

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

4. Quick Check:

   Queue = FIFO [OK]

Hint: Queue always removes the oldest element first [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 add an element `x` to the rear of a queue implemented as an array named `queue` in TypeScript?

easy

A. queue.unshift(x);

B. queue.push(x);

C. queue.shift(x);

D. queue.pop(x);

Solution

1. Step 1: Identify array methods for queue operations

   To add at the rear of the queue, we use the array method that appends elements at the end, which is push().

2. Step 2: Check each option

   push(x) adds x at the end; pop() removes from end; shift() removes from front; unshift() adds at front.

3. Final Answer:

   queue.push(x); -> Option B

4. Quick Check:

   Enqueue = push() [OK]

Hint: Use push() to add at the end of array [OK]

Common Mistakes:

• Using pop() which removes instead of adds
• Using shift() or unshift() incorrectly for enqueue
• Confusing push() with unshift()

3. What will be the output of the following TypeScript code implementing a queue using an array?

const queue: number[] = [];
queue.push(10);
queue.push(20);
const removed = queue.shift();
queue.push(30);
console.log(queue);

medium

A. [20, 30]

B. [10, 20, 30]

C. [30, 20]

D. [10, 30]

Solution

1. Step 1: Trace queue operations step-by-step

   Initially queue = []. After push(10), queue = [10]. After push(20), queue = [10, 20]. shift() removes first element 10, queue = [20]. Then push(30), queue = [20, 30].

2. Step 2: Determine final queue state

   After all operations, queue contains [20, 30].

3. Final Answer:

   [20, 30] -> Option A

4. Quick Check:

   After shift(), first element removed, queue = [20, 30] [OK]

Hint: shift() removes front, push() adds rear [OK]

Common Mistakes:

• Forgetting shift() removes first element
• Assuming push() adds at front
• Confusing order of elements after operations

4. Identify the error in the following TypeScript code for queue implementation using an array:

const queue: number[] = [];
queue.push(1);
queue.push(2);
const removed = queue.pop();
console.log(queue);

medium

A. push() should be replaced with unshift()

B. queue should be declared as a linked list

C. Using pop() removes from rear, not front

D. No error, code works correctly

Solution

1. Step 1: Understand queue removal operation

   Queue removes elements from the front (FIFO). Using pop() removes from the rear (last element), which breaks FIFO.

2. Step 2: Check code behavior

   pop() removes last element (2), but queue should remove first element (1) using shift().

3. Final Answer:

   Using pop() removes from rear, not front -> Option C

4. Quick Check:

   Dequeue = shift(), not pop() [OK]

Hint: Use shift() to remove front element, not pop() [OK]

Common Mistakes:

• Using pop() instead of shift() for dequeue
• Thinking push() adds at front
• Confusing array methods for queue operations

5. You want to implement a queue using a fixed-size array of length 3 in TypeScript. After enqueueing 3 elements, you dequeue one element and then enqueue another. What problem will you face if you do not use a circular queue approach?

hard

A. You cannot enqueue the new element because the rear index reached the array end

B. The queue will automatically resize to fit new elements

C. Dequeue operation will remove the wrong element

D. The queue will lose all previous elements

Solution

1. Step 1: Understand fixed-size array queue behavior

   With a fixed-size array, rear index moves forward on enqueue. After 3 enqueues, rear is at end.

2. Step 2: Analyze enqueue after dequeue without circular logic

   Dequeue moves front forward but rear stays at end. Without circular wrap, rear cannot move back to start, so enqueue fails.

3. Final Answer:

   You cannot enqueue the new element because the rear index reached the array end -> Option A

4. Quick Check:

   Fixed array + no circular = enqueue blocked at end [OK]

Hint: Fixed array needs circular logic to reuse space [OK]

Common Mistakes:

• Assuming array resizes automatically
• Thinking dequeue affects rear index
• Ignoring circular queue necessity