Estruturas de Dados: Listas Encadeadas, Pilhas e Filas
Resumo
O documento apresenta três estruturas de dados fundamentais: a lista encadeada e a lista duplamente encadeada, que organizam elementos por ponteiros, e as estruturas pilha (LIFO) e fila (FIFO). Explica as operações básicas de cada uma, suas vantagens, desvantagens e exemplos do cotidiano que ajudam a entender a ordem de atendimento.
Pontos-chave
- Lista encadeada: células que apontam para o próximo elemento, com o último apontando para nulo.
- Na lista encadeada, inserir ou remover elementos não exige mover outros elementos e a memória é alocada dinamicamente.
- Lista duplamente encadeada: cada elemento conhece seu sucessor e seu antecessor, permitindo percorrer nas duas direções, mas ocupa mais espaço.
- Pilha: princípio LIFO (o último que entra é o primeiro que sai), com operações push (empilhar) e pop (desempilhar).
- Fila: princípio FIFO (First In, First Out); novos elementos entram no fim e são removidos do início.
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.
Baixar
PDF Word HTMLPerguntas frequentes
O que é uma pilha em estruturas de dados?
Uma pilha é um tipo abstrato de dado baseado no princípio LIFO, em que o último elemento adicionado é o primeiro a sair. Suas operações principais são push, que empilha, e pop, que desempilha.
Qual a diferença entre pilha e fila?
A pilha segue o princípio LIFO, removendo o último elemento inserido, enquanto a fila segue o princípio FIFO, removendo sempre o elemento que chegou primeiro. Na fila, novos elementos entram no fim e saem pelo início.
Quais as vantagens da lista duplamente encadeada?
Ela permite caminhar nas duas direções da lista e facilita a inclusão e a remoção de elementos. Em contrapartida, ocupa mais espaço e exige a manipulação de um ponteiro extra.
Teste-se
Cartões de revisão
Clique em um cartão para ver a resposta.
Teste
Perguntas geradas com IA a partir do documento: verifique as respostas com o texto.