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!
Categoria: estruturas de dados
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.
| Algoritmo | Big O |
|---|---|
| Espaço | O(n) |
| Busca | O(n) |
| Insert | O(1) |
| Delete | O(1) |
Implementando uma Stack (pilha)
Como de costume, hoje vamos implementar, sem utilizar nenhuma dependência externa, a estrutura de dados que conhecemos na semana passada, a stack(pilha) (link do post).
Deixem suas dúvidas nos comentários.
Até a próxima!
Se inscreva na nossa newsletter
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 »
Implementando uma Linked List
Na semana passada falamos sobre mais uma estrutura de dados, a linked list ou lista encadeada (link do post).
Com todo aquele conceito em mente, hoje vamos implementar essa estrutura de dados em Go sem usar nenhum package de terceiros.
Deixem suas dúvidas nos comentários.
Até a próxima!
Se inscreva na nossa newsletter
Conhecendo estruturas de dados: Linked List
Continuando os posts sobre estruturas de dados, hoje vamos falar sobre linked list ou listas encadeadas.
| Algoritmo | Big O |
|---|---|
| Indexar | O(n) |
| Inserir/deletar no inicio | O(1) |
| Inserir/deletar no meio | O(n) |
| Inserir/deletar no final | O(1) |
| Busca | O(n) |
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 »
Implementando uma Hash Table
Fala galera, tudo certo?
Na semana passada publicamos um post sobre como funciona uma hash table (link do post). Hoje vamos ver como implementar ela usando zero dependências.
Deixem suas dúvidas nos comentários.
Até a próxima!
Se inscreva na nossa newsletter
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.
| Algoritmo | Média | Pior cenário |
|---|---|---|
| Espaço | O(n) | O(n) |
| Busca | O(1) | O(n) |
| Inserção | O(1) | O(n) |
| Exclusão | O(1) | O(n) |
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 »