Algoritmos e estruturas de dados em PHP: do básico à implementação

Algoritmos e Estruturas de Dados em PHP: do básico à implementação

No desenvolvimento web moderno, o conhecimento de algoritmos e estruturas de dados não é apenas uma habilidade acadêmica, mas uma ferramenta prática para criar aplicações rápidas, escaláveis e confiáveis. O PHP, apesar de sua reputação de "linguagem para sites simples", fornece todos os recursos necessários para implementar tarefas computacionais complexas. Neste artigo, vamos abordar as principais estruturas de dados e algoritmos e, mais importante, mostrar como implementá-los em PHP puro com exemplos de código.

1. Estruturas de dados fundamentais em PHP

No PHP, os tipos embutidos (arrays, objetos) já cobrem muitas necessidades, mas para um entendimento profundo e otimização, vale a pena implementar as estruturas clássicas manualmente.

1.1. Pilha (Stack)

A pilha funciona pelo princípio LIFO (Last In, First Out). É usada para desfazer ações (undo), análise de parênteses, travessia de grafos em profundidade.

<?phpclass Stack {    private array $items = [];

    public function push($item): void {        array_push($this->items, $item);    }

    public function pop() {        if ($this->isEmpty()) {            throw new UnderflowException('Stack is empty');        }        return array_pop($this->items);    }

    public function peek() {        return end($this->items);    }

    public function isEmpty(): bool {        return empty($this->items);    }

    public function size(): int {        return count($this->items);    }}

// Exemplo: verificação de parênteses balanceadosfunction isBalanced(string $expression): bool {    $stack = new Stack();    $pairs = ['(' => ')', '{' => '}', '[' => ']'];

    for ($i = 0; $i < strlen($expression); $i++) {        $char = $expression[$i];        if (isset($pairs[$char])) {            $stack->push($char);        } elseif (in_array($char, $pairs)) {            if ($stack->isEmpty() || $pairs[$stack->pop()] !== $char) {                return false;            }        }    }    return $stack->isEmpty();}

echo isBalanced("({[]})") ? "Balanceado" : "Não balanceado"; // Balanceado?>

1.2. Fila (Queue)

A fila funciona pelo princípio FIFO (First In, First Out). É aplicada em sistemas de filas de tarefas, BFS (travessia em largura), bufferização de dados.

<?phpclass Queue {    private array $items = [];

    public function enqueue($item): void {        $this->items[] = $item;    }

    public function dequeue() {        if ($this->isEmpty()) {            throw new UnderflowException('Queue is empty');        }        return array_shift($this->items);    }

    public function peek() {        return $this->items[0] ?? null;    }

    public function isEmpty(): bool {        return empty($this->items);    }

    public function size(): int {        return count($this->items);    }}

// Exemplo: simulação de fila de impressão$printQueue = new Queue();$printQueue->enqueue("document1.pdf");$printQueue->enqueue("photo.jpg");$printQueue->enqueue("report.docx");

while (!$printQueue->isEmpty()) {    echo "Imprimindo: " . $printQueue->dequeue() . "";}?>

1.3. Árvore Binária de Busca (BST)

A árvore proporciona busca, inserção e remoção rápidas de elementos (O(log n) em média).

<?phpclass TreeNode {    public $value;    public ?TreeNode $left = null;    public ?TreeNode $right = null;

    public function __construct($value) {        $this->value = $value;    }}

class BinarySearchTree {    public ?TreeNode $root = null;

    public function insert($value): void {        $this->root = $this->insertNode($this->root, $value);    }

    private function insertNode(?TreeNode $node, $value): TreeNode {        if ($node === null)