Fila dupla

Na ciência da computação, uma fila dupla (abreviada para deque, pronuncia-se deck, como "cheque") é um tipo de dados abstrato que generaliza uma fila, para a qual os elementos podem ser adicionados ou removidos da frente (cabeça) ou de trás (cauda). Também é frequentemente chamada de lista encadeada head-tail, embora se refira apropriadamente a uma estrutura de dados específica implementação de um deque (veja abaixo).

Convenções de nomenclatura

Deque às vezes é escrito dequeue, mas esse uso geralmente é obsoleto na literatura técnica ou na escrita técnica porque dequeue também é um verbo que significa & #34;para remover de uma fila". No entanto, várias bibliotecas e alguns escritores, como Aho, Hopcroft e Ullman em seu livro Data Structures and Algorithms, escrevem dequeue. John Mitchell, autor de Concepts in Programming Languages, também usa essa terminologia.

Distinções e subtipos

Isso difere do tipo de dados abstratos da fila ou da lista primeiro a entrar, primeiro a sair (FIFO), em que os elementos só podem ser adicionados a uma extremidade e removidos da outra. Esta classe de dados gerais tem alguns subtipos possíveis:

• Um deque restringido de entrada é aquele onde a exclusão pode ser feita de ambas as extremidades, mas a inserção pode ser feita apenas em uma extremidade.
• Um deque restrito à saída é aquele em que a inserção pode ser feita em ambas as extremidades, mas a exclusão pode ser feita apenas de uma extremidade.

Os tipos de lista básicos e mais comuns em computação, filas e pilhas, podem ser considerados especializações de deques e podem ser implementados usando deques.

Operações

As operações básicas em um deque são enqueue e dequeue em qualquer extremidade. Também geralmente implementadas são as operações peek, que retornam o valor naquele final sem retirá-lo da fila.

Os nomes variam entre os idiomas; as principais implementações incluem:

Implementações

Existem pelo menos duas maneiras comuns de implementar eficientemente um deque: com um array dinâmico modificado ou com uma lista duplamente encadeada.

A abordagem de matriz dinâmica usa uma variante de uma matriz dinâmica que pode crescer de ambas as extremidades, às vezes chamada de array deques. Esses deques de matriz têm todas as propriedades de uma matriz dinâmica, como acesso aleatório de tempo constante, boa localidade de referência e inserção/remoção ineficiente no meio, com a adição de inserção/remoção de tempo constante amortizado em ambas as extremidades, em vez disso de apenas uma extremidade. Três implementações comuns incluem:

• Armazenar conteúdo deque em um buffer circular, e apenas redimensionar quando o buffer fica cheio. Isso diminui a frequência de redimensionamentos.
• Alocando conteúdo deque do centro da matriz subjacente, e redimensionando o array subjacente quando qualquer extremidade é alcançada. Esta abordagem pode exigir redimensionamentos mais frequentes e desperdiçar mais espaço, particularmente quando os elementos são inseridos apenas em uma extremidade.
• Armazenamento de conteúdo em vários arrays menores, alocando arrays adicionais no início ou fim conforme necessário. A indexação é implementada mantendo um array dinâmico contendo ponteiros para cada um dos arrays menores.

Implementação puramente funcional

Filas duplas também podem ser implementadas como uma estrutura de dados puramente funcional. Existem duas versões da implementação. A primeira, denominada 'deque em tempo real, é apresentada a seguir. Ele permite que a fila seja persistente com operações no pior caso O(1), mas requer listas preguiçosas com memoização. A segunda, sem listas preguiçosas nem memoização, é apresentada ao final das seções. Seu tempo amortizado é O(1) se a persistência não for usada; mas a complexidade de pior tempo de uma operação é O(n) onde estilo n é o número de elementos na fila dupla.

Lembremos que, para uma lista l, |l| denota seu comprimento, que NIL representa uma lista vazia e CONS(h, t) representa a lista cujo cabeçalho é h e cujo final é t. As funções drop(i, l) e take(i, l) retornam a lista l sem seu primeiro i elementos e os primeiros elementos i de l, respectivamente. Ou, se |l| < i, eles retornam a lista vazia e l respectivamente.

Deques em tempo real por meio de programação e reconstrução preguiçosa

