Fila dupla - Double-ended queue

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

Convenções de nomenclatura

Deque às vezes é escrito dequeue , mas esse uso é geralmente descontinuado na literatura técnica ou na redação técnica porque dequeue também é um verbo que significa "remover de uma fila". No entanto, várias bibliotecas e alguns escritores, como Aho , Hopcroft e Ullman em seus livros-texto Estruturas e algoritmos de dados , soletram dequeue . John Mitchell , autor de Conceitos em Linguagens de Programação, 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 geral tem alguns subtipos possíveis:

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

Ambos 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 desenfileiramento são enfileirar e desenfileirar nas duas extremidades. Também geralmente implementadas são as operações de peek , que retornam o valor nessa extremidade sem retirá-lo da fila.

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

Operação nomes comuns) Ada C ++ Java Perl PHP Pitão Rubi Ferrugem JavaScript
insira o elemento na parte de trás injetar, snoc, empurrar Append push_back offerLast push array_push append push push_back push
inserir elemento na frente empurrar, contras Prepend push_front offerFirst unshift array_unshift appendleft unshift push_front unshift
remova o último elemento ejetar Delete_Last pop_back pollLast pop array_pop pop pop pop_back pop
remova o primeiro elemento pop Delete_First pop_front pollFirst shift array_shift popleft shift pop_front shift
examine o último elemento olhadinha Last_Element back peekLast $array[-1] end <obj>[-1] last back <obj>[<obj>.length - 1]
examine o primeiro elemento First_Element front peekFirst $array[0] reset <obj>[0] first front <obj>[0]

Implementações

Existem pelo menos duas maneiras comuns de implementar um deque de forma eficiente: com uma matriz dinâmica modificada ou com uma lista duplamente vinculada .

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 deques de matriz . Esses deques de matriz têm todas as propriedades de uma matriz dinâmica, como acesso aleatório em 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 de apenas um fim. Três implementações comuns incluem:

  • Armazenar o conteúdo deque em um buffer circular e apenas redimensionar quando o buffer ficar cheio. Isso diminui a frequência de redimensionamentos.
  • Alocar conteúdo deque do centro da matriz subjacente e redimensionar a matriz subjacente quando qualquer uma das extremidades for alcançada. Essa abordagem pode exigir redimensionamentos mais frequentes e desperdiçar mais espaço, principalmente 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 no final, 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. O primeiro, denominado ' deque em tempo real , é apresentado 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 . O segundo, sem listas preguiçosas nem memoização, é apresentado no 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 n é o número de elementos na fila dupla.

Lembremos que, para uma lista l, |l|denota seu comprimento, que NILrepresenta uma lista vazia e CONS(h, t)representa a lista cuja cabeça é he cuja cauda é t. As funções drop(i, l)e take(i, l)retornam a lista lsem seus primeiros ielementos e os primeiros ielementos de l, respectivamente. Ou, se |l| < i, eles retornam a lista vazia e lrespectivamente.

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

Uma fila de extremidade dupla é representada como um sêxtuplo, (len_front, front, tail_front, len_rear, rear, tail_rear)onde fronthá uma lista vinculada que contém a frente da fila de comprimento len_front. Da mesma forma, rearé uma lista encadeada que representa o reverso da parte traseira da fila, de comprimento len_rear. Além disso, é garantido que |front| ≤ 2|rear|+1e |rear| ≤ 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_fronte tail_rearsão caudas de fronte de rear, permitem agendar o momento em que algumas operações preguiçosas são forçadas. Observe que, quando uma fila de extremidade dupla contém nelementos na lista da frente e nelementos na lista de trás, então a invariante de desigualdade permanece satisfeita após iinserções e dexclusões quando (i+d) ≤ n/2. Ou seja, no máximo n/2podem ocorrer operações entre cada rebalanceamento.

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

