Conhecendo estruturas de dados: Stack

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!


Subscreva

Fique por dentro de tudo o que acontece no mundo Go.

Um comentário sobre “Conhecendo estruturas de dados: Stack

Deixe uma resposta