Slide aula 11

Prévia do material em texto

2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados - CCT0637
PROFESSOR: EDIBERTO MARIANO
programacaoedi@gmail.com
1
Aula 11: Filas
Listas Lineares
Sequenciais e Encadeadas
(Parte IV)
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Objetivos:
➢Possibilitar ao aluno:
✓Reconhecer e manipular o TAD Fila
✓Desenvolver no laboratório os conceitos sobre o 
TAD Fila por meio de exercícios guiados que criem
✓Situações de uso dessas estruturas.
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Sequenciais e Encadeadas (ligadas) – Listas Lineares
A vantagem é o acesso direto a qualquer dos elementos da lista. 
A desvantagem é que para inserir ou remover elementos, temos que deslocar 
muitos outros elementos.
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Sequenciais e Encadeadas (ligadas) – Listas Lineares
A vantagem é a flexibilidade na inserção e remoção de elementos. 
A desvantagem é que não temos acesso direto aos elementos. Não existe algo
equivalente ao índice para se acessar diretamente o elemento.
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
✓As filas são listas onde o primeiro elemento a 
ser inserido é sempre o primeiro a ser removido. 
✓Por isso as filas são muitas vezes chamadas de 
FIFO (First In First Out).
© N. Félix & H. 
Coelho
© N. Félix & H. Coelho
Definição – já visto antes
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Inclusão e exclusão em uma fila:
Por exemplo:
Se os números 9 12 7 4 e 8 forem inseridos em uma fila
nesta ordem, então eles deverão ser removidos nesta
mesma ordem 9 12 7 4 e 8.
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Especificação:
FIL *Inicia_Fila(int N)
Cria uma nova estrutura de fila com tamanho máximo N.
ENQUEUE(FIL*q, int A)
Insere/Enfileira um novo elemento A no fim da fila Q
int DEQUEUE(FIL *q)
Retira/Desenfileira o elemento do início da fila Q retornando seu valor
int SIZE(FIL *q)
retorna o valor correspondente a quantidade de elementos armazenados
na Fila
int IS_EMPTY(FIL *q)
retorna o valor 1 se a Fila estiver vazia e 0, caso contrário.
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas:
Como no caso de pilhas as filas também podem ser 
implementadas de forma:
✓Estática com acesso sequencial usando arrays.
✓Dinâmica com acesso encadeado usando ponteiros.
Restrições quanto à manipulação:
✓ inserções sempre no final, remoções sempre do 
início da fila.
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: implementação estática
• Definida utilizando alocação estática e acesso sequencial dos elementos
• Definida utilizando um array
• Implementação em módulos, o usuário tem acesso a apenas um
ponteiro do tipo fila
✓ Isso impede o usuário de saber como foi implementada a fila e limita 
o seu acesso a apenas às funções que manipulam o início e o final da fila.
• A principal vantagem de se utilizar um array na definição de uma fila estática
é a facilidade de criar e destruir a fila.
• A principal desvantagem é a necessidade de definir previamente o tamanho
do array e, consequentemente da fila.
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: implementação estática
implementação estática - struct
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: alocação estática
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: Alocação estática
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: Alocação dinâmica
A função malloc
A função malloc (o nome é uma abreviatura de memory allocation), aloca espaço para
um bloco de bytes consecutivos na memória RAM (= random access memory) do
computador e devolve o endereço desse bloco.
O número de bytes é especificado no argumento da função.
No seguinte fragmento de código, malloc aloca 1 byte:
char *ptr;
ptr = malloc (1);
A chamada (a, b) aloca um bloco de a * b 
bytes e atribui valor zero a todos esses 
bytes
A função calloc
int *b;
int a;
...
p=(int *) calloc(a, sizeof(int));
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: Alocação dinâmica
A função free
As variáveis alocadas estaticamente dentro de uma função, também conhecidas como
variáveis automáticas ou locais, desaparecem assim que a execução da função termina.
Já as variáveis alocadas dinamicamente continuam a existir mesmo depois que a execução
da função termina.
Se for necessário liberar a memória ocupada por essas variáveis, é preciso recorrer à
função free.
A função free desaloca a porção de memória alocada por malloc. A instrução free avisa ao
sistema que o bloco de bytes apontado está disponível para reciclagem. A próxima
invocação de malloc poderá tomar posse desses bytes.
Não aplique a função free a uma parte de um bloco de bytes alocado
por malloc (ou realloc). Aplique free apenas ao bloco todo.
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: implementação dinâmica - Incluir
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: implementação dinâmica - Incluir
Adiciona um item no fim da fila q. Retorna true se operação realizada com
sucesso, false caso contrário.
tipo_elem *p; 
p = malloc(sizeof(tipo_elem)); 
if (p == NULL) 
return FALSE; 
p->info = info; 
p->lig = NULL; 
if (vazia(q)) 
q->inicio = p; 
else 
q->fim->lig = p; 
q->fim = p; 
return TRUE;
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: implementação dinâmica - Excluir
Remove um item do início da fila q. Retorna true se operação realizada com
sucesso, false caso contrário
tipo_elem *p; 
if (vazia(q)) 
return FALSE; 
p = q->inicio; 
*info = p->info; 
q->inicio = p->lig; 
if (q->inicio == NULL) 
q->fim = NULL; 
free(p); 
return TRUE; 
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: implementação dinâmica
Vantagens
• Ocupa espaço estritamente necessário 
Desvantagens
• Custos usuais da alocação dinâmica (tempo de alocação, campos de 
ligação)
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Filas: dinâmica / estática (quando usar)
Representação Estática: 
• quando fila tiver tamanho pequeno ou 
• seu comportamento for previsível 
Representação Dinâmica: 
• nos demais casos
2019.2
Professor: Ediberto MarianoAula 11
2020.1
Estrutura de Dados
11. Filas
1) Ano: 2013 / Banca: FCC / Órgão: TRT - 9ª REGIÃO (PR) / Prova: Técnico Judiciário - Tecnologia da 
Informação
Insira os dados de entrada numa fila. Em seguida retire cada dado da fila e insira numa pilha. Mostre a pilha. 
Depois retire os dados da pilha e insira na fila. Mostre a fila. 
Dados de entrada: 11, 12, 23, 14, 25, 50, 8, 18, 29, 10
As estruturas mostradas ficam 
I. Pilha: (topo) 10 - 29 - 18 - 8 - 50 - 25 - 14 - 23 - 12 - 11 
II. Fila: (começo) 11 - 12 - 23 - 14 - 25 - 50 - 8 - 18 - 29 - 10 (fim) 
III. Fila: (começo) 10 - 29 - 18 - 8 - 50 - 25 - 14 - 23 - 12 - 11 (fim) 
IV. Pilha: (topo) 11 - 12 - 23 - 14 - 25 - 50 - 8 - 18 - 29 - 10 
V. A fila mostrada fica com os elementos em ordem invertida dos dados de entrada 
Está correto o que se afirma APENAS em
a) III e IV.
b) II e IV.
c) I, II e III.
d) I, III e V.
e) I, IV e V
Exercícios
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Exercícios
2) Ano: 2012 / Banca: ESAF / Órgão: Receita Federal / Prova: Analista Tributário da Receita
Federal
Assinale a opção correta.
a) Uma fila é um tipo de lista linear em que todas as categorias são inseridas em um
extremo, ficando as classes restritas ao outro extremo.
b) Uma pilha é um tipo de lista linear em que todas as operações de inserção e
remoção são realizadas numa mesma extremidade.
c) Uma fila é um tipo de lista colinear em que inserções parametrizadas são realizadas
no mesmo extremo que as remoções.
d) Uma pilha é um tipo de lista encadeada em que todas as operações de inserção e
retrieve são realizadas na extremidade mais próxima.
e) Uma pilha é um fila linear em que todas as operações de carry e stand são 
realizadas numa mesma extremidade
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Exercícios
3) Ano: 2010 / Banca: ESAF / Órgão: CVM / Prova: Analista de Sistemas
Uma fila é um tipo de lista linear em que:
a) as inserções são realizadas em um extremo e as remoções no outro extremo.
b) as inserções e remoções são realizadas em um mesmo extremo.
c) podem ser realizadas apenas inserções.
d) a inserção de um elemento requer a remoção de outro elemento.
e) a ordem de saída não corresponde à ordem de entrada dos elementos.
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Exercícios
4) Ano: 2010 / Banca: FCC / Órgão: TRT - 22ª Região (PI) / Prova: Analista Judiciário -
Tecnologia da Informação
Uma fila duplamente terminada, isto é, uma estrutura linear que permite inserir e remover de 
ambos os extremos é chamada:
a) Árvore.
b) Shift-and.
c) Autômato.
d) Deque.
e) Boyer-Moore
2019.2
Professor: Ediberto Mariano Aula 11
2020.1
Estrutura de Dados
11. Filas
Exercícios
5) Posso alocar um vetor estaticamente com número não-constante de elementos? Por exemplo,
posso dizer
int v[n];
se o valor de n só se torna conhecido durante a execução do programa?
6) É verdade que devemos atribiuir NULL a cada ponteiro que se tornou inútil ou
desnecessário? Porque?
7) É verdade que deveríamos usar a função calloc no lugar de malloc? Porque?