Estrutura de dados dinâmicas em C - Listas, Filas, Pilhas e Árvores

Através desse artigo de nossa apostila de C, iniciamos um dos mais importantes estudos em linguagem C, onde iremos aprender os conceitos de Listas, Filas, Pilhas e Árvores.

São elementos das estruturas dinâmicas de dados e são essenciais na linguagem C e no estudo da computação, de um modo geral.
Aprendendo estrutura de dados dinâmica, iremos nos aproximar do conhecimento que é realmente empregado nos mais diversos aplicativos e sistemas existentes.

• Obter certificado de programação C
• Leia este tutorial no seu computador ou celular: Apostila C Progressivo

O que é Estrutura Dinâmica de Dados em Linguagem C

Aqui em nossa apostila de C, já estudamos estrutura de dados quando aprendemos sobre vetores, que foi uma maneira de manipular várias informações (variáveis ou estruturas) de uma vez só, pois poderíamos declarar vários desses elementos.
Quando isso era feito, esses dados estavam em uma sequência rigidamente definida na memória, bem como o número de elementos eram constantes. Esses dois detalhes, na verdade, possuem algumas limitações.

Ou seja, estamos um trecho do título deste tutorial, a parte de "Estrutura de Dados".
Também estudamos a outra parte, que se refere ao dinamismo. Vimos isso em nossa seção de Alocação dinâmica de memória, onde deixamos de estar presos ao conceito de "número de elementos fixos", pois lá alocávamos e realocávamos o tanto de espaços de memória que queríamos, da maneira que queríamos.

Pois bem, agora é hora de 'unir forças' e usar esses poderosos conceitos para criar outro importante conceito, o de estrutura de dados dinâmicas, ou seja, as estrutura de dados que são alocadas, realocadas e movidas o quanto e do jeito que quisermos.

Ou seja, ao contrário de vetores de tamanhos fixos, iremos basicamente colocar estruturas(structs) em uma sequência que será criada dinamicamente, da maneira que quisermos. Ou seja, podemos colocar elementos nessa sequência, tirar, mudar de lugar, percorrer e fazer coisas incríveis.

Mas só falando dessa maneira, a coisa fica um pouco confusa e abstrata.
Vamos entrar em detalhes nos tipos de estrutura de dados que iremos estudar: Listas, Filas, Pilhas e Árvores.

O que é uma Lista em C (Lists)

Esqueça a programação. Use seu bom senso e responda: o que é uma lista?
Vamos supor que você fez uma lista de compras.
Ou seja, tem um pedaço de papel com diversos elementos, em uma dada ordem.
Provavelmente essa ordem é a que você vai comprar, do primeiro para o último. Geralmente elas tem uma sequência lógica, como elementos do mesmo setores estarem adjacentes.
Depois você vai trabalhar com essa lista, seguir a ordem dela, marcar se comprou ou não, anotar o preço etc.

A analogia é parecida para uma lista em C.
Em programação, lista é uma série de elementos ligados. O primeiro é ligado no segundo, que é ligado no terceiro etc.
Iremos aprender como colocar elementos, tirar, mudar de posição. Como elas estão ligadas, basta que tenhamos o endereço (ponteiro) para o primeiro elemento da lista.

Ou seja, iremos estudar as chamadas listas encadeadas, que são itens 'alinhados' numa fila.

Filas em C (Queue)

Outro importante conceito de estrutura de dados dinâmica são as filas, que são exatamente iguais as do mundo real.
Como funciona a fila de um caixa eletrônico?

Chega a primeira pessoa, é atendida. Já a segunda, fica na fila, e será atendida depois da primeira.
A terceira a chegar só vai ser atendida depois da segunda, e assim sucessivamente.

Ou seja, os primeiros elementos a chegar serão os primeiros a serem atendidos.
Um termo muito conhecido para designar tal tipo de ideia é FIFO - First In, First Out (Primeiro que entra, primeiro que sai).

Em termos de programação, dizemos que os elementos que chegam vão para a cauda da fila, ou seja, para o final, serão atendidos por último. Os elementos que serão primeiro atendidos são os que estão na cabeça da fila (na frente).
Também chamamos o ato de colocar algo na fila de ENQUEUE, e de tirar de DEQUEUE.

