Stack Applications: Exploring Key Use Cases in Programming

4.1.3 Stack Applications

Stacks are a fundamental data structure in computer science, known for their Last-In-First-Out (LIFO) property. This characteristic makes them particularly useful in a variety of applications, from managing function calls to enabling complex algorithms like backtracking. In this section, we will delve into the diverse applications of stacks, providing practical examples and insights into their implementation in JavaScript.

Key Learning Objectives

• Identify common applications of stacks in programming.
• Understand how stacks are used in function call management (call stacks).
• Explore practical examples where stacks are essential.

Understanding Stacks in Function Call Management

One of the most critical applications of stacks is in managing function calls and recursion in programming languages. The call stack is a stack data structure that stores information about the active subroutines or functions in a program. When a function is called, its execution context is pushed onto the stack. Once the function completes, its context is popped from the stack, and control returns to the calling function.

Function Call Management

In JavaScript, the call stack is integral to the execution of functions. Consider the following example:

function greet() {
    console.log("Hello");
    askName();
}

function askName() {
    console.log("What is your name?");
    sayGoodbye();
}

function sayGoodbye() {
    console.log("Goodbye");
}

greet();

When greet() is invoked, the call stack manages the sequence of function calls as follows:

1. greet() is called and pushed onto the stack.
2. askName() is called within greet() and pushed onto the stack.
3. sayGoodbye() is called within askName() and pushed onto the stack.
4. sayGoodbye() completes and is popped from the stack.
5. askName() completes and is popped from the stack.
6. greet() completes and is popped from the stack.

This stack-based management ensures that each function has its own execution context, preserving the state of local variables and the sequence of execution.

Recursion and the Call Stack

Recursion is a programming technique where a function calls itself. The call stack plays a crucial role in managing recursive calls, ensuring that each recursive invocation has its own execution context. However, excessive recursion can lead to stack overflow, a condition where the stack exceeds its limit due to too many nested calls.

Consider the classic example of calculating the factorial of a number using recursion:

