Queue vs Stack When to Use Which in DSA Typescript - Trade-offs & Analysis

Mental Model

A stack works like a stack of plates where you add and remove from the top. A queue works like a line at a store where the first person in line is served first.

Analogy: Imagine a stack as a pile of books where you can only add or remove the top book. A queue is like a line of people waiting to buy tickets; the first person to get in line is the first to get the ticket.

Stack (top at right): bottom -> 1 -> 2 -> 3 ↑top
Queue (front at left): front ↑1 -> 2 -> 3 -> rear

Dry Run Walkthrough

Input: Stack: push 1, push 2, pop; Queue: enqueue 1, enqueue 2, dequeue

Goal: Show how stack and queue add and remove elements differently

Step 1: Push 1 onto stack

Stack: bottom -> 1 ↑top
Queue: front null rear

Why: Add first element to stack at top

Step 2: Push 2 onto stack

Stack: bottom -> 1 -> 2 ↑top
Queue: front null rear

Why: Add second element on top of first in stack

Step 3: Pop from stack

Stack: bottom -> 1 ↑top
Queue: front null rear

Why: Remove top element from stack (last in first out)

Step 4: Enqueue 1 into queue

Stack: bottom -> 1 ↑top
Queue: front ↑1 rear

Why: Add first element to rear of queue

Step 5: Enqueue 2 into queue

Stack: bottom -> 1 ↑top
Queue: front ↑1 -> 2 rear

Why: Add second element to rear of queue

Step 6: Dequeue from queue

Stack: bottom -> 1 ↑top
Queue: front ↑2 rear

Why: Remove front element from queue (first in first out)

Result:

Stack final: bottom -> 1 ↑top
Queue final: front ↑2 rear

Annotated Code

DSA Typescript

class Stack {
  private items: number[] = [];

  push(value: number): void {
    this.items.push(value); // add to top
  }

  pop(): number | undefined {
    return this.items.pop(); // remove from top
  }

  print(): string {
    return this.items.join(' -> ') + ' -> null';
  }
}

class Queue {
  private items: number[] = [];

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

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

  print(): string {
    return this.items.join(' -> ') + ' -> null';
  }
}

// Driver code
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.pop();
console.log('Stack final:', stack.print());

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.dequeue();
console.log('Queue final:', queue.print());

this.items.push(value); // add to top

push adds element on top of stack

return this.items.pop(); // remove from top

pop removes element from top of stack

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

enqueue adds element at rear of queue

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

dequeue removes element from front of queue

Output

Stack final: 1 -> null

Queue final: 2 -> null

Complexity Analysis

Time: O(1) for push/pop in stack and enqueue in queue; dequeue is O(n) in JavaScript arrays due to shift operation, but conceptually queue operations are O(1) with linked list implementations

Space: O(n) because both stack and queue store all elements in an array

vs Alternative: Using arrays directly for stack and queue is efficient; naive approach like shifting array elements for queue dequeue is costly O(n), but here shift is used which is O(n) in JS arrays but conceptually queue operations are O(1) with linked list

Edge Cases

Pop or dequeue from empty stack or queue

Returns undefined or no element, no error

DSA Typescript

return this.items.pop(); // remove from top

Push or enqueue duplicate values

Duplicates are allowed and stored normally

DSA Typescript

this.items.push(value); // add to top/rear

When to Use This Pattern

When a problem needs last-in-first-out order, use a stack; when it needs first-in-first-out order, use a queue.

Common Mistakes

Mistake: Using stack pop operation when FIFO order is needed
Fix: Use queue dequeue operation to remove from front for FIFO

Mistake: Trying to remove from empty stack or queue without check
Fix: Check if stack or queue is empty before pop or dequeue

Summary

Stack adds/removes elements from the top (LIFO), queue adds at rear and removes from front (FIFO).

Use stack when you need to reverse order or track recent items; use queue when order of arrival matters.

