Stack

Stack is a linear data structure in which the element inserted last is the element to be deleted first.

It is also called Last In First Out (LIFO).

In a stack, the last inserted element is at the top.

Operations:

• push() to insert an element into the stack

• pop() to remove an element from the stack

• top() Returns the top element of the stack.

• isEmpty() returns true if stack is empty else false.

• size() returns the size of stack.

Types:

• Fixed Size Stack: As the name suggests, a fixed size stack has a fixed size and cannot grow or shrink dynamically. If the stack is full and an attempt is made to add an element to it, an overflow error occurs. If the stack is empty and an attempt is made to remove an element from it, an underflow error occurs.

• Dynamic Size Stack: A dynamic size stack can grow or shrink dynamically. When the stack is full, it automatically increases its size to accommodate the new element, and when the stack is empty, it decreases its size. This type of stack is implemented using a linked list, as it allows for easy resizing of the stack.

Applications:

• Infix to Postfix /Prefix conversion

• Redo-undo features at many places like editors, photoshop.

• Forward and backward features in web browsers

• Used in many algorithms like Tower of Hanoi, tree traversals, stock span problems, and histogram problems.

• Backtracking is used to solve problems like the Knight-Tour problem, N-Queen problem, maze problems, and game-like chess or checkers in all these problems we dive into someway if that way is inefficient, we come back to the previous state and go into some another path. To get back from a current state we need to store the previous state in a stack.

• In Graph Algorithms like Topological Sorting and Strongly Connected Components

• In Memory management, any modern computer uses a stack as the primary management for a running purpose. Each program that is running in a computer system has its own memory allocations.

• Stack also helps in implementing function call in computers. The last called function is always completed first.

Implementation:

Using Arrays:

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

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

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

    peek() { return this.items[this.items.length - 1]; }

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

    size() { return this.items.length; }

    printStack() {
        let result = '';
        for (let i = this.items.length - 1; i >= 0; i--) {
            result += this.items[i] + '\n';
        }
        console.log(result);
    }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.printStack(); // Output: 30\n20\n10\n
console.log(stack.peek()); // Output: 30
console.log(stack.pop()); // Output: 30
stack.printStack(); // Output: 20\n10\n
console.log(stack.size()); // Output: 2
console.log(stack.isEmpty()); // Output: false

Using Linked Lists:

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

class Stack {
    constructor() {
        this.top = null;
        this.size = 0;
    }

    // Push an element onto the stack
    push(element) {
        const newNode = new Node(element);
        newNode.next = this.top;
        this.top = newNode;
        this.size++;
    }

    // Remove and return the top element of the stack
    pop() {
        if (this.isEmpty()) { return "Underflow"; }
        const poppedElement = this.top.data;
        this.top = this.top.next;
        this.size--;
        return poppedElement;
    }

    // Return the top element of the stack without removing it
    peek() {
        if (this.isEmpty()) { return "Stack is empty"; }
        return this.top.data;
    }

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

    size() { return this.size; }

    printStack() {
        let current = this.top;
        let result = '';
        while (current !== null) {
            result += current.data + '\n';
            current = current.next;
        }
        console.log(result);
    }
}

// Example usage:
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.printStack(); // Output: 30\n20\n10\n
console.log(stack.peek()); // Output: 30
console.log(stack.pop()); // Output: 30
stack.printStack(); // Output: 20\n10\n
console.log(stack.size()); // Output: 2
console.log(stack.isEmpty()); // Output: false

Stacks Good at 😀:

• Fast Operations

• Fast Peek

• Ordered

Stacks Bad at 😒:

• Slow Lookup