Onde normalmente eu usaria um Deque em software de produção?

21

Estou bastante familiarizado com onde usar pilhas, filas e árvores em aplicativos de software, mas nunca usei um Deque (fila dupla dupla) antes. Onde eu normalmente os encontraria na natureza? Estaria nos mesmos lugares que uma Fila, mas com outros itens?

data-structures Engenheiro Mundial
fonte
2
en.wikipedia.org/wiki/Double-ended_queue#Applications
Arseni Mourzenko 8/12/12
parece que há alguma confusão neste tópico. Na internet, o "deque" é uma fila dupla (a Wikipedia menciona a implementação da lista vinculada). No entanto, no C ++ STL, "std :: deque" é uma estrutura semelhante a uma matriz implementada como uma matriz de blocos de dados. Ele oferece acesso aleatório, semelhante ao std :: vector, mas sua capacidade de redimensionamento é mais próxima da std :: list porque, à medida que os dados são adicionados, ele adiciona blocos e não realoca e move os dados existentes.
DXM
1
@ DXM: um deque STL ainda é uma fila dupla e fornece operações mais rápidas no final (dependendo da implementação). O fato de oferecer acesso ao meio também não torna sua operação principal menos parecida com uma fila.
Gbjbaanb
@gbjbaanb: Tudo o que estou dizendo é que se você olhar para interfaces públicas de 3 classes: std :: vector, std :: list (ou std :: fila) e std :: deque, você verá esse std :: vector e std :: deque têm interface pública idêntica e capacidade idêntica (std :: deque é um pouco mais flexível às custas de maior espaço de memória). Por outro lado, std :: list e std :: queue se comportam mais como suas contrapartes de CS, lista vinculada e fila, respectivamente. CS deque! = Std :: deque
DXM
Acho que esta resposta é mais prática por shiv.mymail - stackoverflow.com/questions/3880254/…
roottraveller

Respostas:

21

Uma maneira de usar o deque é "envelhecer" os itens. Geralmente é usado como um recurso de desfazer ou histórico. Uma nova ação é inserida no deque. Os itens mais antigos estão na frente. Um limite no tamanho do deque força os itens na frente a serem removidos em algum momento à medida que novos itens são inseridos (envelhecendo os itens mais antigos). Ele fornece uma maneira rápida de acessar as duas extremidades da estrutura, porque você conhece instantaneamente os itens mais antigos e os mais novos para remover a frente e confirmar a ação mais antiga em O (1) ou desfazer em O (1).

jmq
fonte
Eu não acho que deques são usados ​​/ necessários aqui. Uma pilha simples (talvez com tamanho limitado) é suficiente.
Konrad Rudolph
2
@ Konrad Como você envelhece itens em uma pilha simples? (ou seja, como você remove comandos que são "muito antigos"?)
Andres F.
@AndresF. A idade é independente do tamanho da pilha? Nesse caso, nunca ouvi falar dessa estrutura de dados. Caso contrário, é simplesmente uma pilha com tamanho fixo que pode ser implementada em termos de deque, ou simplesmente postulando uma estrutura de dados mais simples chamada pilha de tamanho fixo.
Konrad Rudolph
Afinal, os deques são úteis;) Nunca ouvi falar de uma pilha de tamanho fixo (no sentido que você quer dizer, de remover o item mais antigo). Faz sentido, mas não é o que geralmente significa "pilha", e se é restos realmente mais simples para ser visto :)
Andres F.
Isso foi publicado nos comentários da pergunta original: en.wikipedia.org/wiki/Double-ended_queue É apenas uma fila dupla. Usei-o na prática da maneira descrita acima (e foi por isso que o publiquei). Em uma pilha verdadeira, as únicas operações que você deve ter são push, pop, top e peek (poderíamos argumentar outras, mas geralmente é isso). Você não deve ter conhecimento do que está no fundo da pilha ou mesmo de como acessá-lo. Em uma "pilha de tamanho fixo", você geraria excesso de pilha em vez de envelhecer itens antigos quando a preenchesse.
JMQ
1

Excelente pergunta. Não me lembro do curso CS 102 mencionando um único aplicativo para a fila dupla.

Até hoje, o único aplicativo que conheço é o agendador de roubo de trabalho mencionado no artigo da Wikipedia .

Funciona essencialmente da seguinte maneira:

Em um modelo de procedimento normal e de thread único, toda chamada de função envia um registro de ativação para a chamada pilha de chamadas . Um registro de ativação contém as variáveis ​​e parâmetros locais dessa chamada. Depois que a chamada para o método é concluída ("retorna"), o último registro de ativação é exibido na pilha de chamadas.

Isso é particularmente importante porque é assim que a recursão é implementada: a estrutura da recursão é representada no estado atual da pilha de chamadas.

Ao paralelizar um algoritmo recursivo, podemos explorar essa propriedade substituindo a pilha de chamadas por uma fila de chamadas. Cada encadeamento na computação obtém sua própria fila de chamadas e envia e lança registros de ativação como em uma execução seqüencial.

Porém, quando um segmento termina seu trabalho (= sua fila de chamadas está vazia), rouba o trabalho de outro segmento, removendo um registro de ativação da fila de chamadas desse segmento, removendo da extremidade "incorreta".

Basicamente, a fila de chamadas atua como duas pilhas de chamadas que agora atendem a dois threads.

Konrad Rudolph
fonte
Você tem uma fonte para isso? Soa interessante.
Kyjelly90210
1
@ Richard1987 O artigo da Wikipedia cita o artigo original. Existem várias implementações, por exemplo, na implementação de roubo de trabalho de extensão paralela GNU c ++ stdlib (mas o código é horrível de ler) ou uma implementação paralela de dividir e conquistar generalizada pelos seus verdadeiramente (mas a última usa um estilo de programação muito idiomático em particular para a biblioteca e, portanto, difícil de ler)
Konrad Rudolph