¿Dónde usaría típicamente un Deque en el software de producción?

21

Estoy bastante familiarizado con dónde usar pilas, colas y árboles en aplicaciones de software, pero nunca antes había usado una Deque (cola de doble terminación). ¿Dónde los encontraría típicamente en la naturaleza? ¿Estaría en los mismos lugares que una cola pero con gribbilies adicionales?

data-structures Ingeniero mundial
fuente
2
en.wikipedia.org/wiki/Double-ended_queue#Applications
Arseni Mourzenko
Parece que hay algo de confusión en este hilo. En internet, "deque" es una cola doble (wikipedia menciona la implementación de la lista vinculada). Sin embargo, en C ++ STL, "std :: deque" es una estructura tipo matriz implementada como una matriz de bloques de datos. Ofrece acceso aleatorio, similar a std :: vector, pero su capacidad de cambio de tamaño es más cercana a la de std :: list porque a medida que se agregan datos, agrega bloques y no reasigna y mueve los datos existentes.
DXM
1
@DXM: una deque STL sigue siendo una cola de doble extremo y proporciona operaciones más rápidas en los extremos (dependiendo de la implementación). El hecho de que también ofrezca acceso al medio no hace que su operación principal sea menos similar a la cola.
gbjbaanb
@gbjbaanb: Todo lo que digo es que si miras las interfaces públicas de 3 clases: std :: vector, std :: list (o std :: queue) y std :: deque, verás que std :: vector y std :: deque tienen una interfaz pública idéntica y una capacidad idéntica (std :: deque es un poco más flexible a expensas de una mayor huella de memoria). std :: list y std :: queue, por otro lado, se comportan más como sus contrapartes CS, lista enlazada y cola respectivamente. CS deque! = Std :: deque
DXM
Encuentro esta respuesta más práctica por shiv.mymail - stackoverflow.com/questions/3880254/…
roottraveller

Respuestas:

21

Una forma en que se usa una deque es "envejecer" los artículos. Por lo general, se usa como una función de deshacer o historial. Se inserta una nueva acción en la deque. Los artículos más antiguos están en el frente. Un límite en el tamaño de la reducción obliga a eliminar los elementos en la parte delantera en algún momento a medida que se insertan nuevos elementos (envejeciendo los elementos más antiguos). Luego proporciona una forma rápida de acceder a ambos extremos de la estructura porque conoce instantáneamente los elementos más antiguos y más nuevos para eliminar el frente y cometer la acción más antigua en O (1) o deshacer en tiempo O (1).

jmq
fuente
No creo que se usen / necesiten deques aquí. Una pila simple (quizás de tamaño limitado) es suficiente.
Konrad Rudolph,
2
@ Konrad ¿Cómo envejece los artículos en una pila simple? (es decir, ¿cómo se eliminan los comandos que son "demasiado viejos"?)
Andres F.
@AndresF. ¿La edad es independiente del tamaño de la pila? Si es así, nunca he oído hablar de esta estructura de datos. De lo contrario, se trata simplemente de una pila con un tamaño fijo que se puede implementar en términos de una reducción, o simplemente postulando una estructura de datos más simple llamada pila de tamaño fijo.
Konrad Rudolph,
Por lo tanto, las etiquetas son útiles después de todo;) Nunca he oído hablar de una pila de tamaño fijo (en el sentido que quiere decir, de eliminar el elemento más antiguo). Tiene sentido, pero no es lo que generalmente se entiende por "apilar", y queda por ver si en realidad es más simple :)
Andres F.
Esto se publicó en los comentarios de la pregunta original: en.wikipedia.org/wiki/Double-ended_queue Es solo una cola de doble finalización. Lo he usado en la práctica de la manera que describí anteriormente (por eso lo publiqué). En una verdadera pila, las únicas operaciones que debe tener son push, pop, top y peek (podríamos discutir otras, pero generalmente es así). No debe tener conocimiento de lo que está en la parte inferior de la pila o incluso cómo acceder a la parte inferior. En una "pila de tamaño fijo" simplemente generarías un desbordamiento de pila en lugar de envejecer elementos viejos cuando lo llenaras.
jmq
1

Excelente pregunta No recuerdo que nuestro curso CS 102 mencionara una sola aplicación para la cola de doble final.

Hasta el día de hoy, la única aplicación que conozco es el programador de robo de trabajo mencionado en el artículo de Wikipedia .

Funciona esencialmente de la siguiente manera:

En un modelo de procedimiento normal de un solo subproceso, cada llamada de función empuja un registro de activación en una llamada pila de llamadas . Un registro de activación contiene las variables y parámetros locales de esa llamada. Una vez que se completa la llamada al método ("retornos"), el último registro de activación se saca de la pila de llamadas.

Esto es particularmente importante porque así es como se implementa la recursividad: la estructura de la recursión se representa en el estado actual de la pila de llamadas.

Al poner en paralelo un algoritmo recursivo, podemos explotar esta propiedad reemplazando la pila de llamadas con una cola de llamadas. Cada subproceso en el cálculo obtiene su propia cola de llamadas y empuja y muestra registros de activación como en una ejecución secuencial.

Pero una vez que un subproceso ha terminado su trabajo (= su cola de llamadas está vacía), roba el trabajo de otro subproceso al eliminar un registro de activación de la cola de llamadas de ese subproceso al eliminarlo del extremo "incorrecto".

Básicamente, la cola de llamadas actúa como dos pilas de llamadas que ahora sirven a dos hilos.

Konrad Rudolph
fuente
¿Tienes una fuente para esto? Suena interesante.
kyjelly90210
1
@ Richard1987 El artículo de Wikipedia cita el artículo original. Existen varias implementaciones, por ejemplo en la implementación de robo de trabajo de extensión paralela GNU c ++ stdlib (pero el código es horrible de leer) o una implementación paralela de divide y vencerás generalizada por la tuya realmente (pero esta última usa un estilo de programación muy idiomático particular a la biblioteca y por lo tanto difícil de leer)
Konrad Rudolph