Pilha: Estrutura de Dados em PHP Orientado a Objetos

As estruturas de dados são coleções de elementos onde podemos efetuar operações e interações. Especialmente em técnicas de Programação Orientada a Objetos, se faz uso massivo das estruturas como Pilhas, Filas, Listas ligadas, Árvores, Hash Tables e Grafos.  

O que é uma Pilha?

Uma Pilha ou Stack é uma estrutura de dados em que cada elemento novo que entra, vai ficando empilhado. Ou seja, cada novo elemento vai ficando no topo da estrutura de dados. 

Uma analogia que ajuda bastante na fixação deste conceito é comparar com uma “Pilha de Pratos”. Cada novo prato que for sendo adicionado, vai ficando no topo. Da mesma forma, quando vamos remover um prato da pilha, removemos do topo. Tecnicamente este comportamento padrão recebe o nome de LIFO (Last in First Out), o mesmo que: O último elemento a entrar é o primeiro a sair. 

Operações em Pilhas

Como você pode perceber, na teoria é bem simples o conceito. Vou fazer uma implementação na prática para te mostrar no código como tudo isso acontece. Para algumas linguagens de programação, que permite a Orientado a Objetos (POO) é muito mais comum essa manipulação com objetos. Vou implementar os exemplos em PHP para ajudar a galera que ainda está misturando procedural com POO de forma descontrolada. Saber separar os paradigmas é fundamental para uma melhor legibilidade do código e para garantir a manutenção do código.

As principais operações que podemos efetuar em uma Pilha são: 

• peek ou top: retorna o elemento no topo da pilha sem removê-lo;
• push: insere um novo elemento no topo da pilha;
• pop: remove o elemento do topo da pilha.
• isEmpty (opcional): verifica se a pilha está vazia;

Para completar este exemplo, vou criar uma classe para representar os nossos itens através de um Value Object genérico, só para exemplificar como os elementos vão ficar disponíveis em nossa Stack.

<?php

declare(strict_types=1);

namespace Growthdev\DataStructure\Stack;

final class ValueObject
{
    private string $value;

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

    public function getValue(): string
    {
        return $this->value;
    }
}

Vou definir uma interface para representar o contrato para que as coleções de dados possam ser especializadas. Ou seja, vamos definir os métodos obrigatórios para a classe que implementar esta interface.

<?php

declare(strict_types=1);

namespace Growthdev\DataStructure\Stack;

interface Collection
{
    public function peek(): ?ValueObject;
    
    public function push(ValueObject $item): void;

    public function pop(): ?ValueObject;
}

Precisamos de outro contrato, interface, para efetuarmos a contagem dos elementos da pilha:.

• count ou size: retorna o número de itens contidos na pilha.

<?php

declare(strict_types=1);

namespace Growthdev\DataStructure\Stack;

interface Countable
{
    public function count(): int;
}

Interações com Pilhas

Agora que já definimos as operações que podemos realizar em nossa estrutura de dados do tipo Pilha, temos que conseguir interagir com os seus valores de alguma forma. Me refiro interagir no sentido de percorrer e acessar os seus elementos/valores de forma dinâmica.

Os principais métodos de interações que vamos utilizar para percorrer nossa pilha são:

• hasNext: retorna um true se ainda existir elementos a serem percorridos;
• current: retorna o elemento atual da interação;
• next:  retorna controlar a posição dos elementos;
• rewind: é o resetador das posições dos elementos 

<?php

declare(strict_types=1);

namespace Growthdev\DataStructure\Stack;

interface Iterator
{
    public function hasNext(): bool;

    public function current(): ?ValueObject;

    public function next(): void;

    public function rewind(): void;
}

Ligação entre elementos da Pilha

Agora vamos criar uma estrutura para armazenar nossas coleções de dados e implementar os métodos definidos nos contratos das interfaces. Mas antes, preciso criar um objeto que irá dar dinâmica de ligação entre um elemento e outro da nossa pilha. Para isso, vamos criar um  Node.

Podemos considerar esta classe também como uma classe genérica, de modo que vamos passar um Value Object e fazermos um “auto referenciamento” para apontar para o próximo elemento(next) do nó da nossa estrutura de dados:

<?php

declare(strict_types=1);

namespace Growthdev\DataStructure\Stack;

final class Node
{
    private ?ValueObject $value;
    private ?Node $next;

    public function __construct(ValueObject $value, ?Node $next = null)
    {
        $this->value = $value;
        $this->next = $next;
    }

    public function getNext(): ?Node
    {
        return $this->next;
    }
    
    public function getValue(): ?ValueObject
    {
        return $this->value;
    }
}

Implementando os métodos e fazendo a ligação dos elementos, temos a seguinte lista linkada para representar nossa Pilha:

<?php

declare(strict_types=1);

namespace Growthdev\DataStructure\Stack;

class Stack implements Collection, Countable, Iterator
{
    private int $count = 0;
    private int $position = 0;
    private ?Node $node = null;
    private ?Node $lastNode = null;

    public function peek(): ?ValueObject
    {
        return $this->node->getValue();
    }

    public function push(ValueObject $value): void
    {
        $this->node = new Node($value, $this->node);
        $this->lastNode = $this->node;

        $this->count++;
    }