empty = (0, NIL, NIL, 0, NIL, NIL)
fun insert'(x, (len_front, front, tail_front, len_rear, rear, tail_rear)) =
  (len_front+1, CONS(x, front), drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun head((_, CONS(h, _), _, _, _, _)) = h
fun head((_, NIL, _, _, CONS(h, NIL), _)) = h
fun tail'((len_front, CONS(head_front, front), tail_front, len_rear, rear, tail_rear)) =
  (len_front - 1, front, drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty

Resta explicar como definir um método balanceque reequilibra o deque se insert'ou tailquebra o invariante. O método inserte tailpodem ser definidos por primeiro aplicar insert'e tail'e, em seguida, aplicar balance.

fun balance(q as (len_front, front, tail_front, len_rear, rear, tail_rear)) =
  let floor_half_len = (len_front + len_rear) / 2 in
  let ceil_half_len = len_front + len_rear - floor_half_len in
  if len_front > 2*len_rear+1 then
    let val front' = take(ceil_half_len, front)
        val rear' = rotateDrop(rear, floor_half_len, front)
    in (ceil_half_len, front', front', floor_half_len, rear', rear')
  else if len_front > 2*len_rear+1 then
    let val rear' = take(floor_half_len, rear)
        val front' = rotateDrop(front, ceil_half_len, rear)
    in (ceil_half_len, front', front', floor_half_len, rear', rear')
  else q

onde rotateDrop(front, i, rear))retorna a concatenação de fronte de drop(i, rear). Isso é front' = rotateDrop(front, ceil_half_len, rear)colocado no front'conteúdo de fronte o conteúdo do rearque ainda não está em rear'. Como a eliminação de nelementos leva tempo, usamos a preguiça para garantir que os elementos sejam descartados dois a dois, com duas quedas sendo feitas durante cada operação. tail'insert'

fun rotateDrop(front, i, rear) =
  if i < 2 then rotateRev(front, drop(i, rear), $NIL)
  else let $CONS(x, front') = front in
    $CONS (x, rotateDrop(front', j-2, drop(2, rear)))

onde rotateRev(front, middle, rear)é uma função que retorna a frente, seguido pelo meio invertido, seguido pela parte traseira. Esta função também é definida utilizando preguiça para garantir que ele pode ser computada passo a passo, com um passo executado durante cada insert'e tail'e tendo uma constante de tempo. Esta função usa o invariante |rear|-2|front|2 ou 3.

fun rotateRev(NIL, rear, a)=
  reverse(rear++a)
fun rotateRev(CONS(x, front), rear, a)=
  CONS(x, rotateRev(front, drop(2, rear), reverse (take(2, rear))++a))

onde ++está a função concatenando 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_fronte tail_rearpoderiam ser removidas da representação da fila dupla.

Suporte de linguas

Os contêineres de Ada fornecem os pacotes genéricos Ada.Containers.Vectorse 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::dequee std::list, para as implementações de matriz múltipla e lista vinculada, respectivamente.

A partir do Java 6, o Collections Framework do Java fornece uma nova Dequeinterface 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 a matriz dinâmica e as implementações de lista vinculada, respectivamente. No entanto, o ArrayDeque, ao contrário do seu nome, não suporta acesso aleatório.

O protótipo de array de Javascript e os arrays de 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 collectionsmódulo com suporte para objetos deque . Ele é implementado usando uma lista duplamente vinculada de submatrizes de comprimento fixo.

A partir do PHP 5.3, a extensão SPL do PHP contém a classe 'SplDoublyLinkedList' que pode ser usada para implementar estruturas de dados Deque. Anteriormente, para fazer 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 funcional e eficiente 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 muito lenta ). Kaplan e Tarjan foram os primeiros a implementar deques catenáveis ​​confluentemente persistentes ideais. Sua implementação era estritamente funcional, no sentido de que não utilizava 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 o amortizado. Kaplan, Okasaki e Tarjan produziram uma versão mais simples, não bootstrapped e amortizada 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 mais simples (mas ainda altamente complexa) estritamente puramente funcional de deques catenáveis, e também uma implementação muito mais simples de deques não catenáveis ​​estritamente funcionais, ambos os quais têm limites ótimos de pior caso.

Rust std::collectionsinclui VecDeque, que implementa uma fila dupla usando um buffer em anel que pode ser ampliado.

Complexidade

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

Formulários

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

Veja também

Referências

links externos