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 NIL
representa uma lista vazia e CONS(h, t)
representa a lista cuja cabeça é h
e cuja cauda é t
. As funções drop(i, l)
e take(i, l)
retornam a lista l
sem seus primeiros i
elementos e os primeiros i
elementos de l
, respectivamente. Ou, se |l| < i
, eles retornam a lista vazia e l
respectivamente.
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 front
há 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|+1
e |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_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çadas. Observe que, quando uma fila de extremidade dupla contém n
elementos na lista da frente e n
elementos na lista de trás, então a invariante de desigualdade permanece satisfeita após i
inserções e d
exclusões quando (i+d) ≤ n/2
. Ou seja, no máximo n/2
podem 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 balance
que reequilibra o deque se insert'
ou tail
quebra o invariante. O método insert
e tail
podem 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 front
e de drop(i, rear)
. Isso é front' = rotateDrop(front, ceil_half_len, rear)
colocado no front'
conteúdo de front
e o conteúdo do rear
que ainda não está em rear'
. Como a eliminação de n
elementos 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_front
e tail_rear
poderiam ser removidas da representação da fila dupla.
Suporte de linguas
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 matriz múltipla e lista vinculada, respectivamente.
A partir do Java 6, o Collections Framework do Java fornece uma nova Deque
interface 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 collections
mó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::collections
inclui 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
- Implementação de deque de código aberto com segurança de tipo na Comprehensive C Archive Network
- Documentação SGI STL: deque <T, Alloc>
- Projeto de código: um estudo aprofundado do contêiner STL Deque
- Implementação de Deque em C
- Implementação de VBScript de stack, queue, deque e Red-Black Tree
- Várias implementações de deques não catenáveis em Haskell