Dynamic Stack Using Resizable Array in DSA Typescript - Deep Dive

Overview - Dynamic Stack Using Resizable Array

What is it?

A dynamic stack using a resizable array is a way to store items in a last-in, first-out order where the storage space can grow or shrink as needed. Unlike a fixed-size stack, this stack can expand when more space is needed and reduce when less space is used. It uses an array that changes size automatically to hold the stack elements. This makes it flexible and efficient for varying amounts of data.

Why it matters

Without dynamic resizing, stacks would have a fixed size, causing wasted memory or errors when too many items are added. Dynamic stacks solve this by adjusting size on demand, making programs more reliable and memory-friendly. This is important in real-world applications where the amount of data is unpredictable, like undo features in apps or parsing expressions.

Where it fits

Before learning this, you should understand basic arrays and the stack concept with fixed size. After this, you can explore linked-list stacks, dynamic queues, and advanced memory management techniques.

Mental Model

Core Idea

A dynamic stack uses an array that grows or shrinks automatically to hold elements in last-in, first-out order without wasting space.

Think of it like...

Imagine a stack of plates that can magically add or remove shelves underneath to hold more or fewer plates as needed, so you never run out of space or have empty shelves wasting room.

Stack Top -> [Element N]
             [Element N-1]
             [ ... ]
             [Element 2]
             [Element 1]
Array Capacity -> |----------------------|
                 | Current Size (count) |

Build-Up - 7 Steps

1

Foundation

Understanding Basic Stack Operations

Concept: Introduce the core stack operations: push (add), pop (remove), and peek (view top).

A stack stores items so the last one added is the first one removed. Push adds an item on top, pop removes the top item, and peek shows the top item without removing it. Imagine stacking books: you add on top and remove from top only.

Result

You can add and remove items in a strict last-in, first-out order.

Understanding these operations is essential because all stack implementations, dynamic or fixed, rely on these basic rules.

2

Foundation

Fixed-Size Array Stack Basics

Concept: Learn how a stack can be built using a fixed-size array and a pointer to track the top.

Use an array with a set size, and a variable 'top' to track where the last item is. Push increases 'top' and stores the item; pop decreases 'top'. If you try to push when full, it fails; if you pop when empty, it fails.

Result

You get a working stack but limited by the fixed array size.

Knowing this shows why fixed stacks can waste space or cause errors when full, motivating dynamic resizing.

3

Intermediate

Concept of Resizable Arrays

🤔Before reading on: do you think arrays can change size automatically in all programming languages? Commit to yes or no.

Concept: Introduce the idea that arrays can be resized by creating new arrays and copying elements.

Since arrays have fixed size, to resize, create a bigger array, copy old items, then replace the old array. This lets us grow capacity when needed. Similarly, we can shrink the array when many slots are unused to save memory.

Result

You can now adjust array size dynamically, enabling flexible storage.

Understanding resizing is key to building dynamic data structures that adapt to changing data sizes.

4

Intermediate

Implementing Dynamic Stack Push Operation

🤔Before reading on: when pushing to a full array, do you think we should increase size by 1 or double the size? Commit to your answer.

Concept: Learn how to handle push when the array is full by resizing before adding the new item.

When pushing and the array is full, create a new array double the current size, copy all elements, then add the new item. Doubling size reduces how often resizing happens, improving efficiency.

Result

Push works smoothly without errors, and the stack grows as needed.

Knowing why doubling size is better than adding one prevents performance issues from frequent resizing.

5

Intermediate

Implementing Dynamic Stack Pop Operation

🤔Before reading on: after popping, should we shrink the array immediately or wait until usage is low? Commit to your answer.

Concept: Learn how to shrink the array when many slots are unused to save memory, but avoid shrinking too often.

After popping, if the number of items is less than a quarter of the array size, create a smaller array half the size and copy elements. This avoids wasting memory but prevents frequent resizing that hurts performance.

Result

Pop removes items and the stack shrinks when appropriate, balancing memory and speed.

Understanding when and how to shrink prevents memory waste without slowing down the program.

6

Advanced

TypeScript Implementation of Dynamic Stack

🤔Before reading on: do you think the top pointer should be incremented before or after adding the new element? Commit to your answer.

Concept: See a complete TypeScript class implementing a dynamic stack with resizing logic.

class DynamicStack { private array: T[]; private top: number; constructor() { this.array = new Array(2); this.top = -1; } push(item: T): void { if (this.top + 1 === this.array.length) { this.resize(this.array.length * 2); } this.top++; this.array[this.top] = item; } pop(): T | undefined { if (this.top === -1) return undefined; const item = this.array[this.top]; this.array[this.top] = undefined as any; this.top--; if (this.top + 1 > 0 && this.top + 1 === Math.floor(this.array.length / 4)) { this.resize(Math.floor(this.array.length / 2)); } return item; } peek(): T | undefined { if (this.top === -1) return undefined; return this.array[this.top]; } private resize(newCapacity: number): void { const newArray = new Array(newCapacity); for (let i = 0; i <= this.top; i++) { newArray[i] = this.array[i]; } this.array = newArray; } } // Example usage: const stack = new DynamicStack(); stack.push(10); stack.push(20); stack.push(30); stack.pop(); stack.push(40); stack.push(50); stack.pop(); stack.pop(); stack.peek();

Result

After operations, stack contains 10 -> 20 -> 40 -> null (top is 40).

Seeing the full code clarifies how resizing integrates with push and pop, and how top is managed carefully.

7

Expert

Performance and Memory Trade-offs in Resizing

🤔Before reading on: do you think resizing always improves performance or can it sometimes slow down operations? Commit to your answer.

Concept: Understand the cost of resizing and how doubling and quartering balance speed and memory use.

