Introdução a estruturas de dados

Muitas vezes guardar os dados de um problema de uma certa maneira pode simplificar bastante o mesmo, tornando as operações que necessitamos de fazer nesse conjunto mais rápidas. Para isso, existem estruturas de dados que nos permitem guardar informação de modo a tornar certas operações mais eficientes. Três das mais simples de usar e perceber são listas ligadas, pilhas e filas.

Listas ligadas

Esta estrutura permite-nos guardar dados em sequência (como um array), com inserções e remoções em qualquer posição em $O(1)$. Em contrapartida, encontrar um elemento numa certa posição na lista torna-se O(N).

Como o artigo explica, esta estrutura consiste num conjunto de elementos que têm dois atributos, o seu valor e algo que indique o próximo elemento na sequência.

Guardar e percorrer

Para guardar a lista basta guardar o primeiro elemento, e para percorre-la começamos no primeiro e vamos andando, utilizando o atributo que nos indica o próximo elemento até este não existir. Para saber qual o elemento numa certa posição fazemos o mesmo que ao percorrer, mas paramos quando já percorremos o número desejado, sendo que isto é $O(N)$.

Inserção e remoção

Para inserir um elemento numa certa posição basta mudar o próximo elemento do anterior para o novo elemento e fazer com que o próximo elemento do novo seja o próximo elemento antigo do anterior. Sendo que apenas efetuamos duas operações (trocar o valor de duas variáveis), a complexidade total é $O(1)$, no entanto, se não tivermos o elemento previamente guardado temos de percorrer a lista em $O(N)$ para chegar a ele. Remover é semelhante e tem a mesma complexidade, basta colocar o próximo do elemento anterior ao que queremos remover como o próximo dele próprio.

Listas duplamente ligadas

Para melhorar a navegação, podemos guardar para cada elemento, além do próximo, o anterior. Isto permite-nos navegar a lista em ambos os sentidos, caso seja necessário. As operações ficam semelhantes, apenas temos de atualizar o elemento anterior a cada um de maneira equivalente ao próximo.

Pilhas

Uma pilha é um exemplo de uma estrutura que pode ser implementada com uma lista ligada, mas o seu comportamenteo obedece a certas regras. Veremos a seguir outra estrutura nas mesmas condições, uma fila.

Esta estrutura permite-nos guardar sequências tal como listas ligadas, mas segundo uma ordem LIFO (last in first out), que significa que o último elemento a ser inserido é o único que pode ser removido. Assim, podemos representá-la guardando o primeiro elemento apenas e, para cada elemento, guardar o próximo e o seu valor.

Inserção e Remoção

Para inserir um elemento na pilha (uma operação normalmente denominada de push), analogamente ao que fazíamos numa lista ligada, basta criar um elemento novo que aponte para o primeiro antigo e que tenha o novo valor e guardá-lo como o novo primeiro. A complexidade é $O(1)$, pois trata-se apenas de uma operação. Remover é semelhante, basta substituir o primeiro elemento pelo próximo elemento do próprio.

Aplicações

Para consolidarmos estes conceitos, eis um artigo para aplicarem uma pilha. Notem que o facto de dizermos que é suposto implementarem uma pilha é uma dica para te ajudar a resolvê-lo.

Filas

Esta estrutura é muito semelhante a uma pilha, mas em vez de seguir uma ordem LIFO, segue uma ordem FIFO (first in first out), que significa que o primeiro elemento a ser inserido é também o primeiro a ser removido. Ou seja, podemos apenas inserir no fim e remover do início.

Inserção e Remoção

Remover um elemento é literalmente igual a uma pilha. Para adicionar, temos de guardar além do primeiro, o último, e, de modo semelhante à pilha, criamos o elemento novo que passa a ser o último com o valor pretendido que tem como próximo o antigo último. Nestas operações temos de ter cuidado com o caso em que a fila está vazia por vezes.