Dynamic Stack Using Resizable Array in DSA Typescript

Mental Model

A stack is a collection where you add and remove items from the top. When the array holding the stack is full, we create a bigger array and move everything there.

Analogy: Imagine a stack of plates on a table. When the table is too small to hold more plates, you get a bigger table and move all plates there so you can keep stacking.

Stack array: [ 1, 2, 3, null, null ]
Top index: ↑ 2 (points to 3)
null means empty space ready for new items

Dry Run Walkthrough

Input: Push values 1, 2, 3, 4 into a stack with initial array size 3

Goal: Show how the stack grows when pushing beyond initial capacity

Step 1: Push 1 onto stack

[1, null, null]
Top index: ↑ 0

Why: Add first item at position 0

Step 2: Push 2 onto stack

[1, 2, null]
Top index: ↑ 1

Why: Add second item at position 1

Step 3: Push 3 onto stack

[1, 2, 3]
Top index: ↑ 2

Why: Fill the array to capacity

Step 4: Push 4 triggers resize: create new array double size (6), copy old items

[1, 2, 3, null, null, null]
Top index: ↑ 2

Why: Need more space to add new item

Step 5: Add 4 at next position after resize

[1, 2, 3, 4, null, null]
Top index: ↑ 3

Why: Add new item after resizing

Result:

[1, 2, 3, 4, null, null]
Top index: ↑ 3

Annotated Code

DSA Typescript

class DynamicStack {
  private arr: (number | null)[];
  private top: number;

  constructor(initialSize: number = 3) {
    this.arr = new Array(initialSize).fill(null);
    this.top = -1;
  }

  push(value: number): void {
    if (this.top + 1 === this.arr.length) {
      // Resize array when full
      const newArr = new Array(this.arr.length * 2).fill(null);
      for (let i = 0; i < this.arr.length; i++) {
        newArr[i] = this.arr[i];
      }
      this.arr = newArr;
    }
    this.top++;
    this.arr[this.top] = value;
  }

  pop(): number | null {
    if (this.top === -1) return null;
    const value = this.arr[this.top];
    this.arr[this.top] = null;
    this.top--;
    return value;
  }

  printStack(): void {
    let result = '';
    for (let i = 0; i <= this.top; i++) {
      result += this.arr[i] + (i === this.top ? '' : ' -> ');
    }
    result += ' -> null';
    console.log(result);
  }
}

// Driver code
const stack = new DynamicStack(3);
stack.push(1);
stack.push(2);
stack.push(3);
stack.printStack();
stack.push(4); // triggers resize
stack.printStack();

