Fila_Dupla_-_Deque

Prévia do material em texto

Estruturas de Dados I
 Filas
Fila dupla - Deque
Estruturas de Dados I
Consultas
Consultas
Início
Final
Exclusões
Inserções
Exclusões
Inserções
Fila dupla
Fila dupla - Deque
 Inserção, remoção e acesso às duas extremidades
Estruturas de Dados I
 Operações válidas:
 Criar uma fila dupla vazia
 Inserir um nodo no início 
 Inserir um nodo no fim
 Excluir um nodo do início
 Excluir um nodo do fim
 Consultar / modificar nodo do início ou do fim
 Destruir a fila dupla
Fila dupla
Fila dupla - Deque
Estruturas de Dados I
 Fila dupla
Fila dupla implementada por contiguidade física
Estruturas de Dados I
LI : limite inferior da área no arranjo
IF : início da fila
FF : final da fila
LS : limite superior da área disponível
1 2 3 4 5 6 7 8 9 10 12 13 14
LI
LS
IF
FF
Deque
Fila dupla por contiguidade
Fila dupla implementada sobre arranjo
TipoFila = arranjo [1..N] de TipoNodo
Tipo de dados para fila dupla por contiguidade:
Estruturas de Dados I
Criação de uma fila dupla
 Inicializar indicadores de início e final da fila dupla
 Fila criada vazia
0 1 2 3 4 5 6 7 8 9 10 12 13 14
LI
LS
IF
FF
Deque
Fila dupla por contiguidade
Estruturas de Dados I
Algoritmo: 
Inicializar Deque implementada sobre Arranjo
Algoritmo InicializarDequeArr 
 Entrada: LI (inteiro)
 Saídas: IF, FF (inteiros)
início
 IF  FF  LI – 1
fim 
Fila dupla por contiguidade
Estruturas de Dados I
Inserção de um nodo em uma fila dupla
Fila dupla por contiguidade
 A inserção pode ser feita em qualquer uma das duas extremidades
 Definir em qual extremidade deve ser inserido o novo nodo
 Ocupação circular do arranjo
Início
Final
Inserção
Inserção
Estruturas de Dados I
LS
FF
LI
DEQUE
1 2 3 4 5 6 7 8 9 10 12 13 14
LS
FF
IF
LI
1 2 3 4 5 6 7 8 9 10 12 13 14
IF
LS
FF
LI
1 2 3 4 5 6 7 8 9 10 12 13 14
LS
FF
IF
LI
1 2 3 4 5 6 7 8 9 10 12 13 14
IF
DEQUE
DEQUE
DEQUE
Inserção no final
Ocupação circular do arranjo:
Fila dupla por contiguidade
Estruturas de Dados I
LS
FF
LI
DEQUE
1 2 3 4 5 6 7 8 9 10 12 13 14
LS
FF
IF
LI
1 2 3 4 5 6 7 8 9 10 12 13 14
IF
LS
FF
LI
1 2 3 4 5 6 7 8 9 10 12 13 14
LS
FF
IF
LI
1 2 3 4 5 6 7 8 9 10 12 13 14
IF
DEQUE
DEQUE
DEQUE
Inserção no início
Ocupação circular do arranjo:
Fila dupla por contiguidade
Estruturas de Dados I
Algoritmo: Inserir um nodo no Início de Deque implementada sobre Arranjo
Algoritmo InserirIniDequeArr
 Entrada: Deque (TipoDequeArr)
 LI, LS, IF, FF (inteiros)
 Info (TipoNodo)
 Saídas: Deque (TipoDequeArr)
 IF, FF (inteiros)
 Sucesso (lógico)
início
 se ((FF = IF - 1) ou ((IF = LI) e (FF = LS)))
 então Sucesso  falso
 senão início
 Sucesso  verdadeiro
 se IF = LI – 1 {DEQUE VAZIA}
 então IF  FF  LI
 senão se IF > LI 
 então IF  IF – 1
 senão IF  LS 
 Deque[IF]  Info
 fim
fim 
Estruturas de Dados I
Remoção de um nodo de uma fila dupla
Fila dupla por contiguidade
 A remoção pode ser feita em qualquer uma das duas extremidades
 Definir de qual extremidade deve ser removido o novo nodo
