Dynamic Stack Using Resizable Array in DSA Javascript

Mental Model

A stack is like a pile where you add or remove items only from the top. When the pile gets full, we make it bigger automatically to hold more items.

Analogy: Imagine a stack of plates. You can only add or take the top plate. If the stack is too tall for the shelf, you get a bigger shelf and move all plates there.

Array: [1, 2, 3, null, null]
Top points here ↑
Stack: 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: Start with empty stack, push 1, push 2, push 3, push 4 (resize needed), pop once

Goal: Show how the stack grows when full and how pop removes the top item

Step 1: push 1 onto stack

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

Why: Add first item at start of array

Step 2: push 2 onto stack

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

Why: Add next item at next free spot

Step 3: push 3 onto stack

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

Why: Add third item, still space left

Step 4: push 4 triggers resize (array full), copy old items, add 4

Array resized to size 8: [1, 2, 3, 4, null, null, null, null]
Top at index 3 ↑

Why: Array full, so double size and copy items before adding new

Step 5: pop top item (4) from stack

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

Why: Remove top item by moving top pointer down

Result:

Array: [1, 2, 3, null, null, null, null, null]
Top at index 2 ↑
Stack content: 1 -> 2 -> 3 -> null

Annotated Code

DSA Javascript

class DynamicStack {
  constructor() {
    this.array = new Array(4).fill(null); // start with size 4
    this.top = -1; // no items yet
  }

  push(value) {
    if (this.top + 1 === this.array.length) {
      // resize array when full
      const newArray = new Array(this.array.length * 2).fill(null);
      for (let i = 0; i < this.array.length; i++) {
        newArray[i] = this.array[i]; // copy old items
      }
      this.array = newArray;
    }
    this.top += 1; // move top pointer up
    this.array[this.top] = value; // add new value
  }

  pop() {
    if (this.top === -1) {
      return null; // stack empty
    }
    const value = this.array[this.top];
    this.array[this.top] = null; // clear top
    this.top -= 1; // move top pointer down
    return value;
  }

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

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

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

check if array is full to trigger resize

const newArray = new Array(this.array.length * 2).fill(null);

create bigger array double the size

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

copy old items to new bigger array

this.top += 1;

move top pointer up to add new item

this.array[this.top] = value;

store new value at top position

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

handle empty stack on pop

this.array[this.top] = null;

clear top item before moving pointer down

this.top -= 1;

move top pointer down to remove item

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(1) average for push and pop, but O(n) when resizing because all items are copied

Space: O(n) because array size grows with number of items

vs Alternative: Compared to fixed-size array stack, dynamic resizing avoids overflow but costs occasional copying

Edge Cases

pop from empty stack

returns null safely without error

DSA Javascript

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

push when array is full

array doubles in size and copies old items before adding new

DSA Javascript

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

push and pop repeatedly

stack grows and shrinks logically, array size remains until next resize

DSA Javascript

this.top += 1; and this.top -= 1;

When to Use This Pattern

When you need a stack that can grow beyond a fixed size without errors, use a dynamic array stack to resize automatically.

Common Mistakes

Mistake: Not resizing array when full causes errors or overwriting
Fix: Add check to resize array before pushing new item

Mistake: Forgetting to move top pointer after push or pop
Fix: Always update top index correctly after adding or removing

Mistake: Not clearing popped item leaves stale data
Fix: Set popped position to null to avoid confusion

Summary

Implements a stack that grows automatically by resizing its underlying array when full.

Use when you want a stack without a fixed size limit and need efficient push/pop operations.

The key is to double the array size and copy items when full, keeping push mostly fast.

Practice

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

easy

A. It does not allow duplicate elements.

B. It uses less memory than a fixed-size array stack.

C. It always has a fixed capacity to avoid resizing overhead.

D. It can grow or shrink automatically as elements are added or removed.

Solution

1. Step 1: Understand fixed-size array stack limitation

   A fixed-size array stack has a set capacity and cannot grow beyond it, causing overflow if exceeded.

2. Step 2: Understand dynamic stack advantage

   A dynamic stack using a resizable array can increase its capacity automatically when full, allowing more elements without overflow.

3. Final Answer:

   It can grow or shrink automatically as elements are added or removed. -> Option D

4. Quick Check:

   Dynamic resizing = automatic growth/shrink [OK]

Hint: Dynamic stack resizes array automatically when full [OK]

Common Mistakes:

• Thinking dynamic stack uses less memory always
• Assuming fixed capacity avoids resizing overhead
• Believing dynamic stack disallows duplicates

2. Which of the following is the correct way to double the size of the internal array in a dynamic stack implemented in JavaScript?

easy

A. this.array = new Array(this.array.length * 2);

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

C. this.array.length = this.array.length + 1;

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

Solution

1. Step 1: Understand array resizing in JavaScript

