Filas, Pilhas e Listas PDF

Preview

Summary

Nesta unidade de aprendizagem, entenderemos o conceito de Fila, Pilha e Lista. Veremos que Fila é uma estrutura de dados do tipo FIFO (First In, First Out) ou PEPS (Primeiro a Entrar, Primeiro a Sair) e Pilha é uma estrutura do tipo LIFO (Last In, First Out) ou UEPS (Último a Entrar, Primeiro a Sair...

Description

Filas, Pilhas e Listas 1. Filas e Filas de Prioridade Em nosso cotidiano, frequentemente verificamos o uso do conceito de Fila. Usamos a fila do banco, a fila do supermercado, a fila do hospital, a fila do estádio etc. O conceito pode ser empregado para organizar os elementos de maneira que o primeiro a ser inserido seja também o primeiro a ser retirado, podendo apresentar particularidades, como a fila de Banco, na qual pode haver clientes com prioridades (que devem ser atendidos primeiro). Nesse caso, é necessário que se utilize o conceito de uma Fila de Prioridades. 1.1 Filas Computacionalmente, uma Fila pode ser definida como estrutura do tipo FIFO (First In, First Out) ou PEPS (Primeiro a Entrar, Primeiro a Sair). Isto é, no contexto computacional, a Fila apresenta as mesmas características das filas presentes em nosso cotidiano. 1.1.2 Atendimento ao Primeiro Elemento e Inserção de Elementos Novos no Final Utilizando uma estrutura de dados do tipo FIFO, o primeiro elemento a ser inserido também será o primeiro a ser retirado. Em uma Fila, as inserções e as remoções são feitas nas extremidades opostas, pois o elemento do início sempre é retirado, e o novo elemento é sempre inserido no final da Fila. Uma Fila pode ser implementada utilizando os conceitos de uma Lista Sequencial ou de uma Lista Encadeada. 1.1.3 Filas de Prioridades Em uma Fila comum, todos os elementos possuem a mesma prioridade. Assim, seguem rigorosamente o conceito de FIFO (First In, First Out). Entretanto, pode surgir a necessidade de criar aplicações mais complexas, em que os elementos tenham prioridades diferentes. Sendo preciso usar uma estrutura de Fila de Prioridade. Uma Fila de Prioridade é um tipo especial de Fila, em que os elementos podem ter prioridades diferentes e, dessa forma, devem ser tratados e atendidos de maneira diferenciada. Nesse tipo de Fila, cada elemento possui um campo especial que define sua prioridade. Vejamos alguns exemplos de problemas do nosso cotidiano que devem ser resolvidos utilizando o conceito de Fila de Prioridade: ▪ Fila de Banco: Clientes preferenciais possuem prioridade de atendimento em um banco; ▪ Fila de Hospital: Pessoas com problemas de saúde mais grave devem ser tratadas primeiro; ▪ Controle de Processos: Processos com maior urgência devem ser atendidos primeiro.

2. Pilhas Uma Pilha pode ser definida como estrutura do tipo LIFO (Last In, First Out) ou UEPS (Último a entrar, Primeiro a Sair). A Pilha pode ser considerada uma Fila de Prioridade, na qual o último elemento inserido possui uma prioridade maior que os demais. Em uma Pilha, os elementos são retirados e inseridos em uma única extremidade. Portanto, na Pilha, administramos as operações de inserção e remoção pelo Topo. Utilizando uma estrutura de dados do tipo LIFO, o último a ser inserido sempre será o primeiro elemento a ser retirado. Uma Pilha, assim como uma Fila, também pode ser implementada utilizando os conceitos de uma Lista Sequencial ou de uma Lista Encadeada. 3. Listas Ordenadas e Listas não Ordenadas Na área da computação, é fundamental trabalhar com conjuntos de dados (coleções) para resolução de problemas computacionais. Esses conjuntos de dados podem ser organizados por meio de uma lista linear, na qual podem ser realizadas diversas operações, como: inserir e excluir de elementos, buscar elementos, encontrar o maior e menor elemento, contar elementos, alterar valores dos elementos e também buscar os elementos sucessores e predecessores.

Importante! Uma lista linear não possui, a princípio, uma regra para inserção e remoção de seus elementos, que poderão ser inseridos ou removidos em qualquer posição. - Inserção: Geralmente, em Listas não ordenadas, inserimos os elementos no final. Nas Listas ordenadas, percorremos a Lista e inserimos o novo elemento na sequência, garantindo a continuação da ordenação. - Remoção: Em uma Lista, qualquer elemento pode ser removido. Dessa forma, para que ocorra a Remoção, é preciso buscar o elemento que se deseja remover e retirá-lo da Lista. A remoção pode ser realizada pelo índice ou pelo valor elemento. Além disso, podem ser utilizados diferentes tipos de busca para encontrar o elemento, como a busca binária e a busca sequencial.

A opção pela utilização de uma Lista ordenada ou não ordenada depende de vários fatores, incluindo a análise de complexidade. Nem sempre é vantajoso manter a ordenação dos elementos, sendo possível resolver inúmeros problemas computacionais sem que os dados da Lista estejam ordenados.

Na resolução de problemas computacionais que envolvem ordenação, podemos optar por já inserir os elementos em uma Lista ordenada ou inserir os elementos desordenados e ordená-los utilizando um método de ordenação. Portanto, na resolução de problemas computacionais, é preciso avaliar todos os cenários e verificar a importância de ordenação das listas e em qual momento isso deve ser feito. Na linguagem Java, existem diversas classes que podem ser utilizadas para as implementações de Listas. As mais famosas são ArrayList e LinkedList, que implementam respectivamente listas com alocação sequencial e encadeada. Essas classes permitem que seus elementos possam ser ordenados por meio do método sort. A seguir, estão os códigos utilizados para esse método....