Instituto de Computação Algoritmos e Estrutura de Dados II

Listas,

Pilhas e Filas

Universidade Federal do Amazonas

Instituto de Computação

Algoritmos e Estrutura de Dados II

Horácio Fernandes

ColabWeb: http://bit.ly/aed2-colab [e-mail]



Listas, Pilhas e Filas

Avisos

. Atenção #1

– Estes slides estão em versão beta.

– Apesar de terem sido revisados, alguns códigos podem ainda conter

alguns bugs.

– Caso encontre algum, envie e-mail para

. [e-mail]

. Atenção #2

– Cuidado ao copiar/colar códigos do formato PDF. Em geral as “aspas”

ficam erradas e caracteres invisíveis são introduzidos em seu código,

gerando erros de compilação quase impossíveis de serem detectados.

Dê preferência para o formado ODP (LibreOffice).



Listas, Pilhas e Filas

Estruturas de Dados

. O que é uma Estrutura de Dados?

– É um conjunto de tipos, operações sobre estes tipos, e seus

correspondentes conceitos cujo principal objetivo gira em torno de

armazenar informações de forma organizada.

– Em Orientação a Objetos, um tipo de dado e suas operações

corresponde a uma Classe.

– Portanto, nesta disciplina estaremos trabalhando na implementação

de classes específicas para o armazenamento e acesso a

informações.

– Mais especificamente, focaremos nos algoritmos de manipulação das

estruturas e na análise dos mesmos.



Listas, Pilhas e Filas

Análise de Complexidade

. A análise de um algoritmo consiste em “medir” o custo ou tempo

de execução do mesmo bem como a quantidade de memória

necessária para rodá-lo. Neste curso, focaremos na medida de

custo de execução.

. Uma vez que “tempo” depende do computador, do compilador e

de outros fatores, em geral usamos a noção de complexidade

para analisar algoritmos.

. Complexidade Assintótica:

– Função matemática f(n) que indica o comportamento da quantidade de

operações executadas por um algoritmo

– Tal função é dependente (em geral) do tamanho n de entrada do algoritmo

– Ignora-se os custos menos significativos, constantes, etc

– Principais classes (na ordem):

. O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n), O(n!)



Listas, Pilhas e Filas

Análise de Complexidade

. A análise de complexidade pode ser indicada em três casos:

– Pior Caso: quando o algoritmo é executado com uma entrada específica

que faz com que o algoritmo execute a quantidade máxima de operações

possível.

– Melhor Caso: quando o algoritmo é executado com uma entrada que gera

a menor quantidade de operações executadas possível.

– Caso Médio: é o caso esperado que o algoritmo seja executado na

maioria das vezes.

. Notação nos slides

– Em geral, estamos mais interessados no pior caso de execução dos

algoritmos. Tais complexidades serão indicadas em muitos algoritmos e

códigos apresentados nos slides através da seguinte notação:

Custo

O(n2) Leia-se: o algoritmo possui complexidade O de n2.

Deduz-se que é o pior caso de execução do algoritmo.



Listas, Pilhas e Filas

Principais Estruturas de Dados

. Algumas das estruturas de dados mais utilizadas e que

estudaremos e analisaremos neste curso:

– Listas, Pilhas e Filas (Lists, Stacks, Queues)

. Armazenam elementos de um conjunto como uma sequência de

elementos

– Tabelas Hash (Hash Tables)

. Armazenam valores em um vetor (tabela), mas de forma organizada de

acordo com uma chave associada a cada valor

– Árvores (Trees)

. Armazenam dados de forma organizada de acordo com o conteúdo do

elemento em uma estrutura que lembra uma árvore (com raízes e folhas)

– Grafos (Graphs)

. Armazenam dados que são capazes de referenciar outros dados,

representando relações ou conexões entre os mesmos.