Deques - Estrutura de Dados

Prévia do material em texto

Lucas de Lima 
Turma B 
 
DEQUE 
 
Definição: 
 É um tipo abstrato de dados que generaliza uma FILA . Na ciência da 
computação, uma fila duplamente terminada é abreviada como deque ( D ouble 
E nded Que ue, no português: fila com duas saídas, mas, às vezes também é 
chamada de lista encadeada cabeça-cauda, porém esse termo é menos utilizado. O 
deque é um tipo de fila, com uma prioridade. Só é possível inserir elementos em 
ambos os lados (tanto no seu início como no seu final) mesmo que 
desproporcionalmente, desde que não ultrapasse o limite máximo. É importante 
notar que os elementos só podem ser inseridos nas extremidades do deque. Este 
tipo de estrutura de dados, pode simular tanto uma fila como uma pilha, pois 
possuem as operações elementares que permitem realizar as inserções e remoções 
que caracterizam estes dois tipos de estruturas de dados. Os deques são também 
muito usados em diversos tipos de aplicações computacionais, dada a sua 
flexibilidade no que diz respeito à inserção e remoção dos dados. 
 
Implementação: 
Um deque é implementado usualmente usando uma estrutura chamada 
deque circular, para facilitar as operações de inserção e remoção em ambas as 
extremidades. Deques circulares são duplamente encadeados, ou seja, tem duas 
extremidades onde o início e o fim do vetor são unidos. Essa estrutura, como dita 
anteriormente, facilita a inserção e remoção de elementos, por não precisar 
percorrer todo o deque para chegar no último elemento e vice versa. 
 A implementação de um deque por alocação dinâmica ou estática é feita 
definindo um tamanho máximo para o deque e duas variáveis inteiras que indicam o 
topo e a base. 
 A TAD Deque é dividida pelo total de posições em duas extremidades, onde o 
total não pode ser extrapolado, senão ocorre o estouro da memória (overflow), que 
já foi programada para uma determinada quantidade, não havendo possibilidade de 
mudança após já se ter definido o total. 
 
 
 
 
 
Exemplo de implementação com vetor: 
[3] 
 
Exemplo de implementação com listas ligadas:
[3] 
- Na implementação através de listas ligadas, a utilização de uma lista 
duplamente encadeada torna a implementação mais eficiente. 
- Remover o nó do final é mais eficiente em uma lista duplamente encadeada 
do que em uma lista simplesmente encadeada. 
 
 
 
 
 
Exemplos de implementação: 
 
Fila para compra de ingressos 
 
Um exemplo prático de Double Queue seria uma fila para compra de um ingresso, a 
pessoa que compra o ingresso sai da fila mas pode voltar com prioridade para uma 
eventual alteração ou devolução, sem precisar enfrentar a fila novamente. Da 
mesma forma, a última pessoa da fila pode desistir por algum motivo. Em ambos os 
casos, temos uma inserção/remoção no início e fim da fila, sem alterar os demais 
elementos. 
 
 
 
Histórico de Navegação 
 
-> URL no histórico de navegação, frequentemente a URL é colocada à frente da fila 
e a mais antiga removida. * 
-> Operações "desfazer" em softwares. * 
-> Vídeo DEQUE Works - Download realizado 
 
 
 
 
 
Fontes: 
[1]. https://pt.wikipedia.org/wiki/Deque_(estruturas_de_dados) 
[2]. http://www.inf.ufsc.br/~r.mello/ine5384/9-Deques.pdf 
[3]. http://osorio.wait4.org/oldsite/prog2/prog2-dequeestatico.pdf 
[4]. http://cic.unb.br/~alchieri/disciplinas/graduacao/ed/pilhas_filas_deques.pdf