📚 PHP Stack & Queue Basics

PHP Stack Implementations

Array as Stack (Most Common)

$stack = [];

// Push
$stack[] = 10;
$stack[] = 20;
$stack[] = 30;

// Peek (without removing)
$top = end($stack); // 30

// Pop
$val = array_pop($stack); // 30

// Check empty
empty($stack); // false

SplStack

$stack = new SplStack();
$stack->push(10);
$stack->push(20);

$top = $stack->top();   // 20  (peek)
$val = $stack->pop();   // 20
echo $stack->count();   // 1
echo $stack->isEmpty(); // false

Note: PHP arrays (array_push/array_pop) are generally preferred — they're faster and more idiomatic.

---

PHP Queue Implementations

Array as Queue

$queue = [];

// Enqueue
array_push($queue, 'a');
array_push($queue, 'b');

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

// Dequeue (expensive — O(n) re-index)
$val = array_shift($queue); // 'a'

SplQueue (Preferred for Large Queues)

$queue = new SplQueue();
$queue->enqueue('a');
$queue->enqueue('b');

$front = $queue->bottom(); // 'a' (peek front)
$val   = $queue->dequeue(); // 'a'
echo $queue->count(); // 1

SplQueue is O(1) enqueue/dequeue — backed by a doubly linked list.

---

Deque (Double-Ended Queue)

// PHP array used as deque
$deque = [];

// Push front
array_unshift($deque, 1);  // expensive O(n)

// Push back
$deque[] = 2;              // O(1)

// Pop front
array_shift($deque);       // O(n) re-index

// Pop back
array_pop($deque);         // O(1)

// Use SplDoublyLinkedList for O(1) both ends
$dq = new SplDoublyLinkedList();
$dq->unshift(1);   // push front O(1)
$dq->push(2);      // push back  O(1)
$dq->shift();      // pop front  O(1)
$dq->pop();        // pop back   O(1)

---

Q1 — Valid Parentheses (Warm-Up)

🧠 How to Approach This

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

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

Step 3 — Optimal insight: Stack maintains the expected matching order.

Step 4 — Algorithm:

1. For each char: if open → push; if close → check stack top

2. Stack must be empty at end

Step 5 — Edge cases: Only closing brackets; mixed {[()]}.

function isValid(string $s): bool {
    $stack = [];
    $map   = [')' => '(', ']' => '[', '}' => '{'];
    foreach (str_split($s) as $ch) {
        if (in_array($ch, ['(', '[', '{'])) {
            $stack[] = $ch;
        } else {
            if (empty($stack) || end($stack) !== $map[$ch]) return false;
            array_pop($stack);
        }
    }
    return empty($stack);
}

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

---

Q2 — Min Stack

🧠 How to Approach This

Step 1 — Recognize the pattern: Alongside each value, track the current minimum so pop/push are still O(1).

Step 2 — Brute force (what NOT to do): Scan entire stack for min on each getMin call — O(n).

Step 3 — Optimal insight: Store [value, currentMin] pairs — constant lookup.

Step 4 — Algorithm:

1. push: store [$val, min($val, top min)]

2. pop/top/getMin: index into top pair

Step 5 — Edge cases: Single element; multiple elements with same value.

class MinStack {
    private array $stack = [];

    public function push(int $val): void {
        $min = empty($this->stack) ? $val : min($val, end($this->stack)[1]);
        $this->stack[] = [$val, $min];
    }

    public function pop(): void {
        array_pop($this->stack);
    }

    public function top(): int {
        return end($this->stack)[0];
    }

    public function getMin(): int {
        return end($this->stack)[1];
    }
}

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