Uma fila dupla é representada como um sêxtuplo (len_front, front, tail_front, len_rear, rear, tail_rear) onde front é uma lista encadeada que contém o front da fila de comprimento len_front. Da mesma forma, rear é uma lista encadeada que representa o reverso do final da fila, de comprimento len_rear. Além disso, é garantido que |front| ≤ 2|traseira|+1 e |traseira| ≤ 2|front|+1 - intuitivamente, significa que tanto a frente quanto a traseira contém entre um terço menos um e dois terços mais um dos elementos. Por fim, tail_front e tail_rear são caudas de front e de rear, permitem agendar o momento em que algumas operações preguiçosas são forçados. Observe que, quando uma fila dupla contém elementos n na lista frontal e elementos n na lista traseira, a invariante de desigualdade permanece satisfeita após i inserções e exclusões de d quando (i+d) ≤ n/2. Ou seja, no máximo operações n/2 podem acontecer entre cada rebalanceamento.

Vamos primeiro dar uma implementação das várias operações que afetam a frente do deque - contras, cabeça e cauda. Essas implementações não necessariamente respeitam a invariante. Em um segundo momento, explicaremos como modificar um deque que não satisfaz o invariante em um que o satisfaz. No entanto, eles usam a invariante, pois se a frente estiver vazia, a parte traseira terá no máximo um elemento. As operações que afetam o final da lista são definidas de forma semelhante por simetria.

