A Stack is a linear data structure that follows the LIFO principle: the last element added to the stack is the first one to be removed. Think of it as a vertical container where you can only interact with the top item.

Think of a Stack of Plates in a cafeteria:

1. You can put a new plate on the very Top (Push).
2. You can take the Top plate off (Pop).
3. You can't take a plate from the middle without removing all the plates above it first.
4. The plate you put on last is the one you must use first.

---

Core Operations

• Push: Adds an item to the top. ($O(1)$)
• Pop: Removes the top item. ($O(1)$)
• Peek: Returns the top item without removing it. ($O(1)$)
• isEmpty: Returns true if the stack is empty. ($O(1)$)

Implementation

Stacks can be implemented using:

• Arrays: Fast and memory-efficient if the size is predictable.
• Linked Lists: Better for dynamic resizing, avoid the $O(n)$ cost of array resizing.

---

javascript Standard
/**
 * Simple Stack using an Array
 */
class Stack {
  constructor() {
    this.items = [];
  }

  // Add to top
  push(element) {
    this.items.push(element);
  }

  // Remove from top
  pop() {
    if (this.isEmpty()) return "Underflow";
    return this.items.pop();
  }

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

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

/**
 * Common Interview Task: Valid Parentheses
 * Check if "([])" is valid.
 */
function isValid(s) {
  const stack = [];
  const map = { ')': '(', '}': '{', ']': '[' };

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

---

Use Cases

• Function Calls: The CPU uses a "Call Stack" to manage function execution.
• Undo/Redo: Storing previous states.
• Expression Parsing: Converting Infix to Postfix (Reverse Polish Notation).
• Backtracking: Finding a path in a maze.

Must-Practice Problems

• Min Stack: Design a stack that returns the minimum element in $O(1)$ time.
• Evaluate Reverse Polish Notation.
• Simplify Path: (A classic Unix-style problem).
• Largest Rectangle in Histogram: (An advanced stack problem).