Stack Implementation Using Array in DSA Typescript - Execution Trace

Concept Flow - Stack Implementation Using Array

Start

↓

Initialize empty array

↓

Push operation?

Yes→Add element at array end

↓

Update top pointer

↓

Pop operation?

Yes→Remove element from array end

↓

Update top pointer

↓

Peek operation?

Yes→Return element at top

↓

Continue

↓

Is stack empty?

↓

End

The stack uses an array where push adds to the end, pop removes from the end, and peek reads the last element, tracking the top position.

Execution Sample

DSA Typescript

let stack: number[] = [];
stack.push(10);
stack.push(20);
stack.pop();
stack.push(30);
console.log(stack);

This code pushes 10 and 20, pops the last element (20), then pushes 30, finally printing the stack.

Execution Table

Step	Operation	Nodes in Stack (Array)	Top Pointer Index	Visual State
1	Initialize stack	[]	-1	Empty stack []
2	Push 10	[10]	0	10
3	Push 20	[10, 20]	1	10 -> 20
4	Pop	[10]	0	10
5	Push 30	[10, 30]	1	10 -> 30
6	Print stack	[10, 30]	1	10 -> 30

💡 All operations done, stack contains [10, 30] with top at index 1

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
stack	[]	[10]	[10, 20]	[10]	[10, 30]	[10, 30]
top	-1	0	1	0	1	1

Key Moments - 3 Insights

Why does the top pointer start at -1 instead of 0?

The top pointer is -1 initially because the stack is empty (see Step 1 in execution_table). When the first element is pushed, top moves to 0.

What happens to the top pointer after a pop operation?

After pop (Step 4), the top pointer decreases by 1 to point to the new last element (index 0), reflecting the removal of the last item.

Why do we add or remove elements only at the end of the array?

Stack follows Last-In-First-Out (LIFO), so push adds at the end and pop removes from the end, keeping operations efficient and consistent (see Steps 2,3,4,5).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the top pointer value?

A 1

B 0

C -1

D 2

💡 Hint

Check the 'Top Pointer Index' column at Step 3 in execution_table

At which step does the stack become empty again?

A Step 4

B Step 5

C Stack never becomes empty after initialization

D Step 2

💡 Hint

Look at the 'Nodes in Stack' column in execution_table; stack is empty only at Step 1

If we add stack.push(40) after Step 5, what will be the top pointer value?

A 1

B 2

C 3

D 0

💡 Hint

Pushing adds one element and increments top pointer by 1 (see Steps 2 and 3)

Concept Snapshot

Stack using array:
- Use array to hold elements
- top pointer tracks last element index (-1 if empty)
- push adds element at array end, increments top
- pop removes element from array end, decrements top
- peek reads element at top without removing
- LIFO order: last pushed is first popped

Full Transcript

This visualization shows how a stack is implemented using an array. The stack starts empty with top pointer at -1. Each push adds an element at the end of the array and moves top pointer forward. Each pop removes the last element and moves top pointer backward. The stack maintains last-in-first-out order by only adding/removing elements at the array's end. The example code pushes 10, then 20, pops once removing 20, then pushes 30. The final stack contains 10 and 30 with top pointer at index 1.

Practice

1. What is the main characteristic of a stack data structure implemented using an array?

easy

A. It stores elements in sorted order

B. It follows First In First Out (FIFO) order

C. It allows random access to elements

D. It follows Last In First Out (LIFO) order

Solution

1. Step 1: Understand stack behavior

   A stack adds and removes elements from the same end, so the last element added is the first to be removed.

2. Step 2: Identify the order type

   This behavior is called Last In First Out (LIFO).

3. Final Answer:

   It follows Last In First Out (LIFO) order -> Option D

4. Quick Check:

   Stack = LIFO [OK]

Hint: Stack always removes the last added item first [OK]

Common Mistakes:

• Confusing stack with queue (FIFO)
• Thinking stack sorts elements
• Assuming random access like arrays

2. Which of the following is the correct way to push an element 'x' onto a stack implemented as an array named stack in TypeScript?

easy

A. stack.insert(x);

B. stack.pop(x);

C. stack.push(x);

D. stack.add(x);

Solution

1. Step 1: Recall array methods for stack push

   In TypeScript, to add an element at the end of an array, use the push method.

2. Step 2: Verify other options

   pop removes elements, insert and add are not valid array methods.

3. Final Answer:

   stack.push(x); -> Option C

4. Quick Check:

   Push uses .push() method [OK]

Hint: Use .push() to add elements to array stack [OK]

Common Mistakes:

• Using pop instead of push
• Using non-existent methods like insert or add
• Confusing push with pop

3. What will be the output of the following TypeScript code implementing a stack using an array?

const stack: number[] = [];
stack.push(10);
stack.push(20);
stack.pop();
stack.push(30);
console.log(stack);

medium

A. [10, 20, 30]

B. [10, 30]

C. [20, 30]

D. [30]

Solution

1. Step 1: Trace stack operations step-by-step

   Initially stack = []. After push(10), stack = [10]. After push(20), stack = [10, 20]. After pop(), top element 20 is removed, stack = [10]. After push(30), stack = [10, 30].

2. Step 2: Determine final stack state

   The console.log prints the current stack array: [10, 30].

3. Final Answer:

   [10, 30] -> Option B

4. Quick Check:

   Push and pop update stack correctly [OK]

Hint: Pop removes last pushed element, then push adds new [OK]

Common Mistakes:

• Forgetting pop removes last element
• Assuming pop removes first element
• Confusing order of push and pop

4. Identify the error in the following TypeScript code for stack pop operation and select the correct fix.

class Stack {
  private items: number[] = [];
  pop(): number {
    return this.items.pop();
  }
}

medium

A. pop() should check if stack is empty before popping

B. items array should be public, not private

C. pop() should return void, not number

D. No error, code is correct

Solution

1. Step 1: Analyze pop method behavior

   The pop() method of array returns number | undefined if empty. Returning directly without check can cause undefined return.

2. Step 2: Identify fix for empty stack

   To avoid returning undefined, pop() should check if items is empty before popping and handle that case.

3. Final Answer:

   pop() should check if stack is empty before popping -> Option A

4. Quick Check:

   Check empty before pop to avoid undefined [OK]

Hint: Always check stack empty before pop to avoid errors [OK]

Common Mistakes:

• Ignoring empty stack check
• Changing return type incorrectly
• Making items public unnecessarily

5. Given a stack implemented using an array, how would you implement a function reverseStack that reverses the elements in the stack without using any extra stack or array? Which approach is correct?

hard

A. Use recursion to pop all elements, then insert them at bottom recursively

B. Use a for loop to swap elements from start and end indices

C. Pop all elements into a new array, then push back in reverse order

D. Use a queue to dequeue and enqueue elements to reverse order

Solution

1. Step 1: Understand constraints

   No extra stack or array allowed, so iterative swapping or extra storage is not possible.

2. Step 2: Use recursion to reverse stack

   Recursion can pop all elements, then insert each element at the bottom of the stack recursively, effectively reversing it.

3. Step 3: Evaluate other options

   Use a for loop to swap elements from start and end indices requires direct index access which is not typical for stack abstraction. Pop all elements into a new array, then push back in reverse order uses extra array. Use a queue to dequeue and enqueue elements to reverse order uses queue, which is extra data structure.

4. Final Answer:

   Use recursion to pop all elements, then insert them at bottom recursively -> Option A

5. Quick Check:

   Recursion reverses stack without extra storage [OK]

Hint: Recursion can reverse stack by inserting at bottom [OK]

Common Mistakes:

• Using extra arrays or stacks against constraints
• Trying to swap elements directly in stack
• Using other data structures like queue