Baixe o app para aproveitar ainda mais
Prévia do material em texto
UNICARIOCA MÓDULO-03 FILAS ESTRUTURA DE DADOS FILA (QUEUE) ESTRUTURA_DE_DADOS MÓDULO_03_FILAS 1 MANUEL � 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. ESTRUTURA_DE_DADOS MÓDULO_03_FILAS 2 MANUEL 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 MÓDULO_03_FILAS 3 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 ESTRUTURA_DE_DADOS MÓDULO_03_FILAS 4 MANUEL 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( ) ESTRUTURA_DE_DADOS MÓDULO_03_FILAS 5 MANUEL 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 MÓDULO_03_FILAS 6 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( ) ESTRUTURA_DE_DADOS MÓDULO_03_FILAS 7 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ÇÃ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 ] ESTRUTURA_DE_DADOS MÓDULO_03_FILAS 8 MANUEL 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 MÓDULO_03_FILAS 9 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 ESTRUTURA_DE_DADOS MÓDULO_03_FILAS 10 MANUEL
Compartilhar