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

Mental Model

A stack is a way to keep things in order so you can only add or remove the last thing you put in. It helps solve problems where you need to remember things in reverse order.

Analogy: Imagine a stack of plates in a cafeteria. You can only add a new plate on top or take the top plate off. You can't take a plate from the middle without removing the ones above it first.

Top -> [Plate3] -> [Plate2] -> [Plate1] -> null
          ↑ (top)

Dry Run Walkthrough

Input: Push plates 1, 2, 3 onto the stack, then pop one plate

Goal: Show how stack keeps track of plates so the last one added is the first one removed

Step 1: Push plate 1 onto the stack

Top -> [Plate1] -> null
          ↑ (top)

Why: We start with an empty stack and add the first plate on top

Step 2: Push plate 2 onto the stack

Top -> [Plate2] -> [Plate1] -> null
          ↑ (top)

Why: New plate goes on top, so plate 2 is now on top of plate 1

Step 3: Push plate 3 onto the stack

Top -> [Plate3] -> [Plate2] -> [Plate1] -> null
          ↑ (top)

Why: Plate 3 is added on top, making it the last plate added

Step 4: Pop the top plate from the stack

Top -> [Plate2] -> [Plate1] -> null
          ↑ (top)

Why: Removing the top plate (plate 3) shows stack removes last added first

Result:

Top -> [Plate2] -> [Plate1] -> null
          ↑ (top) -- Plate 3 removed first, last in first out order

Annotated Code

DSA Typescript

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

  push(item: T): void {
    this.items.push(item); // add item on top
  }

  pop(): T | undefined {
    return this.items.pop(); // remove and return top item
  }

  print(): void {
    console.log('Top -> ' + this.items.slice().reverse().map(item => `[${item}]`).join(' -> ') + ' -> null');
  }
}

// Driver code
const stack = new Stack<string>();
stack.push('Plate1');
stack.push('Plate2');
stack.push('Plate3');
stack.print();
stack.pop();
stack.print();

this.items.push(item); // add item on top

add new item to the end of the array representing the top of the stack

return this.items.pop(); // remove and return top item

remove and return the last item added, following last-in-first-out order

console.log('Top -> ' + this.items.slice().reverse().map(item => `[${item}]`).join(' -> ') + ' -> null');

print stack from top to bottom by reversing the array and adding brackets for clarity

Output

Top -> [Plate3] -> [Plate2] -> [Plate1] -> null

Top -> [Plate2] -> [Plate1] -> null

Complexity Analysis

Time: O(1) for push and pop because adding or removing the last item is instant

Space: O(n) because the stack stores all items pushed onto it

vs Alternative: Compared to arrays where removing from the front is slow O(n), stack operations are fast O(1) because they only work at one end

Edge Cases

Pop from empty stack

Returns undefined safely without error

DSA Typescript

return this.items.pop(); // remove and return top item

When to Use This Pattern

When a problem needs you to remember things in reverse order or undo actions, reach for the stack pattern because it naturally handles last-in-first-out order.

Common Mistakes

Mistake: Trying to remove items from the bottom or middle of the stack
Fix: Only remove items from the top using pop to keep stack order intact

Summary

Stack stores items so the last one added is the first one removed.

Use stack when you need to reverse order or track recent actions.

The key insight is last-in-first-out order, like a stack of plates.

Practice

1. Why do we use a stack data structure in programming?

easy

A. To sort numbers in ascending order automatically

B. To store data in random order for quick access

C. To keep track of function calls and return in the correct order

D. To store large amounts of data permanently

Solution

1. Step 1: Understand the purpose of a stack

   A stack stores items in Last In First Out (LIFO) order, which is perfect for tracking function calls.

2. Step 2: Relate stack to function calls

   When a function calls another, the current function is paused and saved on the stack. When the called function finishes, the program returns to the last saved function.

3. Final Answer:

   To keep track of function calls and return in the correct order -> Option C

4. Quick Check:

   Stack = function call tracking [OK]

Hint: Stack follows LIFO, perfect for tracking nested calls [OK]

Common Mistakes:

• Thinking stack stores data randomly
• Confusing stack with queue
• Assuming stack sorts data automatically

2. Which of the following is the correct way to push an element '5' onto a stack named myStack in TypeScript?

easy

A. myStack.push(5);

B. myStack.add(5);

C. myStack.insert(5);

D. myStack.enqueue(5);

Solution

1. Step 1: Recall stack method names in TypeScript

   Stacks use push() to add elements on top.

2. Step 2: Identify correct method for adding element

   push() is the standard method; others like add(), insert(), or enqueue() are not used for stacks.

3. Final Answer:

   myStack.push(5); -> Option A

4. Quick Check:

   Push adds element on top [OK]

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

Common Mistakes:

• Using enqueue which is for queues
• Using add or insert which are not stack methods
• Confusing push with pop

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

const stack: number[] = [];
stack.push(10);
stack.push(20);
const popped = stack.pop();
stack.push(30);
console.log(stack);

medium

A. [30]

B. [10, 20, 30]

C. [20, 30]

D. [10, 30]

Solution

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

   Initially stack is empty []. Push 10 -> [10]. Push 20 -> [10, 20]. Pop removes 20 -> [10]. Push 30 -> [10, 30].

2. Step 2: Determine final stack content

   After all operations, stack contains [10, 30].

3. Final Answer:

   [10, 30] -> Option D

4. Quick Check:

   Push/pop changes stack top [OK]

Hint: Pop removes last pushed element [OK]

Common Mistakes:

• Forgetting pop removes top element
• Assuming pop returns stack without removing
• Mixing order of push and pop

4. Find the error in this TypeScript stack usage code:

const stack: number[] = [];
stack.push(1);
stack.push(2);
const top = stack.peek();
console.log(top);

medium

A. Stack does not have a peek() method by default

B. push() method is used incorrectly

C. stack should be declared as Stack<number> not number[]

D. console.log cannot print stack elements

Solution

1. Step 1: Check methods available on array used as stack

   TypeScript arrays have push() and pop(), but no peek() method by default.

2. Step 2: Identify cause of error

   Calling stack.peek() will cause a runtime error because peek() is not defined.

3. Final Answer:

   Stack does not have a peek() method by default -> Option A

4. Quick Check:

   peek() missing in array stack [OK]

Hint: Array stack has pop(), no peek() [OK]

Common Mistakes:

• Assuming peek() exists on arrays
• Thinking push() is wrong
• Confusing type declaration with method error

5. You want to reverse a string using a stack in TypeScript. Which approach correctly uses a stack to reverse the string "hello"?

hard

A. Push characters and pop in same order to keep string unchanged

B. Push each character onto stack, then pop all to build reversed string

C. Use stack to sort characters alphabetically

D. Push entire string onto stack, then pop once to get reversed string

Solution

1. Step 1: Understand stack reversal logic

   Pushing characters one by one stores them in order. Popping them reverses the order because stack is LIFO.

2. Step 2: Apply to string reversal

   Push 'h', 'e', 'l', 'l', 'o' then pop all to get 'o', 'l', 'l', 'e', 'h' which is reversed string.

3. Final Answer:

   Push each character onto stack, then pop all to build reversed string -> Option B

4. Quick Check:

   Stack LIFO reverses order [OK]

Hint: Push chars, pop all to reverse string [OK]

Common Mistakes:

• Pushing entire string at once
• Popping in same order as push
• Using stack for sorting instead of reversing