Implementando uma Queue (fila)

Dando continuidade nas nossas implementações de estruturas de dados, nesse post vamos mostrar como implementar uma Fila (post teórico) sem qualquer dependência externa.

Deixem suas dúvidas nos comentários.

Até a próxima!


Subscreva

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

Conhecendo estruturas de dados: Queue (fila)

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

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 »

Conhecendo estruturas de dados: Linked List

Continuando os posts sobre estruturas de dados, hoje vamos falar sobre linked list ou listas encadeadas.

AlgoritmoBig O
IndexarO(n)
Inserir/deletar no inicioO(1)
Inserir/deletar no meioO(n)
Inserir/deletar no finalO(1)
BuscaO(n)
Big O de uma linked list

Essa estrutura de dados foi inventada em 1955-1956 por Allen Newel, Cliff Shaw e Herbert A. Simon como sua principal estrutura de dados em sua linguagem de programação chamada de Information Processing Language (IPL). IPL foi usada pelos autores para desenvolver diversos programas de inteligência artificial, incluindo Logic Theory Machine, General Problem Solver e um programa de xadrez.

Leia mais »

Conhecendo estruturas de dados: Hash table/hash map

Hoje vamos iniciar uma nova série de posts aqui no blog onde vamos conhecer como algumas estruturas de dados funcionam, e para começar, vamos falar da hash table ou hash map.

AlgoritmoMédiaPior cenário
EspaçoO(n)O(n)
BuscaO(1)O(n)
InserçãoO(1)O(n)
ExclusãoO(1)O(n)
hash table big O

Essa estrutura de dados foi inventada em 1953 e consiste basicamente em uma tabela do tipo key/value. Para calcular a key de um determinado registro usamos uma função chamada de hash function ou hash code.

Idealmente essa função irá gerar uma única key para cada objeto que vamos tentar armazenar nessa estrutura de dados.

Leia mais »