Data Structures Series #1: Stacks - Implementation & Use Cases

Introduction Welcome to my tech blog series, where I'll explore one data structure a day! In this first post, we’ll dive into Stacks, one of the fundamental data structures in computer science. We’ll cover its implementation in JavaScript, explore real-world use cases, and provide example code to reinforce your understanding. What is a Stack? A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning the last item added is the first one to be removed. Think of a stack of plates in a cafeteria—each new plate is placed on top, and you take the top plate first. Key Operations in a Stack: Push – Adds an element to the top of the stack. Pop – Removes the top element from the stack. Peek – Returns the top element without removing it. isEmpty – Checks if the stack is empty. Size – Returns the number of elements in the stack. Implementing a Stack in JavaScript 1. Using an Array (Simplest Approach) JavaScript arrays have built-in methods (push and pop) that make it easy to implement a stack. class Stack { constructor() { this.items = []; } push(element) { this.items.push(element); } pop() { if (this.isEmpty()) { return null; } return this.items.pop(); } peek() { return this.isEmpty() ? null : this.items[this.items.length - 1]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } } // Usage example const stack = new Stack(); stack.push(10); stack.push(20); console.log(stack.peek()); // 20 console.log(stack.pop()); // 20 console.log(stack.size()); // 1 2. Using a Linked List (More Efficient for Large Data Sets) For a more efficient stack (especially for large-scale applications), we can implement it using a linked list, avoiding array resizing overhead. class Node { constructor(value) { this.value = value; this.next = null; } } class Stack { constructor() { this.top = null; this.length = 0; } push(value) { const newNode = new Node(value); newNode.next = this.top; this.top = newNode; this.length++; } pop() { if (this.isEmpty()) { return null; } const poppedValue = this.top.value; this.top = this.top.next; this.length--; return poppedValue; } peek() { return this.isEmpty() ? null : this.top.value; } isEmpty() { return this.length === 0; } size() { return this.length; } } // Usage example const stack = new Stack(); stack.push(10); stack.push(20); console.log(stack.peek()); // 20 console.log(stack.pop()); // 20 console.log(stack.size()); // 1 Real-World Use Cases of Stacks 1. Browser History Navigation When you visit a webpage, it gets pushed onto a stack. Pressing the back button pops the last visited page. class BrowserHistory { constructor() { this.history = new Stack(); } visitPage(url) { this.history.push(url); } goBack() { return this.history.pop(); } } const browser = new BrowserHistory(); browser.visitPage('google.com'); browser.visitPage('dev.to'); console.log(browser.goBack()); // dev.to 2. Undo/Redo Functionality Text editors use two stacks—one for undo and one for redo actions. 3. Expression Evaluation - Postfix, Prefix Stacks are used to evaluate expressions like Postfix (Reverse Polish Notation) and Prefix Notation. function evaluatePostfix(expression) { const stack = new Stack(); const tokens = expression.split(' '); for (let token of tokens) { if (!isNaN(token)) { stack.push(parseInt(token)); } else { const b = stack.pop(); const a = stack.pop(); switch (token) { case '+': stack.push(a + b); break; case '-': stack.push(a - b); break; case '': stack.push(a b); break; case '/': stack.push(a / b); break; } } } return stack.pop(); } console.log(evaluatePostfix("2 3 + 5 *")); // 25 4. Expression Evaluation - Syntax Parsing Stacks are used in evaluating arithmetic expressions and validating balanced parentheses in expressions like: function isBalanced(expression) { const stack = []; const pairs = { '(': ')', '{': '}', '[': ']' }; for (let char of expression) { if (pairs[char]) { stack.push(char); } else if (Object.values(pairs).includes(char)) { if (!stack.length || pairs[stack.pop()] !== char) { return false; } } } return stack.length === 0; } console.log(isBalanced("( [ { } ] )")); // true console.log(isBalanced("( [ { ] } )")); // false 5. Backtracking Algorithms Stacks are essential for solving problems using backtracking, such as maze solving, depth-first search (DFS) in graphs, etc. Conclusion Stacks are a fundamental data structure that power many real-world applications, from browser hist

