Dynamic Stack Using Resizable Array in DSA Typescript - Execution Trace

Concept Flow - Dynamic Stack Using Resizable Array

Start

↓

Push Operation?

No→Pop Operation?

↓

Check Capacity

↓

Resize Array

↓

Add Element

↓

Update Size

↓

Back to Start

The stack starts empty. On push, it checks if the array is full and resizes if needed, then adds the element. On pop, it checks if empty, then removes and returns the top element.

Execution Sample

DSA Typescript

class DynamicStack {
  private arr: number[] = new Array(2);
  private size = 0;
  private capacity = 2;

  push(x: number) {
    if (this.size === this.capacity) this.resize();
    this.arr[this.size++] = x;
  }

  pop(): number | null {
    if (this.size === 0) return null;
    return this.arr[--this.size];
  }

  private resize() {
    this.capacity *= 2;
    const newArr = new Array(this.capacity);
    for (let i = 0; i < this.size; i++) newArr[i] = this.arr[i];
    this.arr = newArr;
  }
}

This code defines a dynamic stack that doubles its array size when full and supports push and pop operations.

Execution Table

Step	Operation	Size Before	Capacity Before	Action	Size After	Capacity After	Array State
1	push(10)	0	2	Add 10 at index 0	1	2	[10, _]
2	push(20)	1	2	Add 20 at index 1	2	2	[10, 20]
3	push(30)	2	2	Resize array to capacity 4, then add 30 at index 2	3	4	[10, 20, 30, _]
4	pop()	3	4	Remove element at index 2 (30)	2	4	[10, 20, 30, _]
5	pop()	2	4	Remove element at index 1 (20)	1	4	[10, 20, 30, _]
6	pop()	1	4	Remove element at index 0 (10)	0	4	[10, 20, 30, _]
7	pop()	0	4	Stack empty, return null	0	4	[10, 20, 30, _]

💡 Execution stops after pop on empty stack returns null.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
size	0	1	2	3	2	1	0	0
capacity	2	2	2	4	4	4	4	4
arr	[]	[10, _]	[10, 20]	[10, 20, 30, _]	[10, 20, 30, _]	[10, 20, 30, _]	[10, 20, 30, _]	[10, 20, 30, _]

Key Moments - 3 Insights

Why do we resize the array before adding a new element when the stack is full?

Because the array has fixed capacity, and when size equals capacity (see step 3 in execution_table), we must create a bigger array to hold more elements before adding the new one.

Why does the array still show old values after popping elements?

Popping only decreases the size pointer (see steps 4-6), but does not erase old values. The stack ignores elements beyond current size.

What happens when we pop from an empty stack?

The pop method returns null immediately (step 7), indicating no elements to remove.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the capacity after resizing?

A 4

B 2

C 3

D 6

💡 Hint

Check the 'Capacity After' column at step 3 in execution_table.

At which step does the stack size become zero?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look at the 'size' row in variable_tracker and find when it reaches 0.

If we push one more element after step 3, what will be the size and capacity?

A Size 4, Capacity 4

B Size 4, Capacity 8

C Size 3, Capacity 4

D Size 5, Capacity 8

💡 Hint

After resizing at step 3, capacity is 4; pushing one element increases size by 1.

Concept Snapshot

Dynamic Stack Using Resizable Array:
- Use an array with initial capacity.
- Push: if full, double capacity and copy elements.
- Pop: remove top element if not empty.
- Size tracks number of elements.
- Capacity doubles to allow growth without frequent resizing.

Full Transcript

This visualization shows how a dynamic stack works using a resizable array. The stack starts empty with capacity 2. Each push adds an element at the current size index. When the array is full, it resizes by doubling capacity and copying elements. Pop removes the top element by decreasing size but does not erase old values. Popping from an empty stack returns null. The variable tracker shows size and capacity changes after each operation. The execution table details each step's action and array state.

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