TAD Deque
ATAI
1
ADT Deque


Uma extensão da estrutura de dados fila que suporta inserções
e remoções no início e no final da fila é chamada de fila de duas
cabeças (double-ended queue ou deque)
O ADT deque D suporta os seguintes métodos fundamentais:
 inserePrimeiro(e): Insere um novo elemento e no início de D
Entrada: Objecto; Saída: Nenhuma

insereUltimo(e): Insere um novo elemento e no final de D
Entrada: Objecto; Saída: Nenhuma

removePrimeiro(): Remove e retorna o primeiro elemento de D
Entrada: Nenhuma; Saída: Objecto

removeUltimo(): Remove e retorna o último elemento de D
Entrada: Nenhuma; Saída: Objecto
2
ADT Deque
Adicionalmente temos os seguintes métodos de suporte:
 primeiro(): Retorna o primeiro elemento de D
Entrada: Nenhuma; Saída: Objecto

ultimo(): Retorna o último elemento de D
Entrada: Nenhuma; Saída: Objecto

tamanho(): Retorna o número de elementos de D
Entrada: Nenhuma; Saída: Inteiro

estaVazia(): Determina se D está vazia
Entrada: Nenhuma; Saída: Booleano
3
Exemplo de execução numa deque
Operação
Saída
D
inserePrimeiro(3)
-
(3)
inserePrimeiro(5)
-
(5,3)
removePrimeiro( )
5
(3)
insereUltimo(7)
-
(3,7)
removePrimeiro( )
3
(7)
removeUltimo( )
7
()
removePrimeiro( )
"erro"
()
estaVazia( )
verdade
()
inserePrimeiro(9)
-
(9)
insereUltimo(7)
-
(9,7)
tamanho( )
2
(9,7)
inserePrimeiro(3)
-
(3,9,7)
insereUltimo(5)
-
(3,9,7,5)
removeUltimo( )
5
(3,9,7)
4
Interface Deque
public interface Deque {
int tamanho();
boolean estaVazia();
void inserePrimeiro(Object novo) throws DequeCheioException;
void insereUltimo(Object novo) throws DequeCheioException;
Object removeUltimo() throws DequeVazioException;
Object removePrimeiro() throws DequeVazioException;
Object ultimo() throws DequeVazioException;
Object primeiro() throws DequeVazioException;
}
5
Lista duplamente ligada
class DLNode {
private Object element;
private DLNode next, prev;
DLNode() { this(null, null, null); }
DLNode(Object e, DLNode p, DLNode n) {
element = e;
next = n;
prev = p;
}
void setElement(Object newElem) { element = newElem; }
void setNext(DLNode newNext) { next = newNext; }
void setPrev(DLNode newPrev) { prev = newPrev; }
Object getElement() { return element; }
DLNode getNext() { return next; }
DLNode getPrev() { return prev; }
}
6
Implementação do Deque com lista dupla
public class MyDeque implements Deque {
DLNode header, trailer;
int size;
// sentinels
// number of elements
public MyDeque() { // initialize an empty deque
header = new DLNode();
trailer = new DLNode();
header.setNext(trailer); // make header point to trailer
trailer.setPrev(header); // make trailer point to header
size = 0;
}
7
Método removeUltimo()
public Object removeUltimo() throws DequeEmptyException {
if (estaVazia())
throw new DequeEmptyException("Deque is empty.");
DLNode last = trailer.getPrev();
Object o = last.getElement();
DLNode secondtolast = last.getPrev();
trailer.setPrev(secondtolast);
secondtolast.setNext(trailer);
size--;
return o;
}
8
Método inserePrimeiro()
public void inserePrimeiro (Object o) {
DLNode second = header.getNext();
DLNode first = new DLNode(o, header, second);
second.setPrev(first);
header.setNext(first);
size++;
}
9
Implementação de Pilha com Deque - 1

A tabela a seguir
mapeia os métodos do
ADT pilha para os
métodos da deque:
Método da Pilha
Implementação da
Deque
tamanho( )
tamanho( )
estaVazia ( )
estaVazia ( )
topo( )
ultimo( )
empilha(e)
insereUltimo(e)
desempilha( )
removeUltimo( )
10
Implementação de Pilha com Deque - 2

A tabela a seguir
mapeia os métodos do
ADT pilha para os
métodos da deque:
Método da Pilha
Implementação da
Deque
tamanho( )
tamanho( )
estaVazia ( )
estaVazia ( )
topo( )
primeiro( )
empilha(e)
inserePrimeiro(e)
desempilha( )
removePrimeiro( )
11
Implementação de Fila com Deque

A tabela a seguir
mapeia os métodos do
ADT fila para os
métodos da deque:
Método da Fila
Implementação da
Deque
tamanho( )
tamanho( )
estaVazia ( )
estaVazia ( )
inicio( )
primeiro( )
insere(e)
insereUltimo(e)
remove( )
removePrimeiro( )
12
Implementação de Pilha com Deque
public class DequeStack implements Pilha {
private Deque d;
public DequeStack() {
d = new ImplemDeque();
}
public int tamanho() {
return d.tamanho();
}
public boolean estaVazia() {
return d.estaVazia();
}
public void empilha (Object obj) {
d.insereUltimo(obj);
}
13
Implementação de Pilha com Deque
public Object topo() throws PilhaVaziaException {
try {
return d.ultimo();
}
catch (DequeEmptyException ece) {
throw new PilhaVaziaException (“Pilha esta vazia!");
}
}
public Object desempilha() throws PilhaVaziaException {
try {
return d.removeUltimo();
}
catch (DequeEmptyException ece) {
throw new PilhaVaziaException (" Pilha esta vazia!");
}
}
}
14
Padrão Adapter
Interface Pilha
Classe DequeStack
Classe Deque
15
Padrão Abstract Factory
16
Padrão Abstract Factory
- CriarFila
- CriarPilha
Pilha
Implem.
Estatica
PilhaArray
Implem.
Dinamica
PilhaDin
Fila
FilaArray
FilaDin
17
Padrão Abstract Factory
- CriarFila
- CriarPilha
Pilha
Implem.
Estatica
PilhaArray
Implem.
Dinamica
PilhaDin
Fila
FilaArray
FilaDin
18