Understanding Stacks in Programming

January 09, 2025 | Data Structures

Stacks are one of the fundamental data structures in computer science. They operate on a Last In, First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed.

How Stacks Work

A stack has two primary operations:

• Push: Add an element to the top of the stack.
• Pop: Remove the top element from the stack.

Additional operations often include:

• Peek/Top: View the top element without removing it.
• isEmpty: Check if the stack is empty.
• Size: Get the number of elements in the stack.

Real-World Analogies

Stacks can be visualized with a stack of plates:

1. The last plate placed on top is the first one to be removed.
2. You can only interact with the top plate.

Use Cases of Stacks

• Expression Evaluation: Used in parsing and evaluating mathematical expressions.
• Undo/Redo Functionality: Many applications use stacks to track actions for undo/redo functionality.
• Backtracking: For example, navigating through browser history.
• DFS Algorithms: Depth-first search in graph traversal.

Implementing a Stack in JavaScript

Here is a simple implementation of a stack using a class:

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

    // Add an element to the stack
    push(element) {
        this.items.push(element);
    }

    // Remove and return the top element
    pop() {
        if (this.isEmpty()) {
            throw new Error("Stack is empty");
        }
        return this.items.pop();
    }

    // View the top element
    peek() {
        if (this.isEmpty()) {
            throw new Error("Stack is empty");
        }
        return this.items[this.items.length - 1];
    }

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

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

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

// Example Usage
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // Output: 20
console.log(stack.pop()); // Output: 20
console.log(stack.isEmpty()); // Output: false

Built-In JavaScript Alternatives

JavaScript arrays can also function as stacks since they provide push and pop methods:

const stack = [];
stack.push(10);
stack.push(20);
console.log(stack[stack.length - 1]); // Peek: Output 20
console.log(stack.pop()); // Pop: Output 20
console.log(stack.length === 0); // isEmpty: Output false

Time Complexity

• Push: O(1)
• Pop: O(1)
• Peek: O(1)

Visualizing Stack Operations

Initial Stack: []

Push(5): [5]
Push(10): [5, 10]
Peek(): [5, 10] (Top: 10)
Pop(): [5] (Removed: 10)
IsEmpty(): false

Advanced Stack Applications

1. Balanced Parentheses:

function isBalanced(expression) {
    const stack = [];
    const pairs = { ')': '(', '}': '{', ']': '[' };

    for (const char of expression) {
        if (['(', '{', '['].includes(char)) {
            stack.push(char);
        } else if ([')', '}', ']'].includes(char)) {
            if (stack.pop() !== pairs[char]) {
                return false;
            }
        }
    }

    return stack.length === 0;
}

console.log(isBalanced("{[()]}")); // Output: true
console.log(isBalanced("{[(])}")); // Output: false

2. Depth-First Search:

function dfs(graph, start) {
    const stack = [start];
    const visited = new Set();

    while (stack.length > 0) {
        const node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node);

            for (const neighbor of graph[node]) {
                stack.push(neighbor);
            }
        }
    }
}

const graph = {
    A: ['B', 'C'],
    B: ['D', 'E'],
    C: ['F'],
    D: [],
    E: ['F'],
    F: []
};

dfs(graph, 'A');
// Output: A, C, F, B, E, D (order may vary)