📚 JavaScript Stack & Queue Basics

Stack (LIFO) with Array

const stack = [];

// Push
stack.push(10);
stack.push(20);
stack.push(30);

// Peek (without removing) — modern JS
const top = stack.at(-1);    // 30
// or: stack[stack.length - 1]

// Pop
const val = stack.pop();     // 30

// Check empty
stack.length === 0;          // false

---

Queue (FIFO) with Array

const queue = [];

// Enqueue
queue.push('a');
queue.push('b');

// Peek
const front = queue[0];      // 'a'

// Dequeue — O(n) re-index (acceptable in interviews)
const val = queue.shift();   // 'a'

Performance note: Array.shift() is O(n) in JavaScript. For performance-critical code, use a two-pointer approach or a dedicated queue class.

---

O(1) Queue with Two Pointers

class Queue {
  constructor() { this.data = []; this.head = 0; }
  enqueue(x)  { this.data.push(x); }
  dequeue()   { return this.data[this.head++]; }
  peek()      { return this.data[this.head]; }
  isEmpty()   { return this.head >= this.data.length; }
  size()      { return this.data.length - this.head; }
}

This avoids re-indexing at the cost of memory not being reclaimed.

---

Deque (Double-Ended Queue)

// Interview-safe: regular array with pop/push/shift/unshift
// (shift/unshift are O(n) but acceptable)

const deque = [];
deque.push(1);       // back O(1)
deque.unshift(0);    // front O(n) — only use when needed
deque.pop();         // back O(1)
deque.shift();       // front O(n)

---

Q1 — Valid Parentheses (Warm-Up)

🧠 How to Approach This

Step 1 — Recognize the pattern: Opening bracket → push; closing → must match stack top.

Step 2 — Brute force (what NOT to do): Count opens vs closes — fails for "([)]".

Step 3 — Optimal insight: Stack enforces LIFO matching order.

Step 4 — Algorithm:

1. Map closing → expected opening

2. Push opens; on close: top must match, else false

3. Stack must be empty at end

Step 5 — Edge cases: Only closings; {[()]}.

function isValid(s) {
  const stack = [];
  const map = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if ('([{'.includes(ch)) {
      stack.push(ch);
    } else {
      if (!stack.length || stack.at(-1) !== map[ch]) return false;
      stack.pop();
    }
  }
  return stack.length === 0;
}

Time: O(n) | Space: O(n)

---

Q2 — Min Stack

🧠 How to Approach This

Step 1 — Recognize the pattern: Track running minimum with each pushed value.

Step 2 — Brute force (what NOT to do): Scan stack on getMin — O(n).

Step 3 — Optimal insight: Store [val, currentMin] pairs — O(1) all ops.

Step 4 — Algorithm:

1. Push: append [val, Math.min(val, top_min)]

2. Pop/top/getMin: index top pair

Step 5 — Edge cases: First push; duplicate min values.

class MinStack {
  constructor() { this.stack = []; }
  push(val) {
    const min = this.stack.length ? Math.min(val, this.stack.at(-1)[1]) : val;
    this.stack.push([val, min]);
  }
  pop()    { this.stack.pop(); }
  top()    { return this.stack.at(-1)[0]; }
  getMin() { return this.stack.at(-1)[1]; }
}

Time: O(1) all ops | Space: O(n)