Início
Final
Remoção
Remoção
Estruturas de Dados I
Algoritmo: Remover o nodo do Fim da Deque implementada sobre Arranjo
Algoritmo RemoverFimDequeArr 
 Entradas: LI, LS, IF, FF (inteiros)
 Saídas: IF, FF (inteiros)
 Sucesso (lógico)
início
 se IF  LI – 1
 então início 
 se IF = FF {DEQUE VAI FICAR VAZIA}
 então IF  FF  LI - 1 
 senão se FF = LI 
 então FF  LS 
 senão FF  FF - 1 
 Sucesso  verdadeiro
 fim
 senão Sucesso  falso
fim 
Estruturas de Dados I
Acesso a uma fila dupla
Fila dupla por contiguidade
Início
Final
Acesso
Acesso
 Somente os nodos das duas extremidades podem ser acessados
Estruturas de Dados I
Algoritmo: Consultar qual o Maior valor contido nas extremidades de uma Deque implementada sobre Arranjo
Algoritmo ConsultarMaiorDequeArr 
 Entradas: Deque (TipoDequeArr)
 LI, IF, FF (inteiros)
 Saída: MaiorValor (inteiro)
início
 se IF = LI - 1 
 então MaiorValor  0
 senão se Deque[IF] > Deque[FF]
 então MaiorValor  Deque[IF]
 senão MaiorValor  Deque[FF]
fim 
Estruturas de Dados I
 Fila dupla
Fila dupla implementada por contiguidade física
Estruturas de Dados I
PtFilaDupla
Início
Final
Exclusões
Inserções
Acesso
Exclusões
Fila dupla implementada por encadeamento
Fila dupla por encadeamento
Inserções
Acesso
Para acessar o último nodo, é necessário percorrer toda a lista a partir do primeiro nodo
Estruturas de Dados I
PtDFD
/
Prim Ult
Fila dupla encadeada com descritor
Fila dupla por encadeamento
Na remoção do último nodo, precisa atualizar descritor que passará a apontar para o penúltimo – percorrer a fila do início para chegar ao penúltimo
Estruturas de Dados I
PtDFD
TipoNodo = registro
 Ant: TipoPtNodo
 Info: TipoInfoNodo
 Prox: TipoPtNodo
	 fim registro 
Tipo de dados para nodos da fila dupla:
TipoDDeque = registro
 Prim: TipoPtNodo
 Ult: TipoPtNodo
 fim registo
TipoPtDDeque = TipoDDeque
Tipo de dados para o descritor da fila dupla:
Descritor
Prim: primeiro da fila
Ult : último da fila
Prim Ult
 Ant Info Prox
Fila dupla – duplo encadeamento e descritor
Fila dupla por encadeamento
Estruturas de Dados I
Criação de fila dupla encadeada
Fila dupla por encadeamento
 Alocação do descritor
 Inicialização do descritor para fila dupla vazia
PtDFD
Prim Ult
Estruturas de Dados I
Algoritmo CriarDequeEnc 
 Entradas: -
 Saída: PtDDeque (TipoPtDDeque)
início
 alocar(PtDDeque)
 PtDDeque.Prim  PtDDdeque.Ult  nulo 
fim 
Algoritmo: 
Criar Deque implementada por Encadeamento
Fila dupla por encadeamento
Estruturas de Dados I
Inserção de um novo nodo
Fila dupla por encadeamento
PtDFD
Prim Ult
PtDFD
Prim Ult
A
C
A
B
B
N
N
C
PtDFD
Prim Ult
C
A
B
No início
No final
Estruturas de Dados I
Algoritmo: 
Inserir nodo em Deque Encadeada
Algoritmo InserirDequeEnc
 Entradas: PtDeque (TipoPtDeque)
 Lado (caractere)
 Valor (TipoInfoNodo)
 Saída: Sucesso (lógico)
var PtNovo (TipoPtNodo)
início
 Sucesso  falso
 se (Lado = “I”) ou (Lado = “F”)
 então início
 Sucesso  verdadeiro
 alocar(PtNovo)
 PtNovo.Info  Valor
 se Lado = “I”
 { então início {INSERE NO INÍCIO} SEGUE }
