Estruturas de dados e algoritmos são temas fundamentais da ciência da computação, sendo utilizados nas mais diversas áreas do conhecimento e com os mais diferentes propósitos de aplicação. Sabe-se que algoritmos manipulam dados. Quando estes dados estão organizados (dispostos) de forma coerente, caracteriza uma forma, uma estrutura de dados. São a organização e os métodos que manipulam esta determinada estrutura que lhes conferem singularidade. As estruturas de dados são chamadas tipos de dados compostos que se dividem em dois: homogêneos (vetores e matrizes) e heterogêneos (registros). As estruturas homogêneas são conjuntos de dados formados pelo mesmo tipo de dado primitivo. As estruturas heterogêneas são conjuntos de dados formados por tipos de dados primitivos diferentes (campos do registro) em uma mesma estrutura. A escolha de uma estrutura de dados apropriada pode tornar um problema complicado em um de solução bastante trivial. O estudo das estruturas de dados está em constante desenvolvimento (assim como o de algoritmos), mas, apesar disso, existem certas estruturas clássicas que se comportam como padrões.

■ Estruturas de dados clássicas

Vetores ou arrays

São estruturas de dados lineares e estáticas, isto é, são compostas por um número fixo (finito) de elementos de um determinado tipo de dados. O tempo de acesso aos elementos de um vetor é muito rápido, sendo considerado constante: o acesso aos elementos é feito pelo seu índice no vetor. Porém, a remoção de elementos pode ser custosa se não for desejável que haja espaços "vazios" no meio do vetor, pois nesse caso é necessário "arrastar" de uma posição todos os elementos depois do elemento removido.

Essa é uma estrutura muito recomendada para casos em que os dados armazenados não mudarão, ou pouco mudarão, através do tempo.

■ Lista

Uma Lista é uma estrutura de dados linear. Uma lista ligada é linear e dinâmica, composta por células que apontam para o próximo elemento da lista. Para "ter" uma lista ligada, basta guardar seu primeiro elemento, e seu último elemento apontar para uma célula nula.

A principal diferença entre as listas e os vetores é que as listas implementam alocação dinâmica de memória.

■ Pilha

As pilhas são estruturas baseadas no princípio LIFO (last in, first out), onde os dados que foram inseridos por último na pilha serão os primeiros a serem removidos. Existem duas funções que se aplicam a todas as pilhas: PUSH, que insere um dado no topo da pilha, e POP, que remove o item no topo da pilha.

■ Fila

As filas são estruturas baseadas no princípio FIFO (first in, first out), em que os elementos que foram inseridos no início são os primeiros a serem removidos. Uma fila possui duas funções básicas: ENQUEUE, que adiciona um elemento ao final da fila, e DEQUEUE, que remove o elemento no início da fila.

A operação ENQUEUE sempre pode ser executada, uma vez que teoricamente uma fila não tem limite. A operação DEQUEUE só pode ser aplicada se a fila não estiver vazia, causando um erro de underflow ou fila vazia se esta operação for realizada nesta situação.

<■ Árvores

Uma árvore é uma estrutura de dados em que cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como:

• uma estrutura (uma árvore);
• um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).
• Não Existe árvores vazias, no mínimo haverá um nó raiz (que não possui pai)

Cada árvore tem apenas uma raiz. Além disso, os elementos associados a cada nó são habitualmente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas.

Árvore, no contexto da programação e ciência da computação, é uma estrutura de dados que herda as características das topologias em árvore. Conceitualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica.

A árvore é composta por um elemento principal chamado raiz, que possui ligações para outros elementos, que são denominados de galhos ou filhos. Estes galhos levam a outros elementos que também possuem outros galhos. O elemento que não possui galhos é conhecido como folha ou nó terminal.

O número máximo de galhos em um elemento é chamado ordem da árvore. Uma árvore binária é aquela de ordem 2, i.e., em que cada elemento possui no máximo 2 galhos.

Uma das operações importantes consiste em percorrer cada elemento da árvore uma única vez. Esse percurso, também chamado de travessia da árvore, pode ser feito em pré-ordem (os filhos de um nó são processados após o nó) ou em pós-ordem (os filhos são processados antes do nó). Em árvores binárias é possível ainda fazer uma travessia-em-ordem, em que se processa o filho à esquerda, o nó, e finalmente o filho à direita.

O algoritmo abaixo descreve uma travessia pré-ordem:

PercursoPreordem(nó): 
  Processa nó
  Para cada filho de nó (se houver)
     Executa recursivamente PercursoPreordem(filho)     

Outra operação, utilizada nas árvores de pesquisa é a travessia da raiz até uma das folhas. Essa operação tem um custo computacional proporcional ao número de níveis da árvore. O pior caso é a travessia de todos os elementos até a folha de nível mais baixo. Árvores balanceadas apresentam o melhor pior caso possível, para um certo número de nós. O pior pior caso apresenta-se na árvore degenerada em que cada nó possui exatamente um filho, e a árvore tem o mesmo número de níveis que de nós, assemelhando-se a uma lista ligada.

■ Árvores binárias

Uma árvore binária é uma árvore em que cada nó tem no máximo dois filhos. São muito utilizadas como estruturas de buscas, como árvores de busca binária e árvores AVL.

■ Tabela de hashing

A tabela hash (de hashing, no inglês), também conhecida por tabela de espalhamento ou tabela de dispersão, é uma estrutura de dados especial, que associa chaves de pesquisa (hash) a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado. É algumas vezes traduzida como tabela de escrutínio.