Lesson 08-Data Structures – Stacks

A stack is a linear data structure that follows the “Last In First Out” (LIFO) principle. In a stack, the last element added is always the first to be removed. The basic operations of a stack include push, pop, and peek.

Basic Concepts of Stacks

A stack has the following core characteristics:

  1. Last In First Out (LIFO): The last element added is the first to be removed
  2. Basic Operations:
    • push(element): Add an element to the top of the stack
    • pop(): Remove and return the top element
    • peek(): View the top element without removing it
    • isEmpty(): Check if the stack is empty
    • size(): Return the number of elements in the stack
    • clear(): Clear the stack

Stack Implementations

Array-Based Stack Implementation

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

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

  // Pop
  pop() {
    if (this.isEmpty()) return undefined;
    return this.items.pop();
  }

  // Peek at the top element
  peek() {
    if (this.isEmpty()) return undefined;
    return this.items[this.items.length - 1];
  }

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

  // Return the stack size
  size() {
    return this.items.length;
  }

  // Clear the stack
  clear() {
    this.items = [];
  }

  // Print the stack contents
  print() {
    console.log(this.items.toString());
  }
}

Time Complexity Analysis:

  • push(): O(1) – Add to the end of the array
  • pop(): O(1) – Remove from the end of the array
  • peek(): O(1) – Access the last element of the array
  • isEmpty(): O(1)
  • size(): O(1)

Linked List-Based Stack Implementation

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

class LinkedListStack {
  constructor() {
    this.top = null; // Top of the stack
    this.bottom = null; // Bottom of the stack (optional)
    this.length = 0;
  }

  // Push
  push(data) {
    const newNode = new Node(data);
    
    if (this.isEmpty()) {
      this.top = newNode;
      this.bottom = newNode;
    } else {
      newNode.next = this.top;
      this.top = newNode;
    }
    
    this.length++;
  }

  // Pop
  pop() {
    if (this.isEmpty()) return undefined;
    
    const removedNode = this.top;
    this.top = this.top.next;
    
    if (this.length === 1) {
      this.bottom = null;
    }
    
    this.length--;
    return removedNode.data;
  }

  // Peek at the top element
  peek() {
    if (this.isEmpty()) return undefined;
    return this.top.data;
  }

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

  // Return the stack size
  size() {
    return this.length;
  }

  // Clear the stack
  clear() {
    this.top = null;
    this.bottom = null;
    this.length = 0;
  }

  // Print the stack contents
  print() {
    let current = this.top;
    const elements = [];
    
    while (current) {
      elements.push(current.data);
      current = current.next;
    }
    
    console.log(elements.reverse().join(' -> ')); // Reverse to display from bottom to top
  }
}

Time Complexity Analysis:

  • push(): O(1) – Add to the head of the linked list
  • pop(): O(1) – Remove from the head of the linked list
  • peek(): O(1) – Access the head node of the linked list
  • isEmpty(): O(1)
  • size(): O(1)

Stack Applications

Function Call Stack

The JavaScript engine uses a call stack to manage function calls:

function firstFunction() {
  console.log('First function');
  secondFunction();
  console.log('First function again');
}

function secondFunction() {
  console.log('Second function');
  thirdFunction();
  console.log('Second function again');
}

function thirdFunction() {
  console.log('Third function');
}

firstFunction();
// Output order:
// First function
// Second function
// Third function
// Second function again
// First function again

The changes in the call stack:

  1. firstFunction() is called and pushed onto the stack
  2. secondFunction() is called and pushed onto the stack
  3. thirdFunction() is called and pushed onto the stack
  4. thirdFunction() finishes execution and is popped from the stack
  5. secondFunction() continues execution and is popped from the stack
  6. firstFunction() continues execution and is popped from the stack

Expression Evaluation

Infix to Postfix Conversion (Reverse Polish Notation)

