A Stack is one of the most fundamental data structures in computer science. It follows the LIFO (Last In, First Out) principle — the last element inserted is the first one to be removed.

Think of a stack of plates:
You place plates on top, and remove from the top.

---

🧠 What is a Stack?

A stack supports mainly four operations:

Simple and powerful — perfect for problems like
✔ undo-redo
✔ backtracking
✔ browser history
✔ valid parentheses
✔ next greater element

---

📌 Stack Implementation Using Array

This is the simplest and most commonly used approach in JavaScript.

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

    push(item) {
        this.stack.push(item);
    }

    pop() {
        if (this.isEmpty()) {
            return null;
        }
        return this.stack.pop();
    }

    peek() {
        if (this.isEmpty()) {
            return null;
        }
        return this.stack[this.stack.length - 1];
    }

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

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

const stack = new Stack();
stack.push(10);
stack.push(12);
stack.push(13);
stack.push(15);
stack.push(17);

stack.pop();
console.log(stack.peek());
console.log(stack);

✔ Output

15
Stack { stack: [ 10, 12, 13, 15 ] }

---

📌 Stack Implementation Using Linked List

A Linked List–based stack allows faster memory allocation and avoids array resizing.

Visualizing the Stack (Linked List)

(top)
  ↓
[14] → [12] → [10] → null

Implementation

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

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

    push(data) {
        const newNode = new Node(data);
        newNode.next = this.top;
        this.top = newNode;
        this.size++;
    }

    pop() {
        if (this.isEmpty()) {
            return "List is already empty";
        }
        const item = this.top.data;
        this.top = this.top.next;
        this.size--;
        return item;
    }

    peek() {
        return this.top?.data || null;
    }

    isEmpty() {
        return this.size === 0;
    }
}

const stack1 = new StackLinkedList();
stack1.push(10);
stack1.push(12);
stack1.push(14);

console.log(stack1.pop());
console.log(stack1.peek());
console.log(stack1);

✔ Output

14
12
StackLinkedList { top: Node { data: 12, next: Node { data: 10, next: null } }, size: 2 }

---

🆚 Array vs Linked List Stack

Both are good—use Array for simplicity and Linked List for flexibility.

---

🧩 Practice Stack Problems

Here are must-solve interview questions based on stacks:

1. Remove All Adjacent Duplicates in a String

2. Valid Parentheses

3. Backspace String Compare

4. Next Greater Element I

5. Online Stock Span

6. Next Greater Element II

7. Remove K Digits

8. Sum of Subarray Minimums

✅ 1. Remove All Adjacent Duplicates in String

Problem

Remove pairs of adjacent duplicate characters until no duplicates remain.

Stack Solution

var removeDuplicates = function(s) {
    const stack = [];

    for (let ch of s) {
        if (stack.length && stack[stack.length - 1] === ch) {
            stack.pop(); // remove duplicate
        } else {
            stack.push(ch);
        }
    }
    return stack.join('');
};

console.log(removeDuplicates("abbaca")); // "ca"

---

✅ 2. Valid Parentheses

Problem

Check if parentheses are correctly balanced.

Stack Solution

var isValid = function(s) {
    const stack = [];
    const map = {
        ')': '(',
        ']': '[',
        '}': '{'
    };

    for (let ch of s) {
        if (ch in map) {
            if (stack.pop() !== map[ch]) return false;
        } else {
            stack.push(ch);
        }
    }
    return stack.length === 0;
};

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

---

✅ 3. Backspace String Compare

Problem

# means backspace. Compare final strings.

Stack Solution

var build = function(s) {
    const stack = [];
    for (let ch of s) {
        if (ch === '#') stack.pop();
        else stack.push(ch);
    }
    return stack.join('');
};

var backspaceCompare = function(s, t) {
    return build(s) === build(t);
};

console.log(backspaceCompare("ab#c", "ad#c")); // true

---

✅ 4. Next Greater Element I

Problem

For each element in nums1, find next greater in nums2.

Stack + Map Solution

var nextGreaterElement = function(nums1, nums2) {
    const stack = [];
    const map = new Map();

    for (let num of nums2) {
        while (stack.length && num > stack[stack.length - 1]) {
            map.set(stack.pop(), num);
        }
        stack.push(num);
    }

    return nums1.map(n => map.get(n) || -1);
};

console.log(nextGreaterElement([4,1,2], [1,3,4,2])); // [-1,3,-1]

---

✅ 5. Online Stock Span

Problem

For each day's price, find how many consecutive previous days have price ≤ current.

Monotonic Stack Solution

var StockSpanner = function() {
    this.stack = []; // [price, span]
};

StockSpanner.prototype.next = function(price) {
    let span = 1;

    while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) {
        span += this.stack.pop()[1];
    }

    this.stack.push([price, span]);
    return span;
};

// Example
const ss = new StockSpanner();
console.log(ss.next(100)); 
console.log(ss.next(80));  
console.log(ss.next(60));
console.log(ss.next(70));
console.log(ss.next(60));
console.log(ss.next(75));
console.log(ss.next(85));

---

✅ 6. Next Greater Element II (Circular Array)

Problem

Return next greater element in circular array.

Stack + Mod Index Solution

var nextGreaterElements = function(nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const stack = [];

    for (let i = 0; i < 2 * n; i++) {
        let num = nums[i % n];

        while (stack.length && num > nums[stack[stack.length - 1]]) {
            res[stack.pop()] = num;
        }

        if (i < n) stack.push(i);
    }
    return res;
};

console.log(nextGreaterElements([1,2,1])); // [2, -1, 2]

---

✅ 7. Remove K Digits

Problem

Remove k digits to make smallest number.

Monotonic Stack Solution

var removeKdigits = function(num, k) {
    const stack = [];

    for (let digit of num) {
        while (k > 0 && stack.length && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }

    while (k > 0) {
        stack.pop();
        k--;
    }

    let result = stack.join('').replace(/^0+/, '');
    return result === '' ? '0' : result;
};

console.log(removeKdigits("1432219", 3)); // "1219"

---

✅ 8. Sum of Subarray Minimums

Problem

Sum of minimum element of every subarray.

Hard — uses Monotonic Stack for previous less + next less.

var sumSubarrayMins = function(arr) {
    const n = arr.length;
    const mod = 1e9 + 7;

    const prev = new Array(n).fill(-1);
    const next = new Array(n).fill(n);

    let stack = [];

    // previous less element
    for (let i = 0; i < n; i++) {
        while (stack.length && arr[stack[stack.length - 1]] > arr[i]) {
            stack.pop();
        }
        prev[i] = stack.length ? stack[stack.length - 1] : -1;
        stack.push(i);
    }

    stack = [];

    // next less or equal element
    for (let i = 0; i < n; i++) {
        while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
            next[stack.pop()] = i;
        }
        stack.push(i);
    }

    let result = 0;

    for (let i = 0; i < n; i++) {
        const left = i - prev[i];
        const right = next[i] - i;
        result = (result + arr[i] * left * right) % mod;
    }

    return result;
};

console.log(sumSubarrayMins([3,1,2,4])); // 17

---

🎯 Final Thoughts

Stacks are incredibly powerful. Once you understand push/pop/peek and the LIFO principle, solving many coding problems becomes easier.