    public function pop(): ?ValueObject
    {
        if ($this->count === 0) {
            return null;
        }

        $node = $this->node;
        $this->node = $this->node->getNext();
        $this->count--;

        return $node->getValue();
    }

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

    public function hasNext(): bool
    {
        return $this->position < $this->count;
    }

    public function current(): ?ValueObject
    {
        return $this->node->getValue();
    }

    public function next(): void
    {
        $this->node = $this->node->getNext();
        $this->position++;
    }

    public function rewind(): void
    {
        $this->position = 0;
        $this->node = $this->lastNode;
        printf("\n 🔥 Rewind the Iterator to the first element...\n");
    }

    public function isEmpty(): bool
    {
        return $this->count === 0;
    }
}

Observe que temos uma composição entre a Stack e o Node. Ou seja, há uma dependência forte, mas neste caso foi proposital 🤫, uma vez que vamos precisar de um Node para fazer as ligações dos elementos para que a Stack atenda a sua finalidade. O Value Object, fiz bem específico com o valor tipo string, e também gerei uma relação de dependência forte, mas foi apenas para deixar este exemplo mais claro possível 😅.

Você encontrará todo o código-fonte no meu Github, onde poderá baixar e estudar livremente: https://github.com/growthdev-repo/data-structure

A classe de testes da Stack está cobrindo todas as principais operações e interações que esta classe se especializou.

<?php

declare(strict_types=1);

namespace Growthdev\DataStructure\Tests\Stack;

use Growthdev\DataStructure\Stack\Stack;
use Growthdev\DataStructure\Stack\ValueObject;
use PHPUnit\Framework\TestCase;

final class StackTest extends TestCase
{
    public function testCanBePeek(): void
    {
        $stack = new Stack();
        $stack->push(new ValueObject('Fist Item'));
        $stack->push(new ValueObject('Second Item'));
        $stack->push(new ValueObject('Last Item (top item)'));

        $this->assertEquals('Last Item (top item)', $stack->peek()->getValue());
    }

    public function testCanBePush(): void
    {
        $stack = new Stack();
        $stack->push(new ValueObject('Walmir'));
        $stack->push(new ValueObject('Silva'));
        $stack->push(new ValueObject('Growth'));
        $stack->push(new ValueObject('Dev'));
        $stack->push(new ValueObject('Example'));
        $stack->push(new ValueObject('Stack'));

        $this->assertEquals(6, $stack->count());
    }

    public function testCanBePop(): void
    {
        $stack = new Stack();
        $stack->push(new ValueObject('Fist Item'));
        $stack->push(new ValueObject('Second Item'));
        $stack->push(new ValueObject('Last Item (top item)'));

        $this->assertEquals('Last Item (top item)', $stack->pop()->getValue());
        $this->assertEquals(2, $stack->count());
    }

    public function testIfIsEmpty(): void
    {
        $stack = new Stack();
        $this->assertTrue($stack->isEmpty());
    }

    public function testCanBeIterated(): void
    {
        $stack = new Stack();
        $stack->push(new ValueObject('Fist Item'));
        $stack->push(new ValueObject('Second Item'));
        $stack->push(new ValueObject('Third Item'));
        $stack->push(new ValueObject('Last Item (top item)'));
    
        $this->assertEquals(4, $stack->count());
        $this->assertEquals('Last Item (top item)', $stack->pop()->getValue());
        $this->assertEquals('Third Item', $stack->pop()->getValue());
        $this->assertEquals('Second Item', $stack->pop()->getValue());
        $this->assertEquals('Fist Item', $stack->pop()->getValue());
        $this->assertEquals(0, $stack->count());
    }

    public function testCanBeIteratedWithLoop(): void
    {
        $stack = new Stack();
        $stack->push(new ValueObject('1º Item'));
        $stack->push(new ValueObject('2º Item'));
        $stack->push(new ValueObject('3º Item'));
        $stack->push(new ValueObject('4º Item (top item)'));

        $stack->rewind();

        while ($stack->hasNext()) {
            $currentValue = $stack->current()->getValue();
            printf("\t%s\n", $currentValue);
            
            $this->assertNotEmpty($currentValue);
            $stack->next();
        }

        $stack->rewind();
        while ($stack->hasNext()) {
            $currentValue = $stack->current()->getValue();
            printf("\t%s\n", $currentValue);
            
            $this->assertNotEmpty($currentValue);
            $stack->next();
        }
    }
}

Ao executar os testes, você notará claramente que o comportamento de LIFO da nossa Stack está funcionando perfeitamente, bem como os métodos de operações e interações:

Este exemplo, vai te ajudar a entender como pensar orientado a objetos e como estruturar seu pensamento na prática. O PHP tem um recurso super interessante que poucos programadores conhecem, Standard PHP Library (SPL). Nesta biblioteca, você encontra uma coleção completa de classes para manipulação de Estruturas de Dados. Em artigo futuro, vou explicar o uso das principais estruturas desta biblioteca!

E aí? Você já trabalha com PHP Orientado a Objetos? Utiliza Estruturas de Dados nos seus projetos? Se sim, compartilhe aqui em um comentário sua experiência. Isso ajuda bastante a comunidade! Até o próximo artigo!

Confiança Sempre!!!