Dynamic Stack Using Resizable Array in DSA Typescript - Build from Scratch

Dynamic Stack Using Resizable Array

📖 Scenario: Imagine you are building a simple text editor. You want to keep track of the actions a user performs so they can undo them. A stack is perfect for this because the last action done is the first one to undo.We will create a dynamic stack that can grow when more actions are added than its current size.

🎯 Goal: Build a dynamic stack using a resizable array in TypeScript. You will create the stack, set its initial capacity, add push and pop methods that resize the array when needed, and finally print the stack contents.

📋 What You'll Learn

Create a class called DynamicStack with an internal array called items.

Add a number variable called capacity to track the allocated capacity of the array.

Implement a push method that adds an element and doubles the capacity if the array is full.

Implement a pop method that removes and returns the last element.

Print the stack contents after operations.

💡 Why This Matters

🌍 Real World

Dynamic stacks are used in undo features, expression evaluation, and backtracking algorithms where the number of elements can change over time.

💼 Career

Understanding dynamic data structures like resizable stacks is important for software developers working on efficient memory management and real-time applications.

1

Create the DynamicStack class with initial properties

Create a class called DynamicStack with a private array items initialized as an empty array of numbers, and a public number variable capacity set to 2.

DSA Typescript

class DynamicStack {
  private items: number[] = []
  public capacity: number = 2
  // Your code here
}

Hint

Use class keyword to create the class. Initialize items as an empty array and capacity as 2.

2

Add the push method with resizing logic

Inside the DynamicStack class, add a public method push that takes a value: number. If the length of items equals capacity, double the capacity. Then add the value to items.

DSA Typescript

class DynamicStack {
  private items: number[] = []
  public capacity: number = 2

  // Add push method here
}

Hint

Check if items.length equals capacity. If yes, multiply capacity by 2. Then use push to add the value.

3

Add the pop method to remove the last element

Inside the DynamicStack class, add a public method pop that returns a number | undefined. It should remove and return the last element from items using the pop array method.

DSA Typescript

class DynamicStack {
  private items: number[] = []
  public capacity: number = 2

  public push(value: number): void {
    if (this.items.length === this.capacity) {
      this.capacity *= 2
    }
    this.items.push(value)
  }

  // Add pop method here
}

Hint

Use the array pop() method to remove and return the last element.

4

Create a stack, push and pop elements, then print the stack

Create an instance of DynamicStack called stack. Push the numbers 10, 20, and 30 onto stack. Then pop one element from stack. Finally, print the current items array of stack using console.log(JSON.stringify(stack['items'])).

DSA Typescript

class DynamicStack {
  private items: number[] = []
  public capacity: number = 2

  public push(value: number): void {
    if (this.items.length === this.capacity) {
      this.capacity *= 2
    }
    this.items.push(value)
  }

  public pop(): number | undefined {
    return this.items.pop()
  }
}

// Create stack, push 10, 20, 30, pop one, then print items
// Your code here

Hint

Remember to create the stack instance, push three numbers, pop once, and then print the items array.

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