Feb 23, 2025 - 13:25

Data Structures Series #1: Stacks - Implementation & Use Cases

Introduction

Welcome to my tech blog series, where I'll explore one data structure a day! In this first post, we’ll dive into Stacks, one of the fundamental data structures in computer science. We’ll cover its implementation in JavaScript, explore real-world use cases, and provide example code to reinforce your understanding.

What is a Stack?

A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning the last item added is the first one to be removed. Think of a stack of plates in a cafeteria—each new plate is placed on top, and you take the top plate first.

Key Operations in a Stack:

Push – Adds an element to the top of the stack.
Pop – Removes the top element from the stack.
Peek – Returns the top element without removing it.
isEmpty – Checks if the stack is empty.
Size – Returns the number of elements in the stack.

Implementing a Stack in JavaScript

1. Using an Array (Simplest Approach)

JavaScript arrays have built-in methods (push and pop) that make it easy to implement a stack.

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.pop();
  }

  peek() {
    return this.isEmpty() ? null : this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

// Usage example
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop());  // 20
console.log(stack.size()); // 1

2. Using a Linked List (More Efficient for Large Data Sets)

For a more efficient stack (especially for large-scale applications), we can implement it using a linked list, avoiding array resizing overhead.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.length++;
  }

  pop() {
    if (this.isEmpty()) {
      return null;
    }
    const poppedValue = this.top.value;
    this.top = this.top.next;
    this.length--;
    return poppedValue;
  }

  peek() {
    return this.isEmpty() ? null : this.top.value;
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }
}

// Usage example
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop());  // 20
console.log(stack.size()); // 1

Real-World Use Cases of Stacks

1. Browser History Navigation

When you visit a webpage, it gets pushed onto a stack. Pressing the back button pops the last visited page.

class BrowserHistory {
  constructor() {
    this.history = new Stack();
  }

  visitPage(url) {
    this.history.push(url);
  }

  goBack() {
    return this.history.pop();
  }
}

const browser = new BrowserHistory();
browser.visitPage('google.com');
browser.visitPage('dev.to');
console.log(browser.goBack()); // dev.to

2. Undo/Redo Functionality

Text editors use two stacks—one for undo and one for redo actions.

3. Expression Evaluation - Postfix, Prefix

Stacks are used to evaluate expressions like Postfix (Reverse Polish Notation) and Prefix Notation.

function evaluatePostfix(expression) {
  const stack = new Stack();
  const tokens = expression.split(' ');

  for (let token of tokens) {
    if (!isNaN(token)) {
      stack.push(parseInt(token));
    } else {
      const b = stack.pop();
      const a = stack.pop();
      switch (token) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(a / b); break;
      }
    }
  }
  return stack.pop();
}

console.log(evaluatePostfix("2 3 + 5 *")); // 25

4. Expression Evaluation - Syntax Parsing

Stacks are used in evaluating arithmetic expressions and validating balanced parentheses in expressions like:

function isBalanced(expression) {
  const stack = [];
  const pairs = { '(': ')', '{': '}', '[': ']' };

  for (let char of expression) {
    if (pairs[char]) {
      stack.push(char);
    } else if (Object.values(pairs).includes(char)) {
      if (!stack.length || pairs[stack.pop()] !== char) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

console.log(isBalanced("( [ { } ] )")); // true
console.log(isBalanced("( [ { ] } )")); // false

5. Backtracking Algorithms

Stacks are essential for solving problems using backtracking, such as maze solving, depth-first search (DFS) in graphs, etc.

Conclusion

Stacks are a fundamental data structure that power many real-world applications, from browser history management to expression evaluation. By understanding their implementation in JavaScript and their use cases, you’ll be well-equipped to use them effectively in your projects.

Stay tuned for the next post in this series, where we’ll explore Queues!