Pilhas em C (Stack)

Outra importante estrutura dinâmica de dados são as pilhas (stacks, em inglês), que tem um funcionamento contrário ao das filas. São ditas do tipo LIFO - Last In, First Out (Ultimo a entrar, primeiro a sair).

Para entender esse tipo de estrutura, podemos imaginar uma pilha de pratos.
Você come uma coisa, e guarda o prato.
Come a segunda coisa, e põe o segundo prato em cima do primeiro.
Come a terceira e põe este prato em cima do segundo, e assim sucessivamente.

Quando você for lavar, que prato vai retirar primeiro? O de cima.
E qual o último prato a ser retirado? O primeiro.
Ou seja, você vai tirando os pratos de cima, que são os pratos que chegaram por último na pilha.
Já os pratos que chegaram primeiro na fila serão os últimos a saírem dela.

Dois termos comum nesse tipo de ordenação de estruturas são PUSH e POP.
PUSH é colocar um elemento na pilha, e POP é tirar.

Árvores em C (Tree)

Os elementos anteriores geralmente apontam para um elemento (o próximo).
Existem listas duplamente encadeadas, que cada elemento está ligado com o anterior e o próximo, mas todas elas são lineares, formam uma sequência única.

Já as árvores não, pois cada elemento pode estar ligado em um ou mais elemento, formando assim uma sub-árvore, e cada uma destas pode formar outras. Ou seja, há uma infinidade de caminhos e possibilidades para estruturas desse tipo.

Daremos atenção especial para as árvores binárias, que possuem no máximo duas ramificações.

Conceitos básicos de uma estrutura dinâmica de dados

Antes de começarmos a estudar separadamente cada estrutura que foi introduzida neste tutorial, vamos ver um esqueleto, uma estrutura básica que iremos usar em todos os itens aqui abordados.

Primeiro de tudo, iremos realmente usar estruturas, ou seja, structs.
Isso porque são elementos bem gerais, que nos permitem criar qualquer tipo de dado, da maneira que quisermos.

A segunda ideia essencial para esse estudo, é a chamada auto-referência.
Ou seja, vamos criar uma struct de um determinado tipo, e dentro dela iremos declarar um membro que é um ponteiro.
Como sabemos, os ponteiros apontam para tipos diferentes de dados, e nesse caso, o ponteiro que fica dentro de uma struct irá apontar para um tipo dessa mesma struct.

Isso se chama auto-referência. Pode ser um pouco estranho, mas é perfeitamente possível e uma ideia bastante usada.
Lembre-se: quando criamos uma struct, ela terá um tamanho (sizeof()) definido. Portanto, ela será um tipo de dado.
Então, é possível existir um ponteiro para este tipo de dado.
Em suma: é uma estrutura que possui um ponteiro.

Geralmente chamamos de nó (ou node, do inglês) os elementos de uma estrutura de dados dinâmica.
Veja como seria nossa struct:

struct node
{
 //dados e variáveis de sua struct aqui
 struct node *nextNode;
}

Esse ponteiro será de uso essencial, como veremos em breve em nossa apostila, pois eles irão apontar para o próximo elemento (próximo nó) ou para NULL, caso seja o último elemento da estrutura de dados.
É importante não se esquecer isso, é a terceira característica básica de todos esses tipos de estrutura de dados, pois é um erro bem comum entre iniciantes: o ponteiro sempre aponta para uma região de memória, aqui iremos fazer ele apontar para o próximo elemento da lista, pilha, fila ou árvore.

Quando criamos uma struct, seu ponteiro automaticamente vai apontar para o lixo, que é um endereço de memória como é endereço de memória caso apontemos esse ponteiro para outra struct, não há diferença.
Por isso é importante apontarmos o último elemento para NULL, pois diferente dos outros, só ele aponta para esse local, daí podemos usar essa informação para saber quando nossa estrutura de dados termina :)

Por hora, não se assuste. Iremos explicar, em detalhes, com muitos exemplos, cada um destes tipos, bem como faremos diversos algoritmos. Lembrando que é um assunto de suma importância, pois são ideias largamente usadas em programação.
Seu sistema operacional, por exemplo, usa e abusa de filas e pilhas para organizar os processos, o que deve ser executado primeiro, depois etc.