Stack Implementation Using Array in DSA Typescript - Deep Dive

Overview - Stack Implementation Using Array

What is it?

A stack is a simple data structure that stores items in a specific order. You can only add or remove items from the top, like a stack of plates. Using an array to build a stack means we use a list of elements where the last added item is the first to be removed. This is called Last In, First Out (LIFO).

Why it matters

Stacks help solve many problems where order matters, like undo actions in apps or checking matching brackets in code. Without stacks, managing such tasks would be confusing and inefficient. They make programs easier to write and understand by controlling how data is accessed and changed.

Where it fits

Before learning stacks, you should know what arrays are and how to use them. After stacks, you can learn about queues, linked lists, and more complex data structures like trees and graphs.

Mental Model

Core Idea

A stack using an array is like a pile where you only add or remove items from the top, following last-in, first-out order.

Think of it like...

Imagine a stack of books on a table. You can only put a new book on top or take the top book off. You cannot take a book from the middle without removing the ones above it first.

Stack (top at right) using array indexes:

Index: 0   1   2   3   4
Value: A | B | C | D | E
                 ↑
               Top

Push adds at the top index, pop removes from the top index.

Build-Up - 7 Steps

1

Foundation

Understanding Stack Basics

Concept: Learn what a stack is and how it works with simple operations.

A stack stores items in order. You can add (push) an item on top or remove (pop) the top item. The last item added is the first one removed. Think of it like a stack of plates where you only take from the top.

Result

You understand the LIFO (Last In, First Out) principle and basic stack operations: push and pop.

Understanding the LIFO order is key to using stacks correctly in many programming problems.

2

Foundation

Arrays as Storage for Stacks

Concept: Use arrays to hold stack items and track the top position.

An array is a list of items stored in order. We use an array to hold stack elements. We keep a number called 'top' to know where the last item is. When we push, we add at 'top + 1'. When we pop, we remove from 'top' and decrease it.

Result

You can visualize the stack inside an array and know how to add or remove items by changing the 'top' index.

Using an array with a 'top' index lets us manage stack operations efficiently and simply.

3

Intermediate

Implementing Push Operation

🤔Before reading on: do you think pushing an item increases or decreases the top index? Commit to your answer.

Concept: Add a new item to the stack by placing it at the next position in the array and updating the top index.

To push an item: 1. Check if the stack is full (top is at last array index). 2. If not full, increase top by 1. 3. Place the new item at array[top]. Example in TypeScript: class Stack { private items: string[] = []; private top: number = -1; private maxSize: number; constructor(size: number) { this.maxSize = size; this.items = new Array(size); } push(item: string): void { if (this.top === this.maxSize - 1) { console.log('Stack Overflow'); return; } this.top++; this.items[this.top] = item; } }

Result

Items are added on top of the stack until it reaches max size, preventing overflow.

Knowing how to check for overflow and update the top index prevents errors and keeps the stack safe.

4

Intermediate

Implementing Pop Operation

🤔Before reading on: do you think popping an item removes it from the start or the top of the array? Commit to your answer.

Concept: Remove the top item from the stack and update the top index accordingly.

To pop an item: 1. Check if the stack is empty (top is -1). 2. If not empty, get the item at array[top]. 3. Decrease top by 1. 4. Return the removed item. Example in TypeScript: pop(): string | undefined { if (this.top === -1) { console.log('Stack Underflow'); return undefined; } const poppedItem = this.items[this.top]; this.top--; return poppedItem; }

Result

Items are removed from the top in reverse order of addition, preventing underflow errors.

Checking for underflow ensures you don't remove items from an empty stack, avoiding runtime errors.

5

Intermediate

Peek and IsEmpty Operations

🤔Before reading on: do you think peek changes the stack or just shows the top item? Commit to your answer.

Concept: Add operations to look at the top item without removing it and to check if the stack is empty.

Peek operation: - Returns the item at the top without changing the stack. IsEmpty operation: - Returns true if top is -1, meaning no items. Example in TypeScript: peek(): string | undefined { if (this.top === -1) return undefined; return this.items[this.top]; } isEmpty(): boolean { return this.top === -1; }

Result

You can safely check the top item and know if the stack has any items without changing it.

Peek and isEmpty help write safer code by letting you inspect the stack state without modifying it.

6

Advanced

Handling Stack Overflow and Underflow

🤔Before reading on: do you think ignoring overflow/underflow causes silent bugs or immediate errors? Commit to your answer.

Concept: Learn to detect and handle errors when pushing to a full stack or popping from an empty stack.

Stack Overflow: - Happens when pushing an item but the stack is full. - Must prevent adding more items. Stack Underflow: - Happens when popping from an empty stack. - Must prevent removing items that don't exist. Example handling: push(item: string): void { if (this.top === this.maxSize - 1) { throw new Error('Stack Overflow'); } this.top++; this.items[this.top] = item; } pop(): string { if (this.top === -1) { throw new Error('Stack Underflow'); } const item = this.items[this.top]; this.top--; return item; }

Result

Your stack safely prevents invalid operations and signals errors clearly.

Handling these errors prevents crashes and bugs, making your stack reliable in real programs.

7

Expert

Optimizing Stack with Dynamic Arrays

🤔Before reading on: do you think fixed-size arrays or dynamic resizing is better for all stack uses? Commit to your answer.

Concept: Improve stack flexibility by resizing the array when needed instead of fixed size.