Resizing copies all elements, which is costly. Doubling size reduces how often resizing happens, making push mostly fast (amortized O(1)). Shrinking only when usage is low avoids frequent resizing that would slow pop. Choosing thresholds (like 1/4 for shrinking) balances memory and speed.

Result

Dynamic stack operations are efficient on average, with controlled memory use.

Knowing these trade-offs helps design stacks that perform well in real applications without wasting resources.

Under the Hood

Internally, the dynamic stack uses a fixed-size array and a 'top' index to track the last element. When pushing to a full array, it creates a new larger array, copies all elements, and replaces the old array. When popping reduces usage below a threshold, it creates a smaller array and copies elements again. This resizing ensures the stack can grow and shrink dynamically while maintaining fast access to the top element.

Why designed this way?

Arrays have fixed size, so resizing is necessary to handle unpredictable data sizes. Doubling size on growth minimizes the number of costly copy operations, improving average performance. Shrinking only when usage is low prevents frequent resizing that would degrade performance. This design balances speed and memory efficiency, which was not possible with fixed-size stacks.

┌─────────────────────────────┐
│        Dynamic Stack        │
├─────────────┬───────────────┤
│   Array     │   Top Index   │
│ [item0,...] │      top      │
├─────────────┴───────────────┤
│ Push: if full -> resize (double size) -> copy elements -> add item
│ Pop: remove item -> if usage < 1/4 capacity -> resize (half size) -> copy
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does resizing the array on every push keep the operation fast? Commit to yes or no.

Common Belief: Resizing the array every time we push an item keeps the stack operations fast.

Reality: Resizing on every push is very slow because copying all elements each time is costly. Doubling size reduces how often resizing happens, making push fast on average.

Why it matters: Without doubling, push operations become very slow, causing poor performance in real applications.

Quick: Should we shrink the array immediately after every pop? Commit to yes or no.

Common Belief: Shrinking the array immediately after every pop saves the most memory and is best practice.

Reality: Shrinking immediately causes frequent resizing, which slows down pop operations. Waiting until usage is low balances memory and speed.

Why it matters: Immediate shrinking leads to performance degradation due to repeated costly resizing.

Quick: Is a dynamic stack always better than a linked-list stack? Commit to yes or no.

Common Belief: Dynamic stacks using arrays are always better than linked-list stacks because arrays are faster.

Reality: Dynamic stacks are faster for cache and memory but resizing costs exist. Linked-list stacks avoid resizing but use more memory per element and have slower access.

Why it matters: Choosing the wrong stack type can cause inefficiency or memory waste depending on the use case.

Expert Zone

1

Doubling the array size on growth and halving on shrinkage creates amortized constant time for push and pop, but the constants matter in real systems.

2

Choosing the shrink threshold (like 1/4) is a trade-off; too high causes frequent resizing, too low wastes memory.

3

In TypeScript, using 'undefined as any' to clear popped slots avoids memory leaks but requires careful typing.

When NOT to use

Avoid dynamic array stacks when element size is very large or unknown at compile time, or when frequent insertions/removals happen in the middle of the stack. Use linked-list stacks or other data structures like dequeues or trees instead.

Production Patterns

Dynamic stacks are used in parsing expressions, undo-redo systems, backtracking algorithms, and managing function calls in interpreters. Production code often combines dynamic stacks with memory pools or custom allocators to optimize performance.

Connections

Amortized Analysis

Builds-on

Understanding how resizing costs spread over many operations explains why dynamic stacks have average constant time push/pop despite occasional expensive resizing.

Memory Management in Operating Systems

Similar pattern

Dynamic resizing of arrays mirrors how OS manages memory allocation and resizing for processes, balancing speed and memory use.

Inventory Management in Warehousing

Analogous process

Just like a warehouse adds or removes shelves based on stock levels, dynamic stacks resize storage based on data volume, optimizing space and access.

Common Pitfalls

#1 Pushing without checking capacity causes array overflow errors.

Wrong approach:

push(item: T): void {
this.top++;
this.array[this.top] = item;
}

Correct approach:

push(item: T): void {
if (this.top + 1 === this.array.length) {
this.resize(this.array.length * 2);
}
this.top++;
this.array[this.top] = item;
}

Root cause:

Not checking if the array is full before adding causes writing outside array bounds.

#2 Shrinking array immediately after every pop causes slow performance.

Wrong approach:

pop(): T | undefined {
if (this.top === -1) return undefined;
const item = this.array[this.top];
this.array[this.top] = undefined as any;
this.top--;
this.resize(this.array.length / 2);
return item;
}

Correct approach:

pop(): T | undefined {
if (this.top === -1) return undefined;
const item = this.array[this.top];
this.array[this.top] = undefined as any;
this.top--;
if (this.top + 1 > 0 && this.top + 1 === Math.floor(this.array.length / 4)) {
this.resize(Math.floor(this.array.length / 2));
}
return item;
}

Root cause:

Shrinking without threshold causes frequent costly resizing.

#3 Not updating 'top' correctly leads to incorrect stack state.

Wrong approach:

push(item: T): void {
this.array[this.top] = item;
this.top++;
}

Correct approach:

push(item: T): void {
this.top++;
this.array[this.top] = item;
}

Root cause:

Incrementing 'top' after assignment overwrites wrong index.

Key Takeaways

A dynamic stack uses a resizable array to store elements in last-in, first-out order, growing and shrinking as needed.

Doubling the array size on growth and shrinking when usage is low balances performance and memory efficiency.

Resizing involves copying elements, so it must be done carefully to avoid slowing down stack operations.

Understanding when and how to resize prevents common bugs and performance issues in dynamic stacks.

Dynamic stacks are widely used in real-world applications where data size varies unpredictably.

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