ESTR_TEMA_04

Prévia do material em texto

UNICARIOCA
TEMA-04
FILAS
ESTRUTURA DE DADOS FILA
(QUEUE)
 CONTEXTO
Considerando-se somente as
operações de acesso, inserção e
remoção, restritas aos extremos de
uma LISTA, temos casos especiais
que aparecem muito frequentemente
na modelagem de problemas a serem
resolvidos por computador.
Esses casos especiais são:
FILAS e PILHAS !
FILA  é uma LISTA LINEAR onde
todas as inserções são feitas num
EXTREMO e todas as remoções e
acessos são realizados no OUTRO.
Filas são também denominadas listas
FIFO (First-In / First-Out, o primeiro que
entra  é o primeiro que sai).
A ordem de saída corresponde
diretamente à ordem de entrada dos
elementos.
FILA é uma ESTRUTURA DINÂMICA.
FILA DE CAIXA BANCÁRIO
FILA - EXEMPLO OPERAÇÕES BÁSICAS SOBRE FILAS
•ENQUEUE (PUSH)  INSERE UM
ELEMENTO NO FINAL DA FILA -
ENFILEIRAR !
•DEQUEUE (POP)  REMOVE UM
ELEMENTO DO COMEÇO DA FILA -
DESENFILEIRAR !
ESTRUTURA DE DADOS - TEMA-04 1 MANUEL
• PUSH  apesar de inserir no FINAL, não é
necessário percorrer toda a fila para inserir
no fim; basta manter sempre um PONTEIRO
para o ÚLTIMO elemento da FILA!
• POP  a remoção ocorre sempre no INÍCIO
(head) da FILA.
OPERAÇÕES BÁSICAS SOBRE FILAS EXEMPLO-01
ENQUEUE(F, a)  F:[ a ] 
ENQUEUE(F, b)  F:[ a, b ] 
ENQUEUE(F, c)  F:[ a, b, c ]
ENQUEUE(F, d)  F:[ a, b, c, d ]
DEQUEUE(F)  F:[ b, c, d ] 
DEQUEUE(F)  F:[ c, d ]
F:[ ]  FILA VAZIA 
ENQUEUE(F, e)  F:[ c, d, e ]
ENQUEUE(F, f)  F:[ c, d, e, f ]
ENQUEUE(F,DEQUEUE (F))F:[ d, e, f ]
2º 1º F:[d, e, f,c ]
DEQUEUE(F)  F:[ e, f , c ]
DEQUEUE(F) F:[ f , c ]
DEQUEUE(F)  F:[ c ]
EXEMPLO-01
F:[ c, d ] CONSIDERE AS SEGUINTES AÇÕES
REALIZADAS EM UMA FILA F:[ ]
AÇÃO
ENFILEIRAR(4)
ENFILEIRAR(5)
ENFILEIRAR(13)
DESENFILEIRAR( )
ENFILEIRAR(7)
ENFILEIRAR(2)
ENFILEIRAR(4)
DESENFILEIRAR( )
EXEMPLO-02
AÇÃO
ENFILEIRAR(9)
ENFILEIRAR(249)
ENFILEIRAR(3267)
ENFILEIRAR(13)
DESENFILEIRAR( )
DESENFILEIRAR( )
ENFILEIRAR(34)
ENFILEIRAR(3)
DESENFILEIRAR( )
INSTRUÇÕES
• A fila está VAZIA e possui tamanho
MÁXIMO de 3 elementos.
• O usuário pode digitar qualquer valor,
mas apenas os valores ímpares devem
ser enfileirados.
• Após a execução dos comandos, o
PRIMEIRO elemento da fila e a SOMA
dos elementos armazenados na fila são,
respectivamente:
A) 3 e 14. 
B) 3 e 3.
C) 4 e 80.
D) 7 e 29.
E) 7 e 40
ESTRUTURA DE DADOS - TEMA-04 2 MANUEL
CONSIDERE AS SEGUINTES AÇÕES
REALIZADAS EM UMA FILA F:[ ]
AÇÃO
ENFILEIRAR(4)
ENFILEIRAR(5)
ENFILEIRAR(13)
DESENFILEIRAR( )
ENFILEIRAR(7)
ENFILEIRAR(2)
ENFILEIRAR(4)
DESENFILEIRAR( )
EXEMPLO-02
• A fila está VAZIA e possui
tamanho MÁXIMO de 3
elementos.
• O usuário pode digitar
qualquer valor, mas apenas os
valores ímpares devem ser
enfileirados.
• Após a execução dos
comandos, o PRIMEIRO
elemento da fila e a SOMA dos
elementos armazenados na fila
são, respectivamente:
CONSIDERE AS SEGUINTES AÇÕES
REALIZADAS EM UMA FILA F:[ ]
• A fila está VAZIA e possui
tamanho MÁXIMO de 3
elementos.
• O usuário pode digitar
qualquer valor, mas apenas
os valores ímpares devem ser
enfileirados.
• Após a execução dos
comandos, o PRIMEIRO
elemento da fila e a SOMA
dos elementos armazenados
na fila são, respectivamente:
EXEMPLO-02
AÇÃO
ENFILEIRAR(9)
ENFILEIRAR(249)
ENFILEIRAR(3267)
ENFILEIRAR(13)
DESENFILEIRAR( )
DESENFILEIRAR( )
ENFILEIRAR(34)
ENFILEIRAR(3)
DESENFILEIRAR( )
CONSIDERE AS SEGUINTES AÇÕES
REALIZADAS EM UMA FILA F:[ ]
AÇÃO
ENFILEIRAR(4)
ENFILEIRAR(5)
ENFILEIRAR(13)
DESENFILEIRAR( )
ENFILEIRAR(7)
ENFILEIRAR(2)
ENFILEIRAR(4)
DESENFILEIRAR( )
EXEMPLO-02
AÇÃO
F:[ ]
F:[ 5 ]
F:[ 5 ; 13]
F:[ 13 ]
F:[ 13 ; 7]
F:[ 13 ; 7]
F:[ 13 ; 7]
F:[ 7 ]
CONSIDERE AS SEGUINTES AÇÕES
REALIZADAS EM UMA FILA F:[ ]
AÇÃO
ENFILEIRAR(9)
ENFILEIRAR(249)
ENFILEIRAR(3267)
ENFILEIRAR(13)
DESENFILEIRAR( )
DESENFILEIRAR( )
ENFILEIRAR(34)
ENFILEIRAR(3)
DESENFILEIRAR( )
EXEMPLO-02
AÇÃO  F:[7]
F:[7 ; 9]
F:[7 ; 9 ; 249 ]
F:[7 ; 9 ; 249 ]
F:[7 ; 9 ; 249 ]
F:[ 9 ; 249 ]
F:[ 249 ]
F:[ 249 ]
F:[ 249 ; 3]
F:[ 3 ]
A) 3 e 14. 
B) 3 e 3.
C) 4 e 80.
D) 7 e 29.
E) 7 e 40
GABARITO - B
PRIMEIRO = 3
SOMA = 3
FILA DUPLA: é uma LISTA LINEAR onde
as inserções, remoções ou acessos são
realizados em QUALQUER EXTREMO.
Filas Duplas são também denominadas
DEQUE (Double-Ended QUEue, ou: Fila
de Extremidade Dupla).
ESTRUTURA DE DADOS - TEMA-04 3 MANUEL
Uma FILA DUPLA pode ainda gerar dois
casos especiais:
• FILA DUPLA DE ENTRADA RESTRITA
 se a INSERÇÃO for restrita a um
único extremo.
• FILA DUPLA DE SAÍDA RESTRITA
 se a REMOÇÃO for restrita a um
único extremo.
A implementação das Filas é viável
quanto temos três recursos básicos:
• ESPAÇO de memória para
armazenar os elementos;
• Uma REFERÊNCIA ao primeiro
elemento da coleção;
• Uma REFERÊNCIA à primeira
posição livre, após o último
elemento da fila.
IMPLEMENTAÇÃO DE FILAS
Carpe Diem
ESTRUTURA DE DADOS - TEMA-04 4 MANUEL