function factorial(n) {
    if (n === 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

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

In this example, each call to factorial() pushes a new execution context onto the stack until the base case (n === 0) is reached. The stack then unwinds, returning the calculated result.

Expression Evaluation and Parsing

Stacks are also essential in expression evaluation and parsing, particularly in converting infix expressions (common mathematical notation) to postfix expressions (Reverse Polish Notation). This conversion is crucial for evaluating expressions without the need for parentheses to dictate precedence.

Converting Infix to Postfix

To convert an infix expression to postfix, we can use the Shunting Yard algorithm, which utilizes a stack to manage operators and ensure correct precedence. Here’s a simplified example:

function infixToPostfix(expression) {
    const precedence = { '+': 1, '-': 1, '*': 2, '/': 2 };
    const stack = [];
    let postfix = '';

    for (let char of expression) {
        if (!isNaN(char)) {
            postfix += char;
        } else if (char in precedence) {
            while (stack.length && precedence[stack[stack.length - 1]] >= precedence[char]) {
                postfix += stack.pop();
            }
            stack.push(char);
        }
    }

    while (stack.length) {
        postfix += stack.pop();
    }

    return postfix;
}

console.log(infixToPostfix("3+4*2")); // Output: 342*+

In this example, the stack is used to temporarily hold operators, ensuring that operators with higher precedence are applied before those with lower precedence.

Evaluating Postfix Expressions

Once an expression is in postfix form, it can be evaluated using a stack. Operands are pushed onto the stack, and operators pop operands from the stack, perform the operation, and push the result back onto the stack.

function evaluatePostfix(expression) {
    const stack = [];

    for (let char of expression) {
        if (!isNaN(char)) {
            stack.push(Number(char));
        } else {
            const b = stack.pop();
            const a = stack.pop();
            switch (char) {
                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("342*+")); // Output: 11

Practical Applications of Stacks

Beyond function call management and expression evaluation, stacks have a wide range of practical applications in software development.

Reversing a String

A stack can be used to reverse a string by pushing each character onto the stack and then popping them off in reverse order.

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

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

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

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

function reverseString(str) {
    let stack = new Stack();
    for (let char of str) {
        stack.push(char);
    }
    let reversed = '';
    while (!stack.isEmpty()) {
        reversed += stack.pop();
    }
    return reversed;
}

console.log(reverseString("hello")); // Output: "olleh"

Undo Mechanisms in Text Editors

Stacks are integral to implementing undo functionality in text editors. Each action performed by the user is pushed onto a stack. When the user triggers an undo, the last action is popped from the stack and reversed.

class TextEditor {
    constructor() {
        this.content = '';
        this.undoStack = [];
    }

    type(text) {
        this.undoStack.push(this.content);
        this.content += text;
    }

    undo() {
        if (this.undoStack.length) {
            this.content = this.undoStack.pop();
        }
    }

    getContent() {
        return this.content;
    }
}

const editor = new TextEditor();
editor.type("Hello");
editor.type(" World");
console.log(editor.getContent()); // Output: "Hello World"
editor.undo();
console.log(editor.getContent()); // Output: "Hello"

Backtracking Algorithms

Backtracking algorithms, such as solving mazes or puzzles, often rely on stacks to explore potential solutions and backtrack when a dead end is reached.

function solveMaze(maze, start, end) {
    const stack = [start];
    const visited = new Set();

    while (stack.length) {
        const [x, y] = stack.pop();
        if (x === end[0] && y === end[1]) {
            return true;
        }
        visited.add(`${x},${y}`);

        for (const [dx, dy] of [[0, 1], [1, 0], [0, -1], [-1, 0]]) {
            const [nx, ny] = [x + dx, y + dy];
            if (maze[nx] && maze[nx][ny] === 0 && !visited.has(`${nx},${ny}`)) {
                stack.push([nx, ny]);
            }
        }
    }

    return false;
}

const maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
];

console.log(solveMaze(maze, [0, 0], [4, 4])); // Output: true

Browser History Navigation

Web browsers use stacks to manage the history of visited pages. The back button pops the current page from the stack, while the forward button pushes it back onto the stack.

class BrowserHistory {
    constructor() {
        this.backStack = [];
        this.forwardStack = [];
        this.currentPage = null;
    }

    visit(page) {
        if (this.currentPage) {
            this.backStack.push(this.currentPage);
        }
        this.currentPage = page;
        this.forwardStack = [];
    }

    back() {
        if (this.backStack.length) {
            this.forwardStack.push(this.currentPage);
            this.currentPage = this.backStack.pop();
        }
    }

    forward() {
        if (this.forwardStack.length) {
            this.backStack.push(this.currentPage);
            this.currentPage = this.forwardStack.pop();
        }
    }

    getCurrentPage() {
        return this.currentPage;
    }
}

const history = new BrowserHistory();
history.visit("Page 1");
history.visit("Page 2");
history.back();
console.log(history.getCurrentPage()); // Output: "Page 1"
history.forward();
console.log(history.getCurrentPage()); // Output: "Page 2"

Visualizing Stack Applications

To better understand stack applications, let’s visualize some of these scenarios using flowcharts and diagrams.

Call Stack Management

    graph TD;
	    A[Start] --> B[Call greet()];
	    B --> C[Call askName()];
	    C --> D[Call sayGoodbye()];
	    D --> E[Return from sayGoodbye()];
	    E --> F[Return from askName()];
	    F --> G[Return from greet()];
	    G --> H[End];

Expression Evaluation

    graph TD;
	    A[Start] --> B[Read Next Token];
	    B --> C{Is Operand?};
	    C -- Yes --> D[Push to Stack];
	    C -- No --> E{Is Operator?};
	    E -- Yes --> F[Pop Operands];
	    F --> G[Evaluate];
	    G --> H[Push Result];
	    H --> B;
	    E -- No --> I[End];

Encouraging Further Exploration

Stacks are a versatile data structure with numerous applications beyond those discussed here. To deepen your understanding, consider exploring additional use cases such as:

• Implementing a stack-based calculator.
• Using stacks in graph algorithms like depth-first search.
• Building a syntax checker for programming languages.

By implementing these and other stack-based solutions, you can gain a deeper appreciation for the power and flexibility of stacks in software development.

Quiz Time!