Fila dupla por encadeamento
Estruturas de Dados I
então início {INSERE NO INÍCIO}
 PtNovo.Ant  nulo
 se PtDDeque.Prim = nulo
 então início
 PtDDeque.Ult  PtNovo
 PtNovo.Prox  nulo
 fim
 senão início
 PtNovo.Prox  PtDDeque.Prim
 (PtDDeque.Prim).Ant  PtNovo
 fim
 PtDDeque.Prim  PtNovo
 fim
 senão início {INSERE NO FINAL}
 PtNovo.Prox  nulo
 se PtDDeque.Prim = nulo
 então início
 PtNovo.Ant  nulo
 PtDDeque.Prim  PtNovo
 fim
 senão início
 (PtDDeque.Ult).Prox  PtNovo
 PtNovo.Ant  PtDDeque.Ult
 fim
 PtDDeque.Ult  PtNovo
 fim
 fim
fim 
Algoritmo (cont): Inserirnodo em Deque Encadeada
Estruturas de Dados I
Remoção de um nodo
Fila dupla por encadeamento
PtDFD
Prim Ult
PtDFD
Prim Ult
A
C
A
B
B
X
X
C
Do final
Do início
Estruturas de Dados I
Algoritmo: 
Remover nodo de Deque Encadeada
Fila dupla por encadeamento
Algoritmo RemoverDequeEnc 
 Entradas: PtDDeque (TipoPtDDeque)
 Lado (caractere)
 Saída: Sucesso (lógico)
var PtAux, PtAnt (TipoPtNodo);
início
 Sucesso  falso
 se (PtDDeque.Prim  nulo) e ((Lado = “I”) ou (Lado = “F”))
 então início
 Sucesso  verdadeiro
 se Lado = “I”
 { então início {REMOVE O PRIMEIRO} SEGUE }
Estruturas de Dados I
 então início {REMOVE O PRIMEIRO}
 PtAux  PtDDeque.Prim
 se PtDDeque.Prim = PtDDeque.Ult
 então PtDDeque.Prim  PtDDeque.Ult  nulo
 senão início
 PtDDeque.Prim  PtAux.Prox
 (PtDDeque.Prim).Ant  nulo
 fim
 fim
 senão início {REMOVE O ÚLTIMO}
 PtAux  PtDDeque.Ult
 se PtDDeque.Prim = PtDDeque.Ult
 então PtDDeque.Prim  PtDDeque.Ult  nulo
 senão início
 PtDDeque.Ult  PtAux.Ant
 (PtDDeque.Ult).Prox  nulo
 fim
 fim
 liberar(PtAux) 
 fim
fim 
Algoritmo (cont): 
Remover nodo de Deque Encadeada
Estruturas de Dados I
Acesso a fila dupla encadeada
Fila dupla por encadeamento
Início
Final
Acesso
Acesso
PtDFD
Prim Ult
C
A
B
X
 Apodem ser acessados o primeiro e último nodo
 Endereços diretamente no descritor
Estruturas de Dados I
Algoritmo: 
Consultar Deque implementada por Encadeamento
Fila dupla por encadeamento
Algoritmo ConsultarDequeEnc 
 Entradas: PtDDeque (TipoPtDDeque)
 Lado (caractere)
 Saídas: Valor (TipoInfoNodo)
 Sucesso (lógico)
início
 Sucesso  falso
 se (PtDDeque.Prim  nulo) e ((Lado = “I”) ou (Lado = “F”))
 então início
 Sucesso  verdadeiro
 se Lado = “I” 
 então Valor  (PtDDeque.Prim).Info
 senão Valor  (PtDDeque.Ult).Info;
 fim
fim 
Estruturas de Dados I
Exercícios
Filas por encadeamento
1. O Algoritmo InserirIniDequeArr insere um novo nodo na extremidade da frente de uma fila dupla. Construa outro algoritmo que insira um novo nodo na outra extremidade, ou seja, no final da fila dupla.
Estruturas de Dados I
Exercícios
Filas por encadeamento
2. O Algoritmo RemoverFimDequeArr remove o nodo que está no final de uma fila dupla. Construa outro algoritmo que remova o nodo que está na frente desta mesma fila dupla.
Estruturas de Dados I
Exercícios
Filas por encadeamento
3. Considerando uma fila dupla implementada por contigüidade física com ocupação circular do espaço disponível, construa algoritmo para informar o valor contido em uma das extremidades da fila dupla. A extremidade considerada deve ser passada como parâmetro.
Estruturas de Dados I
Exercícios
Filas por encadeamento
4. Reescreva as operações definidas para filas duplas encadeadas, para o caso em que não seja utilizado um descritor para a fila. Considere que somente o endereço do primeiro nodo da fila dupla é conhecido, e que não existe duplo encadeamento entre os nodos.
*