Queue Concept and FIFO Principle in DSA Typescript

Mental Model

A queue is a line where the first person in is the first person out. We add items at the back and remove from the front.

Analogy: Imagine waiting in line at a coffee shop. The first person who gets in line is the first to get served and leave the line.

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

Dry Run Walkthrough

Input: Start with empty queue, enqueue 1, enqueue 2, enqueue 3, then dequeue one item

Goal: Show how items enter at the back and leave from the front following FIFO

Step 1: enqueue 1 at back

front -> [1] -> null <- back

Why: First item added becomes both front and back

Step 2: enqueue 2 at back

front -> [1] -> [2] -> null <- back

Why: Add new item after current back to keep order

Step 3: enqueue 3 at back

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

Why: Add new item at the end to maintain queue order

Step 4: dequeue item from front

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

Why: Remove the first item that entered to follow FIFO

Result:

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

Annotated Code

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  front: Node | null;
  back: Node | null;

  constructor() {
    this.front = null;
    this.back = null;
  }

  enqueue(value: number): void {
    const newNode = new Node(value);
    if (!this.back) {
      this.front = newNode;
      this.back = newNode;
      return;
    }
    this.back.next = newNode; // link new node after back
    this.back = newNode; // update back pointer
  }

  dequeue(): number | null {
    if (!this.front) return null; // empty queue
    const dequeuedValue = this.front.value;
    this.front = this.front.next; // move front forward
    if (!this.front) this.back = null; // queue empty now
    return dequeuedValue;
  }

  printQueue(): string {
    let result = '';
    let current = this.front;
    while (current) {
      result += `[${current.value}] -> `;
      current = current.next;
    }
    return 'front -> ' + result + 'null <- back';
  }
}

// Driver code
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue();
console.log(queue.printQueue());

this.back.next = newNode; // link new node after back

attach new node at the end of queue to keep order

this.back = newNode; // update back pointer

move back pointer to new last node

this.front = this.front.next; // move front forward

remove front node by moving front pointer forward

if (!this.front) this.back = null; // queue empty now

if queue is empty after dequeue, reset back pointer

Output

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

Complexity Analysis

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

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

vs Alternative: Compared to arrays where dequeue can be O(n) due to shifting elements, linked list queue keeps both operations O(1)

Edge Cases

dequeue from empty queue

returns null and does not crash

DSA Typescript

if (!this.front) return null; // empty queue

enqueue first element into empty queue

front and back both point to the new node

DSA Typescript

if (!this.back) { this.front = newNode; this.back = newNode; return; }

dequeue last element leaving queue empty

front and back both become null

DSA Typescript

if (!this.front) this.back = null; // queue empty now

When to Use This Pattern

When you see a problem requiring first-in-first-out order, think of the queue pattern because it naturally models waiting lines and order of processing.

Common Mistakes

Mistake: Not updating the back pointer after enqueue, causing new nodes to be disconnected
Fix: Always move the back pointer to the newly added node after linking it

Mistake: Not resetting back pointer to null when queue becomes empty after dequeue
Fix: Check if front is null after dequeue and set back to null to avoid stale pointers

Summary

A queue stores items in order and removes them in the same order they arrived (FIFO).

Use a queue when you need to process items in the exact order they come, like tasks or requests.

The key is to add at the back and remove from the front to keep the order correct.

Practice

1. What does the FIFO principle mean in the context of a queue?

easy

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

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

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

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

Solution

1. Step 1: Understand FIFO meaning

   FIFO means the first element that enters the queue is the first to leave.

2. Step 2: Match FIFO to queue behavior

   Queues follow FIFO, so the first added element is removed first.

3. Final Answer:

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

4. Quick Check:

   FIFO = First In, First Out [OK]

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

Common Mistakes:

• Confusing FIFO with LIFO
• Thinking last added is removed first
• Mixing queue with stack behavior

2. Which of the following is the correct TypeScript syntax to create an empty queue using an array?

easy

A. let queue = {};

B. const queue: number[] = [];

C. const queue = new Queue();

D. queue = [];

Solution

1. Step 1: Identify TypeScript array syntax

   To create an empty array of numbers, use const queue: number[] = [];

2. Step 2: Check other options

   const queue = new Queue(); uses a class not defined here, A creates an object, D is missing declaration keyword.

3. Final Answer:

   const queue: number[] = []; -> Option B

4. Quick Check:

   Array declaration with type and empty brackets [OK]

Hint: Use const with type and empty brackets for empty array [OK]

Common Mistakes:

• Using object {} instead of array []
• Missing type annotation in TypeScript
• Omitting declaration keyword (const/let)

3. What will be the output of the following TypeScript code?

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

medium

A. []

B. [10, 20, 30]

C. [30]

D. [20, 30]

Solution

1. Step 1: Add elements to queue

   Elements 10, 20, 30 are added to the queue in order.

2. Step 2: Remove first element using shift()

   shift() removes 10, so queue now contains [20, 30].

3. Final Answer:

   [20, 30] -> Option D

4. Quick Check:

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

Hint: shift() removes first element, push() adds last [OK]

Common Mistakes:

• Confusing shift() with pop()
• Expecting original array unchanged
• Thinking push() removes elements

4. Identify the error in this TypeScript queue code:

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

medium

A. Using pop() removes last, not first element in queue

B. push() is not valid for arrays

C. queue should be declared as object, not array

D. Missing type annotation for queue

Solution

1. Step 1: Understand queue removal method

   Queue removes elements in FIFO order, so first element should be removed.

2. Step 2: Check method used

   pop() removes last element, which breaks FIFO principle.

3. Final Answer:

   Using pop() removes last, not first element in queue -> Option A

4. Quick Check:

   Queue removal must use shift(), not pop() [OK]

Hint: Use shift() to remove first, pop() removes last [OK]

Common Mistakes:

• Using pop() instead of shift() for queue
• Thinking push() removes elements
• Confusing array with object declaration

5. You have a queue implemented as an array in TypeScript. You add elements 1, 2, 3, then remove two elements. What will be the state of the queue after these operations?

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

hard

A. [2, 3]

B. [1, 2, 3]

C. [3]

D. []

Solution

1. Step 1: Add elements to queue

   Elements 1, 2, 3 are added in order: queue = [1, 2, 3]

2. Step 2: Remove two elements using shift()

   First shift() removes 1, second shift() removes 2, leaving [3]

3. Final Answer:

   [3] -> Option C

4. Quick Check:

   After two shifts, queue = [3] [OK]

Hint: Each shift() removes one from front [OK]

Common Mistakes:

• Removing elements with pop() instead of shift()
• Expecting queue to be empty after two removals
• Confusing order of elements after removals