Remember stack is like a pile of plates (last in first out), queue is like a line of people (first in first out).

Practice

1. Which data structure should you use when you need to process tasks in the exact order they arrive, like customers waiting in line at a store?

easy

A. Stack

B. Queue

C. Array

D. Tree

Solution

1. Step 1: Understand the order requirement

   Tasks must be processed in the order they arrive, which means first-in, first-out (FIFO).

2. Step 2: Match the data structure to FIFO

   A queue follows FIFO, so it fits the requirement perfectly.

3. Final Answer:

   Queue -> Option B

4. Quick Check:

   FIFO = Queue [OK]

Hint: Use queue for first-in, first-out order [OK]

Common Mistakes:

• Confusing stack (LIFO) with queue (FIFO)
• Choosing array without order guarantees
• Thinking tree fits linear order

2. Which of the following is the correct TypeScript syntax to add an element to the top of a stack implemented as an array named stack?

easy

A. stack.unshift(element);

B. stack.pop(element);

C. stack.shift(element);

D. stack.push(element);

Solution

1. Step 1: Identify stack operation to add element

   Adding to the top of a stack means pushing an element onto it.

2. Step 2: Match with correct array method

   In TypeScript, push() adds an element to the end (top) of the array acting as a stack.

3. Final Answer:

   stack.push(element); -> Option D

4. Quick Check:

   Push adds to stack top [OK]

Hint: Use push() to add on stack top [OK]

Common Mistakes:

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

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

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

medium

A. [3, 2]

B. [1, 2, 3]

C. [2, 3]

D. []

Solution

1. Step 1: Trace queue operations

   Elements 1, 2, 3 are added to the queue using push(). Then shift() removes the first element (1).

2. Step 2: Determine queue state after removal

   After removing 1, the queue contains [2, 3].

3. Final Answer:

   [2, 3] -> Option C

4. Quick Check:

   shift() removes first, queue left with [2, 3] [OK]

Hint: shift() removes front in queue [OK]

Common Mistakes:

• Thinking push adds to front instead of back
• Confusing shift() with pop()
• Expecting stack order instead of queue order

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

const stack: number[] = [];
stack.push(10);
stack.push(20);
const top = stack.shift();
console.log(top);

medium

A. Using shift() instead of pop() to remove top element

B. Using push() instead of unshift() to add element

C. Not initializing the stack array

D. Using console.log incorrectly

Solution

1. Step 1: Identify stack removal method

   Stack removes the top element using pop(), not shift().

2. Step 2: Analyze code's removal method

   The code uses shift(), which removes the first element, breaking stack behavior.

3. Final Answer:

   Using shift() instead of pop() to remove top element -> Option A

4. Quick Check:

   Stack removal = pop(), not shift() [OK]

Hint: Stack removes top with pop(), not shift() [OK]

Common Mistakes:

• Confusing shift() with pop()
• Thinking push() adds to front
• Ignoring array initialization

5. You are designing a system to undo and redo user actions. Which data structure combination is best suited for this, and why?

hard

A. Two stacks: one for undo, one for redo, because stacks allow reversing actions easily

B. Two queues: one for undo, one for redo, because queues maintain order of actions

C. One stack only, because redo is not needed

D. One queue only, because undo and redo are processed in order

Solution

1. Step 1: Understand undo/redo requirements

   Undo and redo require reversing and reapplying actions in last-in, first-out order.

2. Step 2: Match data structures to behavior

   Stacks naturally support LIFO, so using two stacks (undo and redo) allows easy push/pop for these operations.

3. Final Answer:

   Two stacks: one for undo, one for redo, because stacks allow reversing actions easily -> Option A

4. Quick Check:

   Undo/Redo = Two stacks (LIFO) [OK]

Hint: Undo/Redo needs two stacks for LIFO action reversal [OK]

Common Mistakes:

• Using queues which do not reverse order easily
• Ignoring redo functionality
• Using only one data structure