Deque é uma abreviação de Double Ended Queue (fila de duas pontas), ele pode ser utilizado para implementar estrutura do tipo fila(FIFO) e pilha(FILO). Caso não saibam o funcionamento dessas duas estruturas de dados, sugiro que leiam. Entretanto, vou abordar algumas características de ambas, a fim de comparar com o deque. Na fila de modo geral, nós adicionamos os elementos na cauda e tiramos na cabeça. A inserção dos dados é do tipo constante, o que agiliza o processo, entretanto, quando tratamos da exclusão dos dados, o Big-O passa a ser O(n) - linear, porque precisamos remanejar todos os dados para que a primeira posição não fique vazia. Enquanto isso, o deque adiciona e remove itens em qualquer direção com o desempenho aproximado O(1), segundo o python collections. Sendo assim, quando comparamos a inserção e remoção de elementos, o deque ganha em questão de performance. O deque pode se comportar como fila(até mesmo as filas de prioridade) ou pilha, com isso, nós podemos excluir e adicionar elementos tanto no início, quanto no final da estruturas.
Veja esta imagem que mostra a diferença entre as três:
A implementação de exclusão e inserção de dados nos deques podem ser realizadas de forma estática ou circular. A forma circular é muito parecida com a da fila que vimos nos resumos passados. Basicamente, a implementação deste tipo é formado por um ponteiro indicando o início e o final da fila, sendo que esta é a forma mais indicada para este tipo de estrutura de dados. Já a forma estática, não é tão indicada por ter sua notação linear O(n), devido ao reajuste das casas para inserção e exclusão de itens do início do vetor.
Aqui está um algoritmo em python com a ideia de deque.
Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!
Este resumo é baseado no curso: Estruturas de dados e algoritmos em python
Top comments (0)