Stack ou pilha, é uma das estruturas de dados mais famosas e uma das mais confundidas também, afinal quem nunca falou… “Sei sim, ela é FIFO… não, LIFO… não, calma”
Uma das primeiras vezes que se viu falar sobre pilha na literatura foi em 1946, quando ninguém mais, ninguém menos que Alan M. Turing usou os termos “bury” e “unbury” como uma forma de chamar e retornar valores de sub-rotinas.
No entanto, embora ele descreve-se o processo, a ideia da criação da estrutura de dados com o nome que conhecemos hoje foi proposta somente em 1955 por Klaus Samelson e Friedrich L. Bauer da Universidade Técnica de Munique.
Uma pilha tem um tamanho definido e somente dois métodos, sendo um para adicionar item, normalmente chamado de push, e outro chamado pop para recuperar/remover.
Dentro da estrutura de dados, os itens são armazenados na ordem que foram adicionados. Caso haja uma tentativa de adição a uma pilha que está cheia, o famoso erro de Stack Overflow será retornado.
Quando recuperamos um item de uma pilha, o método sempre retornará o último item da lista de itens que temos internamente. Um ponto importante é que sempre que um item é retornado, ele também será removido da lista.
Uma maneira muito comum e fácil para explicação de como essa estrutura de dados funciona é compara-lá à uma pilha de pratos, onde o primeiro prato a entrar na pilha, será o último a sair (LIFO: Last In First Out).
A lista de itens armazenados na pilha pode ser implementada usando um array ou uma lista encadeada (linked list).
Como de costume, na próxima terça-feira soltaremos um novo vídeo no nosso canal do youtube mostrando como implementar uma pilha em Go com ZERO dependências externas.
Deixem suas dúvidas nos comentários.
Até a próxima!
[…] de ter falado sobre a estrutura de dados Stack (pilha) no último post da série, nada melhor do que dar continuidade a série falando de Queue (fila), […]