   JavaScript arrays are dynamic but to simulate resizing, we create a new larger array and copy elements.

2. Step 2: Analyze options for doubling size

   this.array = [...this.array, ...new Array(this.array.length)]; uses spread operator to copy existing elements and adds a new array of same length, effectively doubling size.

3. Final Answer:

   this.array = [...this.array, ...new Array(this.array.length)]; -> Option B

4. Quick Check:

   Spread operator copies + new array doubles size [OK]

Hint: Use spread operator to copy and extend array [OK]

Common Mistakes:

• Setting length to length + 1 only increases size by 1, not doubling
• Using push with array adds nested array, not size
• Creating new array without copying loses data

3. Consider the following JavaScript code for a dynamic stack push operation:

class DynamicStack {
  constructor() {
    this.array = [];
    this.top = -1;
  }
  push(value) {
    if (this.top + 1 === this.array.length) {
      this.array = [...this.array, ...new Array(this.array.length || 1)];
    }
    this.top++;
    this.array[this.top] = value;
  }
}
const stack = new DynamicStack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.array.slice(0, stack.top + 1));

What is the output?

medium

A. [10, 20, 30, undefined, undefined]

B. [10, 20]

C. [10, 20, 30]

D. Error: Cannot read property 'slice' of undefined

Solution

1. Step 1: Trace push operations and resizing

   Initially array is empty. First push adds 10, array resizes to length 1 (from 0), then 10 stored at index 0. Second push resizes array from length 1 to 2, adds 20 at index 1. Third push resizes from 2 to 4, adds 30 at index 2.

2. Step 2: Slice array up to top index + 1

   top is 2 after three pushes, so slice(0, 3) returns [10, 20, 30]. Extra undefined elements are beyond slice range.

3. Final Answer:

   [10, 20, 30] -> Option C

4. Quick Check:

   Slice array to top+1 = [10, 20, 30] [OK]

Hint: Slice array up to top+1 to get valid stack elements [OK]

Common Mistakes:

• Expecting undefined elements in output
• Confusing array length with number of elements
• Not updating top index correctly

4. The following code attempts to implement pop operation for a dynamic stack but has a bug:

pop() {
  if (this.top === -1) {
    return null;
  }
  const value = this.array[this.top];
  this.array[this.top] = undefined;
  this.top--;
  if (this.top < this.array.length / 4) {
    this.array.length = Math.floor(this.array.length / 2);
  }
  return value;
}

What is the bug in this pop method?

medium

A. Reducing array length directly may remove elements still in use.

B. It does not check if stack is empty before popping.

C. It does not update the top index after popping.

D. It never shrinks the array size.

Solution

1. Step 1: Understand array shrinking logic

   The code shrinks the array length when top is less than quarter of array length.

2. Step 2: Identify problem with direct length reduction

   Reducing array length directly truncates elements beyond new length, which may include valid stack elements if top is not updated properly.

3. Final Answer:

   Reducing array length directly may remove elements still in use. -> Option A

4. Quick Check:

   Direct length cut risks losing valid elements [OK]

Hint: Avoid direct length cut; copy elements to smaller array instead [OK]

Common Mistakes:

• Ignoring empty stack check
• Not decrementing top index
• Assuming array never shrinks

5. You want to implement a dynamic stack that doubles its array size when full and halves it when the number of elements falls below one-fourth of the capacity. Which approach below correctly handles resizing without losing stack elements?

hard

A. Create a new array of the new size and copy existing elements before replacing the old array.

B. Directly set the array length property to new size to resize the array.

C. Use array.push() to add undefined elements to increase size and pop() to reduce size.

D. Do not resize the array; just keep track of top index.

Solution

1. Step 1: Understand resizing requirements

   Doubling and halving array size requires creating new arrays to avoid losing elements.

2. Step 2: Analyze resizing methods

   Create a new array of the new size and copy existing elements before replacing the old array. copies elements to a new array of correct size, preserving stack data safely.

3. Step 3: Why other options fail

   Directly set the array length property to new size to resize the array. truncates or extends array without copying, losing data. Use array.push() to add undefined elements to increase size and pop() to reduce size. misuses push/pop for resizing. Do not resize the array; just keep track of top index. ignores resizing.

4. Final Answer:

   Create a new array of the new size and copy existing elements before replacing the old array. -> Option A

5. Quick Check:

   Copy elements to new array for safe resizing [OK]

Hint: Always copy elements to new array when resizing [OK]

Common Mistakes:

• Setting length property directly to resize
• Using push/pop to resize array
• Ignoring resizing and risking overflow