vazio = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = (0, NIL, NIL, 0, NIL, NIL)diversão inserção '(x, (len_front, frente, tail_front, - Não., traseiro, Seguir) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = (len_front+1, CONTRAS(x, frente), gota(2, tail_front), - Não., traseiro, gota(2, Seguir)diversão cabeça(_ CONTRAS(h, O quê? Não. Não. Não. O quê? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = hdiversão cabeça(_ NIL, Não. Não. CONTRAS(h, NIL), O quê? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = hdiversão cauda '(len_front, CONTRAS(cabeça_frente, frente), tail_front, - Não., traseiro, Seguir) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = (len_front - Não. 1, frente, gota(2, tail_front), - Não., traseiro, gota(2, Seguir)diversão cauda '(_ NIL, Não. Não. CONTRAS(h, NIL), O quê? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = vazio

Resta explicar como definir um método balance que rebalanceie o deque se insert' ou tail quebrou a invariante. Os métodos insert e tail podem ser definidos aplicando primeiro insert' e tail' e depois aplicando saldo.

diversão equilíbrio(q como (len_front, frente, tail_front, - Não., traseiro, Seguir) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Deixa-me. soalho_alvo_len = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = (len_front + - Não.) / 2 em Deixa-me. O que se passa? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = len_front + - Não. - Não. soalho_alvo_len em se len_front > 2- Não.1 então Deixa-me. valor frente ' = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Toma.(O que se passa?, frente) valor traseiro ' = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = girar Gota(traseiro, soalho_alvo_len, frente) em (O que se passa?, frente ', frente ', soalho_alvo_len, traseiro ', traseiro ') mais se len_front > 2- Não.1 então Deixa-me. valor traseiro ' = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Toma.(soalho_alvo_len, traseiro) valor frente ' = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = girar Gota(frente, O que se passa?, traseiro) em (O que se passa?, frente ', frente ', soalho_alvo_len, traseiro ', traseiro ') mais q

Onde? rotateDrop(front, i, rear)) voltar a concatenação de front de drop(i, rear). Isso.front' = rotateDrop(front, ceil_half_len, rear) colocado em front' o conteúdo de front e o conteúdo de rear que já não está rear'. Desde a queda n elementos toma O(n)O(n)} tempo, usamos preguiça para garantir que os elementos são deixados dois por dois, com duas gotas sendo feitas durante cada tail' e cada insert' operação.

diversão girar Gota(frente, Eu..., traseiro) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = se Eu... < 2 então girar Rev.(frente, gota(Eu..., traseiro), $NIL) mais Deixa-me. $CONS(x, frente ') = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = frente em $CONS (x, girar Gota(frente ', J...2, gota(2, traseiro)

onde rotateRev(front, middle, rear) é uma função que retorna a frente, seguida pelo meio invertido, seguido pela parte traseira. Essa função também é definida usando laziness para garantir que ela possa ser calculada passo a passo, com uma etapa executada durante cada insert' e tail' e tomando um tempo constante. Esta função usa a invariante que |rear|-2|front| é 2 ou 3.

diversão girar Rev.(NIL, traseiro, um? reverso reverso(++)diversão girar Rev.(CONTRAS(x, frente), traseiro, um? CONTRAS(x, girar Rev.(frente, gota(2, traseiro), reverso reverso (Toma.(2, traseiro)++a)

onde ++ é a função que concatena duas listas.

Implementação sem preguiça

Observe que, sem a parte preguiçosa da implementação, esta seria uma implementação não persistente da fila em O(1) tempo amortizado. Nesse caso, as listas tail_front e tail_rear poderiam ser removidas da representação da fila de duas pontas.

Suporte a idiomas

Os contêineres de Ada fornecem os pacotes genéricos Ada.Containers.Vectors e Ada.Containers.Doubly_Linked_Lists, para as implementações de array dinâmico e lista vinculada, respectivamente.

A biblioteca de modelos padrão do C++ fornece os modelos de classe std::deque e std::list, para as implementações de vários arrays e listas vinculadas, respectivamente.

A partir do Java 6, o Java's Collections Framework fornece uma nova interface Deque que fornece a funcionalidade de inserção e remoção em ambas as extremidades. Ele é implementado por classes como ArrayDeque (também novo no Java 6) e LinkedList, fornecendo as implementações de array dinâmico e lista encadeada, respectivamente. No entanto, o ArrayDeque, ao contrário do seu nome, não suporta acesso aleatório.

Protótipo de Array do Javascript & As matrizes do Perl têm suporte nativo para remover (shift e pop) e adicionar (unshift e push) elementos em ambas as extremidades.

Python 2.4 introduziu o módulo collections com suporte para objetos deque. Ele é implementado usando uma lista duplamente encadeada de subarrays de comprimento fixo.

A partir do PHP 5.3, a extensão SPL do PHP contém o 'SplDoublyLinkedList' classe que pode ser usada para implementar estruturas de dados Deque. Anteriormente, para criar uma estrutura Deque, as funções de array array_shift/unshift/pop/push tinham que ser usadas.

O módulo Data.Sequence do GHC implementa uma estrutura deque eficiente e funcional em Haskell. A implementação usa árvores de 2 a 3 dedos anotadas com tamanhos. Existem outras possibilidades (rápidas) para implementar filas duplas puramente funcionais (portanto, também persistentes) (a maioria usando avaliação pesadamente preguiçosa). Kaplan e Tarjan foram os primeiros a implementar deques catenáveis confluentes persistentes ideais. Sua implementação era estritamente puramente funcional no sentido de que não usava avaliação preguiçosa. Okasaki simplificou a estrutura de dados usando avaliação preguiçosa com uma estrutura de dados inicializada e degradando os limites de desempenho do pior caso para amortizado. Kaplan, Okasaki e Tarjan produziram uma versão amortizada mais simples, sem inicialização, que pode ser implementada usando avaliação preguiçosa ou mais eficientemente usando mutação de uma maneira mais ampla, mas ainda restrita. Mihaesau e Tarjan criaram uma implementação puramente funcional mais simples (mas ainda altamente complexa) de deques catenáveis, e também uma implementação muito mais simples de deques não catenáveis estritamente puramente funcionais, ambos com limites ótimos de pior caso.

O std::collections de

Rust inclui VecDeque, que implementa uma fila dupla usando um buffer de anel expansível.

Complexidade

• Em uma implementação de lista dupla duplamente vinculada e assumindo nenhuma sobrecarga/desalocação, a complexidade do tempo de todas as operações deque é O(1). Além disso, a complexidade do tempo de inserção ou exclusão no meio, dada um iterador, é O(1); no entanto, a complexidade do tempo de acesso aleatório pelo índice é O(n).
• Em um array crescente, a complexidade do tempo amortizado de todas as operações deque é O(1). Além disso, a complexidade do tempo de acesso aleatório por índice é O(1); mas a complexidade do tempo de inserção ou exclusão no meio é O(n).

Aplicativos

Uma fila dupla pode ser usada para armazenar o histórico de navegação: novos sites são adicionados ao final da fila, enquanto as entradas mais antigas serão excluídas quando a história é muito grande. Quando um usuário pede para limpar o histórico de navegação pela última hora, as entradas mais recentemente adicionadas são removidas.

Um exemplo em que um deque pode ser usado é o algoritmo de roubo de trabalho. Este algoritmo implementa escalonamento de tarefas para vários processadores. Um deque separado com threads a serem executados é mantido para cada processador. Para executar a próxima thread, o processador obtém o primeiro elemento do deque (usando a operação de deque "remover primeiro elemento"). Se a thread atual bifurcar, ela é colocada de volta na frente do deque ("inserir elemento na frente") e uma nova thread é executada. Quando um dos processadores termina a execução de seus próprios threads (ou seja, seu deque está vazio), ele pode "roubar" uma thread de outro processador: pega o último elemento do deque de outro processador ("remove last element") e o executa. O algoritmo de roubo de trabalho é usado pela biblioteca Threading Building Blocks (TBB) da Intel para programação paralela.