function infixToPostfix(expression) {
  const output = [];
  const operators = [];
  const precedence = { '+': 1, '-': 1, '*': 2, '/': 2, '^': 3 };
  
  for (const token of expression.split(' ')) {
    if (!isNaN(token)) {
      output.push(token);
    } else if (token in precedence) {
      while (
        operators.length > 0 &&
        precedence[operators[operators.length - 1]] >= precedence[token]
      ) {
        output.push(operators.pop());
      }
      operators.push(token);
    } else if (token === '(') {
      operators.push(token);
    } else if (token === ')') {
      while (operators.length > 0 && operators[operators.length - 1] !== '(') {
        output.push(operators.pop());
      }
      operators.pop(); // Pop the left parenthesis
    }
  }
  
  while (operators.length > 0) {
    output.push(operators.pop());
  }
  
  return output.join(' ');
}

console.log(infixToPostfix("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")); // "3 4 2 * 1 5 - 2 3 ^ ^ / +"

Postfix Expression Evaluation

function evaluatePostfix(expression) {
  const stack = new Stack();
  
  for (const token of expression.split(' ')) {
    if (!isNaN(token)) {
      stack.push(parseFloat(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;
        case '^': stack.push(a ** b); break;
        default: throw new Error(`Unknown operator: ${token}`);
      }
    }
  }
  
  return stack.pop();
}

console.log(evaluatePostfix("3 4 2 * 1 5 - 2 3 ^ ^ / +")); // 3 + ((4*2)/(1-5)^(2^3))

Parenthesis Matching

function isValidParentheses(s) {
  const stack = new Stack();
  const pairs = { ')': '(', ']': '[', '}': '{' };
  
  for (const char of s) {
    if (['(', '[', '{'].includes(char)) {
      stack.push(char);
    } else if ([')', ']', '}'].includes(char)) {
      if (stack.isEmpty() || stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }
  
  return stack.isEmpty();
}

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

Decimal to Binary Conversion

function decimalToBinary(decimalNumber) {
  const stack = new Stack();
  
  while (decimalNumber > 0) {
    stack.push(decimalNumber % 2);
    decimalNumber = Math.floor(decimalNumber / 2);
  }
  
  let binaryString = '';
  while (!stack.isEmpty()) {
    binaryString += stack.pop();
  }
  
  return binaryString || '0';
}

console.log(decimalToBinary(10)); // "1010"
console.log(decimalToBinary(255)); // "11111111"

Browser History (Forward/Backward Functionality)

class BrowserHistory {
  constructor() {
    this.backStack = new Stack(); // Back stack
    this.forwardStack = new Stack(); // Forward stack
    this.currentPage = null; // Current page
  }
  
  visit(url) {
    if (this.currentPage !== null) {
      this.backStack.push(this.currentPage);
    }
    this.currentPage = url;
    this.forwardStack.clear(); // Clear forward stack when visiting a new page
    console.log(`Visited: ${url}`);
  }
  
  back() {
    if (this.backStack.isEmpty()) {
      console.log("No pages to go back to");
      return;
    }
    
    this.forwardStack.push(this.currentPage);
    this.currentPage = this.backStack.pop();
    console.log(`Went back to: ${this.currentPage}`);
  }
  
  forward() {
    if (this.forwardStack.isEmpty()) {
      console.log("No pages to go forward to");
      return;
    }
    
    this.backStack.push(this.currentPage);
    this.currentPage = this.forwardStack.pop();
    console.log(`Went forward to: ${this.currentPage}`);
  }
  
  getCurrentPage() {
    return this.currentPage;
  }
}

const browser = new BrowserHistory();
browser.visit('google.com');
browser.visit('youtube.com');
browser.visit('facebook.com');
browser.back(); // Went back to: youtube.com
browser.forward(); // Went forward to: facebook.com
browser.visit('twitter.com'); // Went back to twitter.com (clears forward stack)
browser.forward(); // No pages to go forward to

Undo/Redo Functionality

class TextEditor {
  constructor() {
    this.text = '';
    this.undoStack = new Stack(); // Undo stack
    this.redoStack = new Stack(); // Redo stack
  }
  
  type(content) {
    this.undoStack.push(this.text);
    this.text += content;
    this.redoStack.clear(); // Clear redo stack when entering new content
    console.log(`Current text: ${this.text}`);
  }
  
  undo() {
    if (this.undoStack.isEmpty()) {
      console.log("Nothing to undo");
      return;
    }
    
    this.redoStack.push(this.text);
    this.text = this.undoStack.pop();
    console.log(`After undo: ${this.text}`);
  }
  
  redo() {
    if (this.redoStack.isEmpty()) {
      console.log("Nothing to redo");
      return;
    }
    
    this.undoStack.push(this.text);
    this.text = this.redoStack.pop();
    console.log(`After redo: ${this.text}`);
  }
}

const editor = new TextEditor();
editor.type('Hello');
editor.type(' World');
editor.undo(); // After undo: Hello
editor.redo(); // After redo: Hello World
editor.undo(); // After undo: Hello
editor.type(' JavaScript'); // Current text: Hello JavaScript
editor.undo(); // After undo: Hello

Stack Performance Optimization

  1. Dynamic Array Implementation: When implementing a stack with an array, pre-allocate a certain capacity to reduce the number of expansions
  2. Linked List Implementation Advantages: For frequent push/pop operations, linked list implementation has no expansion overhead
  3. Memory Management: Promptly clean up unused stacks to avoid memory leaks

Relationship Between Stacks and Recursion

Stacks are the underlying mechanism for recursion. Each function call creates a new stack frame on the call stack:

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1); // Each recursive call pushes a new stack frame
}

console.log(factorial(5)); // 120

Excessive recursion depth may lead to stack overflow, which can be simulated using an explicit stack:

function factorialIterative(n) {
  const stack = new Stack();
  let result = 1;
  
  while (n > 0 || !stack.isEmpty()) {
    if (n > 0) {
      stack.push(n);
      n--;
    } else {
      n = stack.pop();
      result *= n;
      n--; // Adjustments needed here; better to separate multiplication and pushing
    }
  }
  
  // A more correct implementation should separate pushing and calculation
  // This is simplified for demonstration; actual use requires a more complex algorithm
  return result; // Note: This implementation is incorrect, for demonstration only
}

Practical Application Scenarios of Stacks

  1. Browser History: Forward and backward functionality
  2. Text Editors: Undo/redo functionality
  3. Expression Evaluation: Infix to postfix conversion, postfix expression evaluation
  4. Function Call Stack: Managing function calls and return addresses
  5. Depth-First Search (DFS): Node traversal in graph algorithms
  6. Parenthesis Matching Check: Verifying if parentheses in expressions are correctly paired
  7. Backtracking Algorithms: Such as the eight queens problem, maze solving, etc.
  8. Memory Management: Storing local variables during function calls

Summary

Stacks are a simple yet powerful data structure with widespread applications in computer science and software development. Understanding the working principles and implementation methods of stacks is crucial for mastering more complex data structures and algorithms. In practical development, stacks are often used in scenarios requiring “Last In First Out” processing, such as function call management, expression evaluation, undo/redo functionality, etc.

Through this tutorial, you should be able to:

  1. Understand the basic concepts and operations of stacks
  2. Implement array-based and linked list-based stacks
  3. Apply stacks to solve practical problems
  4. Analyze the performance characteristics of stacks
  5. Understand the relationship between stacks and recursion

As one of the most fundamental data structures, stacks form the basis for learning more advanced data structures (such as queues, trees, graphs) and algorithms. Mastering the use of stacks will lay a solid foundation for your subsequent learning.

Course: Front-End Data Structures Essentials
Share your love

Trending now

Exploring Web 3D Core Technologies Development
Assembly Language Programming From Low-Level Logic to System Kernel
WebRTC Advanced Guide：Media, Transport & Architecture
WebSocket Deep Guide：Building High-Performance Realtime Systems