Why Queue Exists and What Problems It Solves in DSA Typescript - Why This Pattern

Mental Model

A queue helps manage tasks in the order they arrive, so the first task added is the first one done.

Analogy: Imagine a line at a coffee shop where customers wait their turn. The first person to get in line is the first to get served.

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

Dry Run Walkthrough

Input: Tasks arrive in order: Task1, Task2, Task3. We want to process them in the same order.

Goal: Show how a queue keeps tasks in order and processes them one by one, avoiding confusion or lost tasks.

Step 1: Add Task1 to the queue

Front -> [Task1] -> Rear
↑front and rear point to Task1

Why: We start the queue with the first task waiting to be processed.

Step 2: Add Task2 to the queue

Front -> [Task1] -> [Task2] -> Rear
↑front points to Task1, ↑rear points to Task2

Why: New tasks join at the rear, keeping the order intact.

Step 3: Add Task3 to the queue

Front -> [Task1] -> [Task2] -> [Task3] -> Rear
↑front points to Task1, ↑rear points to Task3

Why: Tasks keep lining up at the rear, preserving arrival order.

Step 4: Process and remove Task1 from the front

Front -> [Task2] -> [Task3] -> Rear
↑front points to Task2, ↑rear points to Task3

Why: We always process the task at the front first to keep order.

Step 5: Process and remove Task2 from the front

Front -> [Task3] -> Rear
↑front and rear point to Task3

Why: Continue processing tasks in the order they arrived.

Step 6: Process and remove Task3 from the front

Queue is empty
Front and Rear are null

Why: All tasks processed in order, queue is now empty.

Result:

Queue is empty
All tasks processed in the order: Task1, Task2, Task3

Annotated Code

DSA Typescript

class Queue<T> {
  private items: T[] = [];

  enqueue(item: T): void {
    this.items.push(item); // add to rear
  }

  dequeue(): T | undefined {
    return this.items.shift(); // remove from front
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  printQueue(): void {
    console.log(this.items.join(' -> ') + ' -> null');
  }
}

// Driver code
const queue = new Queue<string>();
queue.enqueue('Task1');
queue.enqueue('Task2');
queue.enqueue('Task3');

queue.printQueue();

while (!queue.isEmpty()) {
  const task = queue.dequeue();
  console.log('Processing:', task);
  queue.printQueue();
}

this.items.push(item); // add to rear

Add new task at the end of the queue to keep order

return this.items.shift(); // remove from front

Remove and return the task at the front to process in order

while (!queue.isEmpty()) {

Keep processing tasks until none remain

const task = queue.dequeue();

Get the next task to process from the front

Output

Task1 -> Task2 -> Task3 -> null

Processing: Task1

Task2 -> Task3 -> null

Processing: Task2

Task3 -> null

Processing: Task3

 -> null

Complexity Analysis

Time: O(n) for processing all tasks because each task is added and removed once

Space: O(n) because the queue stores all tasks until processed

vs Alternative: Without a queue, managing order manually can cause confusion and extra work; queue automates order with simple operations

Edge Cases

Empty queue when trying to dequeue

Returns undefined safely without error

DSA Typescript

return this.items.shift(); // remove from front

Single task in queue

Enqueue adds it, dequeue removes it leaving queue empty

DSA Typescript

this.items.push(item); // add to rear

When to Use This Pattern

When you need to process things in the exact order they arrive, use a queue because it guarantees first-in-first-out handling.

Common Mistakes

Mistake: Trying to process tasks from the rear instead of the front
Fix: Always remove tasks from the front to maintain correct order

Mistake: Using an array without shift() causing inefficient operations
Fix: Use shift() to remove from front or a linked list for efficient dequeue

Summary

A queue stores items so the first added is the first processed.

Use a queue when order matters and tasks must be handled one by one.

The key is adding at the rear and removing from the front to keep order.

Practice

1. Why do we use a Queue data structure instead of just using an array for all cases?

easy

A. Because queues use less memory than arrays.

B. Because arrays cannot store multiple values.

C. Because a queue follows a specific order (FIFO) which is useful for tasks like scheduling.

D. Because arrays do not allow adding elements.

Solution

1. Step 1: Understand the order of elements in a queue

   A queue follows First-In-First-Out (FIFO) order, meaning the first element added is the first to be removed.

2. Step 2: Compare with arrays and their use cases

   Arrays can store multiple values but do not enforce FIFO order automatically. Queues are designed for tasks like scheduling where order matters.

3. Final Answer:

   Because a queue follows a specific order (FIFO) which is useful for tasks like scheduling. -> Option C

4. Quick Check:

   Queue = FIFO order [OK]

Hint: Queues keep order FIFO, arrays don't enforce order [OK]

Common Mistakes:

• Thinking arrays can't store multiple values
• Confusing memory usage between queues and arrays
• Believing arrays don't allow adding elements

2. Which of the following is the correct way to add an element to the end of a queue in TypeScript?

easy

A. queue.push(element);

B. queue.pop(element);

C. queue.shift(element);

D. queue.unshift(element);

Solution

1. Step 1: Identify the method to add elements at the end of an array

   In TypeScript, push() adds an element to the end of an array, which simulates enqueue in a queue.

2. Step 2: Understand other methods

   pop() removes from the end, shift() removes from the start, and unshift() adds to the start, so they don't add to the end.

3. Final Answer:

   queue.push(element); -> Option A

4. Quick Check:

   push() adds to end [OK]

Hint: Use push() to add at queue's end [OK]

Common Mistakes:

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

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

const queue: number[] = [];
queue.push(10);
queue.push(20);
const first = 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 the queue operations step-by-step

   Initially empty queue: [] - push(10) -> [10] - push(20) -> [10, 20] - shift() removes first element 10 -> queue becomes [20] - push(30) -> [20, 30]

2. Step 2: Check the final console.log output

   The queue now contains [20, 30], so console.log prints this array.

3. Final Answer:

   [20, 30] -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Thinking shift() removes from end
• Confusing push() and unshift() effects
• Expecting original array unchanged after shift()

4. The following TypeScript code is intended to simulate a queue but has a bug. What is the bug?

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

medium

A. console.log cannot print arrays.

B. push() cannot add elements to an array.

C. queue is not initialized correctly.

D. Using pop() removes from the end, not the front of the queue.

Solution

1. Step 1: Understand queue removal operation

   In a queue, elements are removed from the front (FIFO). Using pop() removes from the end (LIFO), which is incorrect for a queue.

2. Step 2: Identify the correct method to remove from front

   The correct method to remove from the front is shift(), not pop().

3. Final Answer:

   Using pop() removes from the end, not the front of the queue. -> Option D

4. Quick Check:

   pop() removes end, queue needs front removal [OK]

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

Common Mistakes:

• Thinking pop() removes from front
• Believing push() can't add elements
• Assuming console.log can't print arrays

5. You want to process tasks in the order they arrive and also be able to add urgent tasks that should run before others. Which data structure best solves this problem and why?

hard

A. Queue, because it processes tasks in arrival order only.

B. Priority Queue, because it processes tasks based on priority and arrival order.

C. Array, because it allows random access to tasks.

D. Stack, because it processes the most recent task first.

Solution

1. Step 1: Understand the problem requirements

   Tasks must be processed in arrival order, but urgent tasks should run before others, meaning priority matters.

2. Step 2: Match data structure to requirements

   A normal queue processes strictly FIFO, ignoring priority. A stack processes last-in-first-out, which is not suitable. A priority queue processes tasks based on priority and can maintain arrival order among same priority tasks.

3. Final Answer:

   Priority Queue, because it processes tasks based on priority and arrival order. -> Option B

4. Quick Check:

   Priority Queue = priority + order [OK]

Hint: Use priority queue for priority + order tasks [OK]

Common Mistakes:

• Choosing queue ignoring priority needs
• Confusing stack order with queue order
• Thinking array handles priority automatically