Neste artigo, o dataholic João Victor aborda sobre algumas das estruturas mais conhecidas na computação: lista, pilha, fila e árvore. Boa leitura!
No dicionário encontra-se a seguinte definição para o termo estrutura: “Modo como alguma coisa é construída, organizada ou está disposta”. Na programação, as estruturas de dados são exatamente assim, formas diferentes de se armazenar, organizar e manipular um conjunto de dados. Algumas das estruturas mais conhecidas na computação são: lista, pilha, fila e árvore. Falaremos brevemente sobre elas a seguir. Vale salientar que além dessas existem outras estruturas que não receberam destaque neste artigo.
Listas ou Listas Encadeadas
Trata-se de uma estrutura linear, onde os elementos são ligados entre si, onde um nó (termo usado para identificar um elemento da estrutura) pode ter uma ligação com seu sucessor (lista encadeada) ou com seu sucessor e antecessor (lista duplamente encadeada). Geralmente utilizamos o termo “apontar” para identificar as ligações, por exemplo: o nó aponta para o seu sucessor. Algumas observações são necessárias antes de vermos a representação gráfica da lista:
● em caso de lista duplamente encadeada, o antecessor do primeiro nó será null (uma ligação para um valor nulo);
● independente de ser duplamente encadeada ou não, o sucessor do último nó aponta para null;
● existe também um tipo de lista conhecido como lista encadeada (ou duplamente encadeada) circular, onde o último elemento aponta para o início da lista, porém não iremos tratar dele nesse artigo.
Representação da lista encadeada
Pilha
Tipo especial de lista, onde a estrutura se baseia no princípio LIFO, que representa a expressão “last in, first out”, onde o último elemento que entra na estrutura é o primeiro a sair. Achou confuso? Explicarei melhor. Imagine uma pilha de livros, o livro que está no topo foi o último adicionado (last in), mas na hora de desempilhar ele será o primeiro a sair da pilha (first out). Esse é o comportamento da estrutura pilha.
Representação do comportamento da pilha
Exemplo de uso na computação:
● Chamadas de funções num interpretador de código;
● Mecanismo de desfazer/refazer dos editores de texto;
● Navegação entre páginas Web;
Fila
Assim como a pilha, a fila é tipo especial de lista, porém esta se baseia no princípio FIFO, que representa a expressão “first in, first out”, onde o primeiro elemento que entra na estrutura também é o primeiro a sair. Um bom exemplo para explicar seu funcionamento é uma fila em um caixa de supermercado, onde o primeiro cliente a entrar na fila (first in) é o primeiro a ser atendido e, consequentemente, é também o primeiro a sair da fila (last in).
Representação do comportamento da fila
Exemplo de uso na computação:
● Processos executados em um sistema operacional.
● Controle de documentos para impressão;
● Troca de mensagens entre computadores numa rede;
Árvores
Diferente das estruturas lineares (elementos dispostos em forma de sequência) apresentadas até agora, as árvores são estruturas não lineares. Seus dados são dispostos de forma hierárquica, onde os elementos se encontram “abaixo” ou “acima” uns dos outros.
Representação da árvore
Como apresentado na figura acima, os nós da árvore possuem algumas nomenclaturas especiais. Toda árvore possui um nó raiz, que possui ligações para os outros elementos. Em outras palavras, é o “começo” da árvore. A partir da raiz, todos os nós possuem um antecessor imediato ou pai, tomando a figura como exemplo: o Dado 3 é pai do Dado 6.
Os nós também podem ter filhos (sucessores imediatos) e irmãos (quando são filhos do mesmo pai), por exemplo: os Dados 4 e 5 são irmãos, pois são filhos do mesmo pai, o Dado 2. Nós sem filhos são chamados de nó folha, nó terminal ou nó externo.
Exemplo do uso na computação:
● Estruturas de pastas de um sistema operacional.
Conclusão
Apesar de se mostrarem simples, as estruturas de dados são peças fundamentais no mundo da programação, pois, como foi visto, elas são amplamente utilizadas na computação, seja no desenvolvimento de softwares, arquitetura de redes ou construção de sistemas operacionais.