Dynamic Stack Using Resizable Array in DSA Javascript - Execution Trace

Concept Flow - Dynamic Stack Using Resizable Array

Start

↓

Push Operation

↓

Check if array is full?

No→Add element at top

Yes↓

Double array size

↓

Add element at top

↓

Pop Operation

↓

Check if stack empty?

Yes→Error or return null

No↓

Remove element from top

↓

Check if array too empty?

Yes↓

Halve array size

↓

End

The stack uses an array that grows when full and shrinks when too empty, adjusting size dynamically during push and pop operations.

Execution Sample

DSA Javascript

stack = []
push(10)
push(20)
push(30)
pop()
push(40)

This code pushes three elements, pops one, then pushes another, showing dynamic resizing if needed.

Execution Table

Step	Operation	Array Size	Stack Elements	Top Index	Resize Action	Visual State
1	Initialize stack	2	[]	-1	None	[]
2	push(10)	2	[10]	0	None	[10]
3	push(20)	2	[10, 20]	1	None	[10, 20]
4	push(30)	4	[10, 20]	1	Double size to 4	[10, 20, _, _]
5	After resize push(30)	4	[10, 20, 30]	2	None	[10, 20, 30, _]
6	pop()	4	[10, 20, 30]	2	None	[10, 20, 30, _]
7	After pop()	4	[10, 20]	1	None	[10, 20, _, _]
8	push(40)	4	[10, 20, 40]	2	None	[10, 20, 40, _]

💡 Execution stops after final push; array resized once when full at step 4.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8
Array Size	2	2	2	4	4	4	4	4
Stack Elements	[]	[10]	[10, 20]	[10, 20]	[10, 20, 30]	[10, 20, 30]	[10, 20]	[10, 20, 40]
Top Index	-1	0	1	1	2	2	1	2
Resize Action	None	None	None	Double size to 4	None	None	None	None

Key Moments - 3 Insights

Why do we double the array size when it's full instead of increasing by one?

Doubling the size reduces how often resizing happens, making push operations efficient overall, as seen at step 4 where size doubles from 2 to 4.

Why do we keep track of 'Top Index' instead of just using array length?

Top Index shows the exact position of the last element, which may be less than array length due to unused slots after resizing, as shown in steps 5 and 7.

What happens if we pop when the stack is empty?

The code should handle this by returning an error or null; in this trace, popping only happens when stack is not empty (step 6), avoiding errors.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what triggers the array resize?

A The array is full before pushing 30

B The array is empty

C The top index is -1

D The array size is already 4

💡 Hint

Check the 'Resize Action' and 'Array Size' columns at step 4 in the execution table.

At which step does the 'Top Index' become 2 for the first time?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Top Index' row in variable_tracker after each step.

If we pop one more time after step 7, what should happen to the array size?

A It should halve because stack is too empty

B It should double again

C It should stay the same

D It should reset to zero

💡 Hint

Stacks usually shrink when usage is low; check the concept flow about shrinking after pop.

Concept Snapshot

Dynamic Stack Using Resizable Array:
- Uses array to store stack elements
- Push adds element at top; pop removes from top
- If array full on push, double its size
- If array too empty on pop, halve its size
- Track 'top' index to manage stack position
- Efficient resizing balances speed and memory

Full Transcript

This visualization shows how a dynamic stack uses a resizable array. Initially, the array has size 2 and is empty. Each push adds an element at the top index. When pushing 30 at step 4, the array is full, so it doubles in size to 4 before adding the element. The top index tracks the last element's position. Popping removes the top element and reduces the top index. The array can shrink when too empty, though not shown here. This dynamic resizing keeps operations efficient and memory balanced.

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