080-stack-problem-8.md

Stack Problem 8

LeetCode: https://leetcode.com/problems/implement-queue-using-stacks/ Difficulty: Medium

Problem

Solve this stack problem efficiently.

Brute Force Approach

function solve(s) {
    // Multiple passes
    let prev = '';
    while (prev !== s) {
        prev = s;
        s = s.replace('()', '');
        s = s.replace('[]', '');
        s = s.replace('{}', '');
    }
    return s === '';
}

⏱️ Time: O(n²) or O(n³)
💾 Space: O(n)

Optimal Approach

function solve(s) {
    const stack = [];
    const pairs = { ')': '(', ']': '[', '}': '{' };
    
    for (const char of s) {
        if (char in pairs) {
            if (stack.length === 0 || stack.pop() !== pairs[char]) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    return stack.length === 0;
}

⏱️ Time: O(n) or O(n log n)
💾 Space: O(n) or O(1)

Visual Diagram

Stack (LIFO):
  ┌───┐
  │ 3 │ ← top
  ├───┤
  │ 2 │
  ├───┤
  │ 1 │
  └───┘

Push 4:    Pop:
  ┌───┐    ┌───┐
  │ 4 │    │ 2 │ ← new top
  ├───┤    ├───┤
  │ 3 │    │ 1 │
  ├───┤    └───┘
  │ 2 │
  ├───┤
  │ 1 │
  └───┘

---

Visit LeetCode for full problem description.