if (this.top + 1 === this.arr.length) {

Check if array is full before adding new item

const newArr = new Array(this.arr.length * 2).fill(null);

Create a new array double the size

for (let i = 0; i < this.arr.length; i++) { newArr[i] = this.arr[i]; }

Copy old items to new bigger array

this.top++; this.arr[this.top] = value;

Move top pointer up and add new value

Output

1 -> 2 -> 3 -> null

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(n) for push when resizing because we copy all elements; O(1) average for push without resizing

Space: O(n) because we store all elements in an array that can grow

vs Alternative: Compared to fixed-size array stack, dynamic stack uses extra time and space during resize but avoids overflow errors

Edge Cases

Popping from empty stack

Returns null safely without error

DSA Typescript

if (this.top === -1) return null;

Pushing when array is full

Array resizes to double capacity before adding new item

DSA Typescript

if (this.top + 1 === this.arr.length) { ... }

Initial stack size zero or very small

Resizes properly on first push to allow growth

DSA Typescript

const newArr = new Array(this.arr.length * 2).fill(null);

When to Use This Pattern

When you need a stack but don't know the max size upfront, use a dynamic stack with resizable array to handle growth smoothly.

Common Mistakes

Mistake: Not resizing array when full causes push to overwrite or error
Fix: Add check to resize array before pushing new item

Mistake: Forgetting to update top index after push or pop
Fix: Always increment top after push and decrement after pop

Summary

It stores stack items in an array that grows when full to hold more elements.

Use it when you want a stack but don't know how many items will be pushed in advance.

The key is to double the array size and copy items when the array runs out of space.

Practice

1. What is the main advantage of using a dynamic stack implemented with a resizable array compared to a fixed-size array stack?

easy

A. It can grow or shrink in size as needed during runtime.

B. It uses less memory than a linked list stack.

C. It always has a fixed maximum size.

D. It does not require resizing or copying elements.

Solution

1. Step 1: Understand fixed vs dynamic size

   A fixed-size array stack has a set size and cannot grow beyond it, limiting capacity.

2. Step 2: Understand dynamic resizing

   A dynamic stack with resizable array can increase or decrease its size during runtime to fit more or fewer elements.

3. Final Answer:

   It can grow or shrink in size as needed during runtime. -> Option A

4. Quick Check:

   Dynamic resizing = flexible size [OK]

Hint: Dynamic arrays resize automatically when full or empty [OK]

Common Mistakes:

• Thinking dynamic stack has fixed max size
• Confusing memory use with linked list
• Assuming no resizing needed

2. Which of the following TypeScript code snippets correctly doubles the size of the internal array when the stack is full?

easy

A. this.array = [...this.array, ...new Array(this.array.length)];

B. this.array.push(...new Array(this.array.length));

C. this.array.length = this.array.length * 2;

D. const newArray = new Array(this.array.length * 2); for(let i=0; i

Solution

1. Step 1: Understand resizing by copying

   To resize, create a new larger array and copy existing elements into it.

2. Step 2: Check each option

   A uses spread but adds empty elements, not doubling size properly; B creates new array, copies elements, then replaces original array; C only changes length property but does not copy elements; D pushes empty elements, not resizing properly.

3. Final Answer:

   const newArray = new Array(this.array.length * 2); for(let i=0; i -> Option D

4. Quick Check:

   Copy elements to new larger array = B [OK]

Hint: Resize by copying elements to new bigger array [OK]

Common Mistakes:

• Only changing length without copying
• Using push to resize array
• Adding empty elements without copying

3. Consider this TypeScript code for a dynamic stack push operation:

push(value: number) {
  if (this.size === this.array.length) {
    const newArray = new Array(this.array.length * 2);
    for (let i = 0; i < this.array.length; i++) {
      newArray[i] = this.array[i];
    }
    this.array = newArray;
  }
  this.array[this.size] = value;
  this.size++;
}

If the initial array length is 2 and we push 3 elements: 10, 20, 30, what is the internal array state after these pushes?

medium

A. [10, 20, 30, undefined]

B. [10, 20, undefined, undefined]

C. [10, 20, 30, 0]

D. [10, 20, 30]

Solution

1. Step 1: Trace initial array and pushes

   Initial array length is 2, so after pushing 10 and 20, array is full.

2. Step 2: On pushing 30, array resizes to length 4 and copies elements 10, 20.

   Then 30 is added at index 2, size becomes 3.

3. Final Answer:

   [10, 20, 30, undefined] -> Option A

4. Quick Check:

   Resize doubles length, elements copied, new slot added [OK]

Hint: Resize doubles array, new elements added at next index [OK]

Common Mistakes:

• Forgetting to resize before adding third element
• Assuming array length stays 2
• Confusing undefined with 0

4. Given this pop method for a dynamic stack:

pop(): number | undefined {
  if (this.size === 0) return undefined;
  this.size--;
  const value = this.array[this.size];
  this.array[this.size] = undefined;
  if (this.size > 0 && this.size === Math.floor(this.array.length / 4)) {
    const newArray = new Array(Math.floor(this.array.length / 2));
    for (let i = 0; i < this.size; i++) {
      newArray[i] = this.array[i];
    }
    this.array = newArray;
  }
  return value;
}

What is the bug in this code?

medium

A. It does not check for empty stack before popping.

B. It sets popped element to undefined before copying, losing data.

C. It shrinks the array too early, causing frequent resizing.

D. It does not update the size after popping.

Solution

1. Step 1: Analyze order of operations

   The code sets this.array[this.size] = undefined before copying elements to newArray.

2. Step 2: Understand effect on copying

   When copying, the popped element is already undefined, so data is lost if resizing happens now.

3. Final Answer:

   It sets popped element to undefined before copying, losing data. -> Option B

4. Quick Check:

   Clear after copying to avoid data loss [OK]

Hint: Clear popped slot after resizing to keep data safe [OK]

Common Mistakes:

• Ignoring order of clearing and copying
• Shrinking array too often is not the main bug here
• Missing empty stack check is false here

5. You want to implement a dynamic stack using a resizable array that shrinks its size when the number of elements falls below one-quarter of the array length. Which approach below correctly avoids frequent resizing when pushing and popping many elements?

hard

A. Resize array to double size on push when full, and halve size on pop when size is exactly one-quarter of array length.

B. Resize array to double size on push when full, and halve size on pop when size is less than or equal to one-quarter of array length.

C. Resize array to double size on push when full, and halve size on pop only when size is less than one-quarter of array length and array length is greater than initial capacity.

D. Resize array to double size on push when full, and halve size on pop whenever size decreases.

Solution

1. Step 1: Understand resizing conditions

   Doubling on push when full is standard. Halving on pop should avoid frequent resizing.

2. Step 2: Avoid frequent resizing by checking size and minimum capacity

   Only halve when size is less than one-quarter and array length is above initial capacity to prevent shrinking too small.

3. Final Answer:

   Resize array to double size on push when full, and halve size on pop only when size is less than one-quarter of array length and array length is greater than initial capacity. -> Option C

4. Quick Check:

   Resize carefully to avoid thrashing [OK]

Hint: Shrink only if size < 1/4 and array bigger than initial [OK]

Common Mistakes:

• Shrinking too early causing many resizes
• Shrinking when size equals one-quarter causing thrashing
• Shrinking below initial capacity