🔧 PHP Stack & Queue Patterns

Pattern 1 — Monotonic Stack (Next Greater Element)

A monotonic stack maintains elements in strictly increasing or decreasing order. Pop whenever the invariant is violated — that's the answer moment.

🧠 How to Approach This

Step 1 — Recognize the pattern: "Next greater / smaller element" questions. Keywords: daily temperatures, next warmer day, stock span.

Step 2 — Brute force (what NOT to do): For each element scan right for next greater — O(n²).

Step 3 — Optimal insight: Monotonic decreasing stack. When a larger element arrives, it's the "next greater" for everything it pops.

Step 4 — Algorithm:

1. Stack stores indices of unresolved elements

2. For each i: while stack not empty and arr[stack.top] < arr[i] → answer[pop] = arr[i]

3. Push i

Step 5 — Edge cases: Elements with no greater successor → remain in stack (answer stays -1).

function nextGreaterElement(array $nums): array {
    $n      = count($nums);
    $result = array_fill(0, $n, -1);
    $stack  = []; // indices

    for ($i = 0; $i < $n; $i++) {
        while (!empty($stack) && $nums[end($stack)] < $nums[$i]) {
            $result[array_pop($stack)] = $nums[$i];
        }
        $stack[] = $i;
    }
    return $result;
}
// [2,1,3,4] → [3,3,4,-1]

Time: O(n) — each element pushed/popped once | Space: O(n)

---

Pattern 2 — Monotonic Stack (Daily Temperatures)

Same pattern but answer = distance, not value.

🧠 How to Approach This

Step 1 — Recognize the pattern: "How many days until a warmer temperature?"

Step 2 — Brute force (what NOT to do): Nested loops — O(n²).

Step 3 — Optimal insight: Monotonic decreasing stack of indices. When warmer temp found, answer = i - popped_index.

Step 4 — Algorithm:

1. Stack of indices

2. For each i: while top's temp < current temp → result[pop] = i - pop

3. Push i

Step 5 — Edge cases: Last element — never warmer → 0.

function dailyTemperatures(array $temps): array {
    $n      = count($temps);
    $result = array_fill(0, $n, 0);
    $stack  = [];

    for ($i = 0; $i < $n; $i++) {
        while (!empty($stack) && $temps[end($stack)] < $temps[$i]) {
            $idx          = array_pop($stack);
            $result[$idx] = $i - $idx;
        }
        $stack[] = $i;
    }
    return $result;
}

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

---

Pattern 3 — Sliding Window Maximum (Deque / Monotonic Queue)

🧠 How to Approach This

Step 1 — Recognize the pattern: "Maximum in sliding window of size k" — window moves right.

Step 2 — Brute force (what NOT to do): Scan k elements for each window — O(n·k).

Step 3 — Optimal insight: Monotonic decreasing deque of indices. Front always holds current window's max index.

Step 4 — Algorithm:

1. For each i: remove indices outside window from front

2. Remove smaller elements from back (they can never be max)

3. Append result when window is full (i >= k-1)

Step 5 — Edge cases: k > n; k = 1.

function maxSlidingWindow(array $nums, int $k): array {
    $n      = count($nums);
    $result = [];
    $deque  = []; // indices, monotonic decreasing

    for ($i = 0; $i < $n; $i++) {
        // Remove out-of-window index from front
        while (!empty($deque) && $deque[0] < $i - $k + 1) {
            array_shift($deque);
        }
        // Remove smaller elements from back
        while (!empty($deque) && $nums[end($deque)] < $nums[$i]) {
            array_pop($deque);
        }
        $deque[] = $i;
        if ($i >= $k - 1) $result[] = $nums[$deque[0]];
    }
    return $result;
}

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

---

Pattern 4 — Implement Queue Using Two Stacks

🧠 How to Approach This

Step 1 — Recognize the pattern: Two LIFO structures simulate one FIFO.

Step 2 — Brute force (what NOT to do): Single stack + reverse on every dequeue — expensive.

Step 3 — Optimal insight: Lazy transfer — move all elements to outStack only when outStack is empty.

Step 4 — Algorithm:

1. Push always goes to inStack

2. Pop/peek: if outStack empty, drain inStack into outStack first

Step 5 — Edge cases: Mixed push/pop operations, amortized O(1).

class MyQueue {
    private array $inStack  = [];
    private array $outStack = [];

    public function push(int $x): void {
        $this->inStack[] = $x;
    }

    public function pop(): int {
        $this->transfer();
        return array_pop($this->outStack);
    }

    public function peek(): int {
        $this->transfer();
        return end($this->outStack);
    }

    public function empty(): bool {
        return empty($this->inStack) && empty($this->outStack);
    }

    private function transfer(): void {
        if (empty($this->outStack)) {
            while (!empty($this->inStack)) {
                $this->outStack[] = array_pop($this->inStack);
            }
        }
    }
}

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

---

Pattern 5 — Largest Rectangle in Histogram

🧠 How to Approach This

Step 1 — Recognize the pattern: For each bar, find how far left and right it can extend at its height.

Step 2 — Brute force (what NOT to do): For each pair of bars compute area — O(n²).

Step 3 — Optimal insight: Monotonic increasing stack. Pop when a shorter bar arrives — the popped bar defines a rectangle bounded by the shorter bar and the new stack top.

Step 4 — Algorithm:

1. Append sentinel 0 to heights

2. Monotonic increasing stack of indices

3. On pop: width = i - stack_top - 1; area = height * width

Step 5 — Edge cases: Sentinel at end forces all remaining bars to be processed.

function largestRectangleArea(array $heights): int {
    $heights[] = 0; // sentinel
    $stack     = [-1];
    $maxArea   = 0;

    foreach ($heights as $i => $h) {
        while (count($stack) > 1 && $heights[end($stack)] > $h) {
            $height  = $heights[array_pop($stack)];
            $width   = $i - end($stack) - 1;
            $maxArea = max($maxArea, $height * $width);
        }
        $stack[] = $i;
    }
    return $maxArea;
}

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