Stack Implementation Using Array in DSA Typescript

Mental Model

A stack is like a pile where you add and remove items only from the top. Using an array, we keep track of the top position to add or remove elements.

Analogy: Imagine a stack of plates. You can only put a new plate on top or take the top plate off. The array holds the plates in order, and a pointer shows which plate is on top.

Array: [ _ , _ , _ , _ , _ ]
Top index: -1 (empty stack)

Visual:
Bottom -> [ ] [ ] [ ] [ ] [ ] ← Top
           ↑top = -1 means no plates

Dry Run Walkthrough

Input: Create stack with size 5, push 10, push 20, pop, push 30

Goal: Show how the stack changes after each push and pop operation using an array

Step 1: Initialize empty stack with size 5

Array: [ _ , _ , _ , _ , _ ]
Top index: -1

Why: Start with an empty stack, top points before first element

Step 2: Push 10 onto stack

Array: [ 10 , _ , _ , _ , _ ]
Top index: 0

Why: Add 10 at position 0, top moves up to 0

Step 3: Push 20 onto stack

Array: [ 10 , 20 , _ , _ , _ ]
Top index: 1

Why: Add 20 at position 1, top moves up to 1

Step 4: Pop top element (20)

Array: [ 10 , 20 , _ , _ , _ ]
Top index: 0

Why: Remove top element by moving top down to 0, 20 is no longer accessible

Step 5: Push 30 onto stack

Array: [ 10 , 30 , _ , _ , _ ]
Top index: 1

Why: Add 30 at position 1, top moves up to 1

Result:

Array: [ 10 , 30 , _ , _ , _ ]
Top index: 1
Stack content from bottom to top: 10 -> 30 -> null

Annotated Code

DSA Typescript

class Stack {
  private arr: number[];
  private top: number;
  private size: number;

  constructor(size: number) {
    this.size = size;
    this.arr = new Array(size);
    this.top = -1; // empty stack
  }

  push(value: number): boolean {
    if (this.top === this.size - 1) {
      return false; // stack overflow
    }
    this.top++;
    this.arr[this.top] = value;
    return true;
  }

  pop(): number | null {
    if (this.top === -1) {
      return null; // stack underflow
    }
    const poppedValue = this.arr[this.top];
    this.top--;
    return poppedValue;
  }

  printStack(): void {
    let result = '';
    for (let i = 0; i <= this.top; i++) {
      result += this.arr[i] + ' -> ';
    }
    result += 'null';
    console.log(result);
  }
}

// Driver code
const stack = new Stack(5);
stack.push(10);
stack.push(20);
stack.pop();
stack.push(30);
stack.printStack();

if (this.top === this.size - 1) { return false; }

Check if stack is full before pushing to avoid overflow

this.top++; this.arr[this.top] = value;

Move top pointer up and insert new value at top

if (this.top === -1) { return null; }

Check if stack is empty before popping to avoid underflow

const poppedValue = this.arr[this.top]; this.top--; return poppedValue;

Retrieve top value and move top pointer down to remove it

for (let i = 0; i <= this.top; i++) { result += this.arr[i] + ' -> '; }

Traverse from bottom to top to print stack contents

Output

10 -> 30 -> null

Complexity Analysis

Time: O(1) for push and pop because we only add or remove from the top without traversing the array

Space: O(n) because we use an array of fixed size n to store stack elements

vs Alternative: Compared to linked list stack, array stack uses fixed memory but is faster for indexing; linked list uses dynamic memory but has overhead for pointers

Edge Cases

Push when stack is full

Push returns false and does not add element

DSA Typescript

if (this.top === this.size - 1) { return false; }

Pop when stack is empty

Pop returns null indicating no element to remove

DSA Typescript

if (this.top === -1) { return null; }

Push and pop repeatedly to empty and refill stack

Stack correctly updates top pointer and contents without error

DSA Typescript

this.top++ and this.top-- lines

When to Use This Pattern

When you need last-in-first-out (LIFO) behavior with fast access, and fixed maximum size is known, use stack with array for simple and efficient implementation.

Common Mistakes

Mistake: Not checking for stack overflow before pushing, causing array index out of bounds
Fix: Add condition to check if top reached size - 1 before pushing

Mistake: Not checking for stack underflow before popping, causing invalid access
Fix: Add condition to check if top is -1 before popping

Mistake: Printing stack from top to bottom instead of bottom to top, confusing output order
Fix: Traverse array from index 0 to top when printing stack

Summary

Implements a stack using an array with a top pointer to add and remove elements from the top.

Use when you want a simple fixed-size stack with fast push and pop operations.

Remember the top pointer moves up on push and down on pop, controlling the current stack size.

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