# 🚀 Stack in JavaScript — Complete Guide with Array & Linked List Implementation

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**:

| Operation | Description |
| --- | --- |
| `push()` | Add an element to the top |
| `pop()` | Remove the top element |
| `peek()` | View top element without removing |
| `isEmpty()` | Check if stack is empty |

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.

```apache
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

```apache
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)

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

### Implementation

```apache
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

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

---

# 🆚 Array vs Linked List Stack

| Feature | Array Stack | Linked List Stack |
| --- | --- | --- |
| Speed | Fast (O(1)) | Fast (O(1)) |
| Memory | Contiguous | Dynamic |
| Overflow | Possible | No |
| Implementation | Simpler | Slightly harder |

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

```apache
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

```apache
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

```apache
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

```apache
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

```apache
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

```apache
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

```apache
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.

```apache
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.