Fixed-size arrays limit stack capacity. To allow more items: - When full, create a bigger array. - Copy old items to new array. - Continue pushing. Example snippet: push(item: string): void { if (this.top === this.items.length - 1) { const newItems = new Array(this.items.length * 2); for (let i = 0; i < this.items.length; i++) { newItems[i] = this.items[i]; } this.items = newItems; } this.top++; this.items[this.top] = item; }

Result

Stack can grow as needed, avoiding overflow errors and improving usability.

Dynamic resizing balances memory use and flexibility, a key technique in real-world stack implementations.

Under the Hood

The stack uses an array and a 'top' index to track the last added item. Push increments 'top' and stores the item; pop returns the item at 'top' and decrements it. The array holds all items in order, but only the 'top' item is accessible for removal or inspection. Overflow happens if 'top' reaches the array's end; underflow if 'top' is -1.

Why designed this way?

Arrays provide fast access by index and simple memory layout. Using a 'top' index avoids shifting elements, making push/pop operations O(1) time. This design is simple, efficient, and easy to implement, which is why it became a standard approach. Alternatives like linked lists add complexity and overhead.

Stack Implementation Using Array:

┌───────────────┐
│   Array       │
│  ┌─────────┐  │
│  │ Items   │  │
│  │ [A,B,C] │  │
│  └─────────┘  │
│               │
│  top -> index 2│
└───────────────┘

Operations:
Push: top++ and add item at array[top]
Pop: remove item at array[top] and top--

Myth Busters - 4 Common Misconceptions

Quick: Does popping an item remove it from the start of the array or the top? Commit to your answer.

Common Belief: Popping removes the first item added, like a queue.

Reality: Popping removes the last item added, following last-in, first-out order.

Why it matters: Confusing stack with queue leads to wrong program behavior and bugs in algorithms relying on LIFO order.

Quick: Can a stack implemented with an array grow automatically without extra code? Commit to your answer.

Common Belief: Arrays automatically resize, so stack size is unlimited.

Reality: Fixed-size arrays do not resize automatically; you must code resizing or risk overflow.

Why it matters: Assuming automatic resizing causes unexpected crashes when the stack is full.

Quick: Is it safe to pop from an empty stack without checks? Commit to your answer.

Common Belief: Yes, popping from empty stack just returns undefined or null safely.

Reality: Popping from empty stack causes underflow error or invalid data access if unchecked.

Why it matters: Ignoring underflow leads to runtime errors and unstable programs.

Quick: Does peek remove the top item from the stack? Commit to your answer.

Common Belief: Peek removes the top item like pop but without returning it.

Reality: Peek only shows the top item without removing it or changing the stack.

Why it matters: Misusing peek as pop causes data loss and unexpected behavior.

Expert Zone

1

The 'top' index starts at -1 to indicate an empty stack, which simplifies boundary checks.

2

Using a fixed-size array is memory efficient but requires careful overflow handling or resizing logic.

3

Dynamic resizing typically doubles the array size to balance between memory use and performance.

When NOT to use

Avoid array-based stacks when you need unlimited size without resizing or when frequent insertions/removals happen in the middle. Use linked-list-based stacks or other dynamic data structures instead.

Production Patterns

Stacks implemented with arrays are used in expression evaluation, syntax parsing, undo mechanisms, and backtracking algorithms. Production code often includes error handling for overflow/underflow and may use dynamic resizing for flexibility.

Connections

Queue Implementation Using Array

Both use arrays but differ in access order; stack is LIFO, queue is FIFO.

Understanding stack helps grasp queue differences, highlighting how access order changes data structure behavior.

Function Call Stack in Programming

The function call stack is a real-world example of a stack data structure managing execution order.

Knowing stack implementation clarifies how programs track function calls and returns, aiding debugging and optimization.

Undo Feature in Text Editors

Undo uses stacks to reverse recent actions in last-in, first-out order.

Recognizing stacks in user interfaces shows how data structures impact everyday software usability.

Common Pitfalls

#1 Pushing items without checking for stack overflow.

Wrong approach:

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

Correct approach:

push(item: string): void {
if (this.top === this.maxSize - 1) {
console.log('Stack Overflow');
return;
}
this.top++;
this.items[this.top] = item;
}

Root cause:

Not checking array bounds leads to writing outside allocated memory, causing errors.

#2 Popping items without checking if stack is empty.

Wrong approach:

pop(): string {
const item = this.items[this.top];
this.top--;
return item;
}

Correct approach:

pop(): string | undefined {
if (this.top === -1) {
console.log('Stack Underflow');
return undefined;
}
const item = this.items[this.top];
this.top--;
return item;
}

Root cause:

Ignoring empty stack state causes invalid data access and runtime errors.

#3 Using peek to remove the top item instead of just viewing it.

Wrong approach:

peek(): string | undefined {
if (this.top === -1) return undefined;
const item = this.items[this.top];
this.top--;
return item;
}

Correct approach:

peek(): string | undefined {
if (this.top === -1) return undefined;
return this.items[this.top];
}

Root cause:

Confusing peek with pop causes unintended removal of stack items.

Key Takeaways

A stack is a last-in, first-out data structure where items are added and removed only from the top.

Using an array with a 'top' index efficiently implements stack operations with constant time complexity.

Always check for stack overflow before pushing and underflow before popping to avoid errors.

Peek and isEmpty operations let you safely inspect the stack without changing it.

Dynamic resizing of the array improves stack flexibility but requires extra code to manage memory.

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