Priyadharshini Selvaraj

Posted on Feb 23

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

#programming #javascript #datastructures

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!

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on data structures and algorithms!

DEV Community