Tag: LIFO

Conhecendo estruturas de dados: Queue (fila)

Tiago Temporin1 comentário

Depois 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), sua famosa irmã e amiga nas confusões do.. “É FIFO ou é LIFO?”.

Queue ou fila, é uma estrutura de dados muito similar a Stack (pilha), o que acaba gerando confusão. A diferença básica entre elas é a ordem na qual seus itens são consumidos, pois ao contrário da Stack, a Queue sempre vai consumir os itens na ordem que foram inseridos.

AlgoritmoBig O
EspaçoO(n)
BuscaO(n)
InsertO(1)
DeleteO(1)
time complexity
Leia mais »

Conhecendo estruturas de dados: Stack

Tiago Temporin1 comentário

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.

Leia mais »