Understanding the Stack Data Structure and Algorithms (LIFO) in JavaScript

Stacks are a fundamental data structure that follows the Last-In-First-Out (LIFO) principle. They are used to efficiently manage and manipulate data in various applications, such as function call tracking, expression evaluation, and more. In this article, we'll explore the stack data structure, discuss its common logic, and provide JavaScript code examples to illustrate its implementation.

A stack is a linear data structure that consists of a collection of elements. Imagine a stack of plates; to get a plate from this stack one has to take it from the topmost position.

The main operations associated with a stack are:

Push: Add an element to the top of the stack.
Pop: Remove and return the element at the top of the stack.
Peek (or Top): Retrieve the element at the top of the stack without removing it.
isEmpty: Check if the stack is empty.

Common Logic of a Stack: The key characteristic of a stack is the LIFO principle, which means that the last element added to the stack is the first one to be removed. To visualize this, think of a stack of plates. You can only add or remove plates from the top of the stack.

JavaScript Implementation of a Stack: Let's create a basic stack implementation in JavaScript using an array. We'll define a Stack class with the common stack operations:

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

  // Push operation
  push(item) {
    this.items.push(item);
  }

  // Pop operation
  pop() {
    if (!this.isEmpty()) {
      return this.items.pop();
    } else {
      return "Stack is empty";
    }
  }

  // Peek operation
  peek() {
    if (!this.isEmpty()) {
      return this.items[this.items.length - 1];
    } else {
      return "Stack is empty";
    }
  }

  // Check if the stack is empty
  isEmpty() {
    return this.items.length === 0;
  }
}

// Example usage:
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop());  // Output: 3
console.log(stack.peek()); // Output: 2
console.log(stack.isEmpty()); // Output: false

In this example, we've implemented the stack operations using an array. You can create a stack instance, push elements onto it, pop elements off it, peek at the top element, and check if it's empty.

Internal Representation:
- In JavaScript, you can implement a stack using an array, as shown in the previous example. However, you can also create a custom implementation using linked lists for more control over memory management.
Complexity Analysis:
- The time complexity of the stack operations in the array-based implementation is O(1) because pushing and popping elements from the end of an array is fast.
- When implementing a stack with a linked list, these operations remain O(1) as well.

Advanced Stack Operations:

Multiple Stacks in a Single Array:
- You can implement multiple stacks in a single array by dividing the array into sections for each stack. This can be useful in scenarios where you need to manage multiple stacks efficiently.
Stack with Min or Max Tracking:
- You can extend the basic stack to keep track of the minimum or maximum element in constant time. To achieve this, maintain an auxiliary stack that stores the minimum or maximum values as elements are pushed and popped from the main stack.
Expression Evaluation:
- Stacks are crucial in evaluating expressions, especially mathematical expressions. You can use two stacks, one for operands and another for operators, to evaluate complex expressions efficiently.

Backtracking and Undo Functionality:

Stacks can be used for implementing backtracking and undo functionality in applications, such as text editors or games. Each action is pushed onto the stack, allowing users to undo or redo operations.


  function combinationSum(candidates, target) {
    const result = []; // Initialize an empty array to store the final combinations.

    function search(startIndex, currentSum, currentCombination) {
      if (currentSum === target) {
        // Base case: If currentSum equals target, we found a valid combination.
        result.push([...currentCombination]); // Add the current combination to the result array.
        return;
      }

      if (currentSum > target) {
        return; // Base case: If currentSum exceeds target, stop this branch of recursion.
      }

      for (let i = startIndex; i < candidates.length; i++) {
        currentCombination.push(candidates[i]); // Choose the candidate and add it to the current combination.
        // Recursive call with updated startIndex to avoid duplicates and continue from the current candidate or beyond.
        search(i, currentSum + candidates[i], currentCombination);
        currentCombination.pop(); // Backtrack: Remove the last element to try the next candidate.
      }
    }

    search(0, 0, []); // Start the recursive backtracking process with startIndex = 0, currentSum = 0, and an empty currentCombination.
    return result; // Return the final list of unique combinations.
  }

Other Use Cases:

Function Call Stack:
- JavaScript uses a stack to manage function calls. When a function is called, its context is pushed onto the call stack. When the function returns, its context is popped from the stack.
Browser History:
- Browsers use a stack to keep track of the user's browsing history. When you click back or forward, pages are pushed and popped from the history stack.
Undo/Redo in Applications:
- Many applications, including text editors and graphic design software, use stacks to implement undo and redo functionality for user actions.
Expression Evaluation in Compilers:
- Compilers use stacks to parse and evaluate expressions in programming languages, ensuring the correct order of operations.

Pathfinding Algorithms:

Stacks are used in pathfinding algorithms like Depth-First Search (DFS) to explore paths in a graph.

  var pathSum = function(root, targetSum) {
      if(!root)return []

      const paths = []

      function dfs(node, target, slate){
          if(!node.left && !node.right){
              if(node.val === target){
                  slate.push(node.val);
                  paths.push(slate.slice())
                  slate.pop() //backtrack
              }

          }

          if(node.left){
              slate.push(node.val);
              dfs(node.left, target - node.val, slate)
              slate.pop()  //backtrack
          }

           if(node.right){
              slate.push(node.val);
              dfs(node.right, target - node.val, slate)
              slate.pop()  //backtrack
          }
      }
      dfs(root, targetSum, [])
      return paths;
  };

In summary, Stack is a versatile data structure with applications across various domains. Understanding the intricacies and being able to implement them effectively in JavaScript can greatly enhance your runtime management in programming and algorithm development. They are not only crucial for managing function calls and maintaining browser history but also play a vital role in more complex tasks like expression evaluation and pathfinding algorithms. For visual practice of stack data structure, click on this link cs.usfca.edu/~galles/visualization/StackArr..

Understanding the Stack Data Structure and Algorithms (LIFO) in JavaScript

Introduction

Advanced Stack Operations:

Other Use Cases: