Estrutura de Dados: Filas e Deques

Prévia do material em texto

Estrutura de Dados
Filas
Jorge Campos
jorge@unifacs.br
Filas
Definição
Uma Fila é uma seqüência mutável de zero ou mais itens na forma A1, A2,…,An, onde A1 é chamado de frente da fila e An é chamado de fundo da fila .
Uma fila é uma estrutura linear onde inserções de elementos são realizadas no fundo da fila e remoções de elementos sempre ocorrem na frente da fila.
Fila é uma estrutura conhecida como FIFO (first in, first out)
Tipo Abstrato de Dados = (objetos, operações)
Operações Sobre Objetos Fila
Criar uma Fila vazia
Verificar se a Fila está vazia 
Esvaziar a Fila
Adicionar um elemento na Fila (enqueue)
Remover um elemento da Fila (dequeue)
Imprimir a Fila
*
Especificação do TAD Fila
public class Queue{
// Visão Geral: ver definição
// Construtores
public Queue()
// Efeito: Inicializa this como uma fila vazia de Objects
// this.isEmpty()=true
// Métodos
public boolean isEmpty()
// Efeito: testa se a fila está vazia
public void makeEmpty()
// Modifica: this
// Efeito: esvazia a fila this_post.isEmpty()=true
public void enqueue (Object elem)
// Modifica: this
// Efeito: adiciona elem no final da fila
public object dequeue() 
// Modifica: this
// Efeito: se this.isEmpty() retorna null caso
// contrário retira o elemento na frente da fila
public void printFila ()
// Efeito: Imprime todos os elementos da pilha usando o método toSting()
*
Implementação do TAD Fila com Apontadores
public class Queue{
// Representação
 private QueueNode front,rear;
 private class QueueNode {
 private Object element;
 private QueueNode next;
 private QueueNode (Object e, QueueNode n) {
 element=e;
 next=n;
 }
 }
// Construtores
public Queue() {
 front=rear=null;
}
// Métodos
public boolean isEmpty() {
 return (front==null);
}
public void makeEmpty() {
 front=rear=null;
}
MinhaFila
QueueNode front
QueueNode rear
*
Implementação do TAD Fila com Apontadores
public void enqueue(Object elem) {
 QueueNode newElement = new QueueNode (elem,null);
 if (front==null) { // insere em uma fila vazia
 front=rear=newElement;
 }
 else {
 rear.next=newElement;
 rear=newElement;
 }
}
MinhaFila
MinhaFila.enqueue(O1) 
QueueNode front
QueueNode rear
element O1
next
newElement 
*
Implementação do TAD Fila com Apontadores
public void enqueue(Object elem) {
 QueueNode newElement = new QueueNode (elem,null);
 if (front==null) { // insere em uma fila vazia
 front=rear=newElement;
 }
 else {
 rear.next=newElement;
 rear=newElement;
 }
}
MinhaFila
MinhaFila.enqueue(O1) 
MinhaFila.enqueue(O2) 
QueueNode front
QueueNode rear
element O1
next
newElement 
element O2
next
newElement 
*
Implementação do TAD Fila com Apontadores
public Object dequeue {
 if (isEmpty()) 
 return null;
 Object elem=front.element;
 front=front.next;
 if (front==null) 
 rear=null; 
 return elem;
}
MinhaFila
MinhaFila.dequeue() 
QueueNode front
QueueNode rear
element O2
next
newElement 
element O1
next
newElement 
*
Implementação do TAD Fila com Apontadores
public void printFila () {
 if (this.isEmpty()) return;
 QueueNode itr=front;
 while (itr!=null) {
 System.out.println(itr.element.toString());
 itr=itr.next;
 }
}
*
Fila com Arranjos
enqueue(O1) 
enqueue(O2) 
dequeue() 
	O1
	O1	O2	O3	O4	O5
	O1	O2	O3	O4	O5
	O1	O2	O3	O4	O5
	O1	O2
Int front
Int rear
Int front
Int rear
Int front
Int rear
Int front
Int rear
Int front
Int rear
Int front
Int rear
enqueue(O3) 
enqueue(O4) 
enqueue(O5) 
dequeue() 
dequeue() 
*
Fila com Arranjos
int front
int rear
enqueue(O6) 
enqueue(O9) 
	O1	O2	O3	O4	O5
	O6	O2	O3	O4	O5
	O6	O7	O8	O4	O5
	 	 	 	 
	O4	O5	O6	O7	O8	O9	 	 
int front
int rear
int front
int rear
int front
int rear
enqueue(O7) 
enqueue(O8) 
*
Aplicações de Fila
	São utilizadas quando desejamos processar itens de acordo com a ordem “primeiro-que-chega, primeiro-atendido”.
	Sistemas operacionais utilizam filas para regular a ordem na qual tarefas devem receber tempo de processamento e na qual recursos devem ser alocados a processos.
	...
*
Deque (Double End Queues)
Definição
Um Deque é uma seqüência mutável de zero ou mais itens na forma A1, A2,…,An, onde A1.
Um deque é uma estrutura linear onde inserções, remoções e inspeções de elementos podem ocorrer em qualquer extremidade.
Tipo Abstrato de Dados = (objetos, operações)
Operações Sobre Objetos Deque
Criar um Deque vazio
Verificar se o Deque está vazio 
Esvaziar o Deque
Adicionar um elemento na frente do Deque (pushFront)
Adicionar um elemento no final do Deque (pushBack)
Remover um elemento na frente do Deque (popFront)
Remover um elemento no final do Deque (popBack)
Inspecionar um elemento na frente do Deque (front)
Inspecionar um elemento no final do Deque (back)
Imprimir o Deque
*