Step 5 of 5

100% Complete

Applications of Stacks

Explore real-world uses of stack data structures

Common Applications of Stacks

Stacks are one of the most widely used data structures in computer science. Their LIFO (Last-In-First-Out) behavior makes them perfect for many applications where the most recently added item needs to be processed first.

Let's explore some of the most common and important applications of stacks.

1. Function Call Management

One of the most important applications of stacks is in managing function calls in programming languages. When a function is called, its execution context (local variables, return address, etc.) is pushed onto a stack known as the "call stack."

When the function returns, its context is popped from the stack, and execution resumes from the return address.

Call Stack Example:

function first() {
  console.log("Starting first");
  second();
  console.log("Ending first");
}
 
function second() {
  console.log("Starting second");
  third();
  console.log("Ending second");
}
 
function third() {
  console.log("In third function");
}
 
// Call stack progression:
// 1. main() is pushed
// 2. first() is pushed
// 3. second() is pushed
// 4. third() is pushed
// 5. third() completes and is popped
// 6. second() completes and is popped
// 7. first() completes and is popped
// 8. main() continues
 
first();

Output:

Starting first Starting second In third function Ending second Ending first

2. Expression Evaluation

Stacks are used to evaluate expressions, particularly those in postfix (Reverse Polish) notation. They're also used in the implementation of expression parsers and compilers.

Evaluating Postfix Expression:

function evaluatePostfix(expression) {
  const stack = new Stack();
  
  for (let token of expression.split(' ')) {
    if (!isNaN(token)) {
      // If token is a number, push it onto the stack
      stack.push(Number(token));
    } else {
      // If token is an operator, pop two operands and apply the operator
      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;
      }
    }
  }
  
  // The final result should be the only item left on the stack
  return stack.pop();
}
 
// Example: "2 3 + 5 *" = (2 + 3) * 5 = 25
console.log(evaluatePostfix("2 3 + 5 *")); // Output: 25

3. Balanced Parentheses

Stacks are perfect for checking if an expression has balanced parentheses, brackets, and braces. This is a common problem in code editors, compilers, and syntax validators.

Checking Balanced Parentheses:

function isBalanced(expression) {
  const stack = new Stack();
  
  for (let char of expression) {
    if (char === '(' || char === '[' || char === '{') {
      // Push opening brackets onto the stack
      stack.push(char);
    } else if (char === ')' || char === ']' || char === '}') {
      // For closing brackets, check if they match the top of the stack
      if (stack.isEmpty()) {
        return false; // More closing brackets than opening
      }
      
      const top = stack.pop();
      
      // Check if the popped bracket matches the current closing bracket
      if ((char === ')' && top !== '(') || 
          (char === ']' && top !== '[') || 
          (char === '}' && top !== '{')) {
        return false; // Mismatched brackets
      }
    }
  }
  
  // If the stack is empty, all brackets were matched
  return stack.isEmpty();
}
 
console.log(isBalanced("({[]})")); // Output: true
console.log(isBalanced("({[})")); // Output: false

4. Undo/Redo Functionality

The undo/redo functionality in text editors and graphic applications is often implemented using two stacks: one for undo operations and one for redo operations.

Simple Undo/Redo Implementation:

class TextEditor {
  constructor() {
    this.text = "";
    this.undoStack = new Stack();
    this.redoStack = new Stack();
  }
  
  // Add text and save previous state for undo
  addText(newText) {
    this.undoStack.push(this.text);
    this.text += newText;
    this.redoStack = new Stack(); // Clear redo stack on new action
  }
  
  // Undo the last action
  undo() {
    if (this.undoStack.isEmpty()) {
      return; // Nothing to undo
    }
    
    this.redoStack.push(this.text); // Save current state for redo
    this.text = this.undoStack.pop(); // Restore previous state
  }
  
  // Redo a previously undone action
  redo() {
    if (this.redoStack.isEmpty()) {
      return; // Nothing to redo
    }
    
    this.undoStack.push(this.text); // Save current state for undo
    this.text = this.redoStack.pop(); // Restore next state
  }
  
  // Get current text
  getText() {
    return this.text;
  }
}
 
// Example usage
const editor = new TextEditor();
editor.addText("Hello");
editor.addText(" World");
console.log(editor.getText()); // Output: "Hello World"
 
editor.undo();
console.log(editor.getText()); // Output: "Hello"
 
editor.redo();
console.log(editor.getText()); // Output: "Hello World"

5. Browser History

The back and forward buttons in web browsers use stacks to keep track of the browsing history. The back button pops from the history stack, while the forward button pops from a separate forward stack.

Simple Browser History Implementation:

class BrowserHistory {
  constructor(homepage) {
    this.backStack = new Stack();
    this.forwardStack = new Stack();
    this.currentPage = homepage;
  }
  
  // Navigate to a new page
  visit(url) {
    this.backStack.push(this.currentPage);
    this.currentPage = url;
    this.forwardStack = new Stack(); // Clear forward history
  }
  
  // Go back to the previous page
  back() {
    if (this.backStack.isEmpty()) {
      return false; // Can't go back
    }
    
    this.forwardStack.push(this.currentPage);
    this.currentPage = this.backStack.pop();
    return true;
  }
  
  // Go forward to the next page
  forward() {
    if (this.forwardStack.isEmpty()) {
      return false; // Can't go forward
    }
    
    this.backStack.push(this.currentPage);
    this.currentPage = this.forwardStack.pop();
    return true;
  }
  
  // Get current page
  getCurrentPage() {
    return this.currentPage;
  }
}
 
// Example usage
const browser = new BrowserHistory("https://www.example.com");
browser.visit("https://www.example.com/page1");
browser.visit("https://www.example.com/page2");
 
console.log(browser.getCurrentPage()); // Output: "https://www.example.com/page2"
 
browser.back();
console.log(browser.getCurrentPage()); // Output: "https://www.example.com/page1"
 
browser.forward();
console.log(browser.getCurrentPage()); // Output: "https://www.example.com/page2"
 
browser.visit("https://www.example.com/page3");
console.log(browser.getCurrentPage()); // Output: "https://www.example.com/page3"
 
// Can't go forward now (forward history was cleared)
console.log(browser.forward()); // Output: false

Other Common Applications

Stacks are used in many other applications, including:

Backtracking Algorithms: Used in maze solving, puzzle solutions, and game AI.
Memory Management: Used in memory allocation and deallocation.
Syntax Parsing: Compilers and interpreters use stacks for parsing expressions and syntax.
String Reversal: A simple application where each character is pushed onto a stack and then popped to reverse the string.
Depth-First Search: Graph traversal algorithms often use stacks to keep track of vertices to visit.

Check Your Understanding

Congratulations!

You've completed the Stack tutorial! You now understand:

What a stack is and the LIFO principle
How to implement the push operation to add elements
How to implement the pop operation to remove elements
How to implement the peek operation to view elements without removing them
Real-world applications of stacks

With this knowledge, you're well-equipped to use stacks in your own programs and understand how they're used in various algorithms and applications.