Guia de Estruturas de Dados: Listas, Pilhas e Filas

Lista Encadeada

A lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por células que apontam para o próximo elemento da lista. Para "ter" uma lista ligada ou encadeada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula. Para inserir dados ou remover dados, é necessário ter um ponteiro que aponte para o primeiro elemento e outro que aponte para o fim, porque se queremos inserir ou apagar dados que estão nessas posições, a operação é rapidamente executada.

A importância e as vantagens são:

• A inserção ou remoção de um elemento na lista não implica a mudança de lugar de outros elementos;
• Não é necessário definir, no momento da criação da lista, o número máximo de elementos que esta poderá ter. Ou seja, é possível alocar memória "dinamicamente", apenas para o número de nós necessários.

Listas Duplamente Encadeadas

Em uma lista duplamente encadeada, cada elemento possui as informações de quem é seu sucessor e seu antecessor.

Principais vantagens e importância:

• Permite caminhar nas duas direções da lista;
• Inclusão e remoção de elementos são realizados com mais facilidade.

Principais problemas:

• Maior espaço alocado;
• Manipulação de um ponteiro extra.

Pilhas

A pilha é um tipo abstrato de dado e estrutura de dados baseado no princípio de "o último que entra é o primeiro que sai" (LIFO), caracterizando um empilhamento de dados. Pilhas são fundamentalmente compostas por duas operações: push (empilhar), que adiciona um elemento no topo da pilha, e pop (desempilhar), que remove o último elemento adicionado. As pilhas são importantes e muito úteis quando queremos armazenar temporariamente uma informação que vamos usar logo depois.

Filas

Uma fila difere de uma pilha na medida em que opera na base de um FIFO (First In, First Out). Assim: adicionamos novos elementos ao fim da fila, e removemos sempre do princípio da fila.

Um exemplo que expõe a importância: no dia a dia, estamos acostumados com as filas em diversos lugares: nos bancos, nos mercados, nos hospitais, nos cinemas, entre outros. As filas são importantes pois elas determinam a ordem de atendimento das pessoas. As pessoas são atendidas conforme a posição delas na fila. O próximo a ser atendido é o primeiro da fila. Quando o primeiro da fila é chamado para ser atendido, a fila "anda", ou seja, o segundo passa a ser o primeiro, o terceiro passa a ser o segundo e assim por diante até a última pessoa. Normalmente, para entrar em uma fila, uma pessoa deve se colocar na última posição, ou seja, no fim da fila. Desta forma, quem chega primeiro tem prioridade. E é dessa mesma maneira que as filas em estruturas de dados são importantes e fundamentais.