¿Hay algún algoritmo interesante que utilice tanto un stack como un cola (deque) ADT?

Question

A menudo usamos stacks o colas en nuestros algoritmos, pero ¿hay algún caso en el que usemos una lista doblemente enlazada para implementar tanto una pila como una cola en el algoritmo? Por ejemplo, en una etapa, presionamos() 6 elementos en la pila, hacemos pop() 2 elementos y luego dequeueamos() el resto de los elementos (4) de la cola de la lista doblemente enlazada. Lo que busco son algoritmos oscuros e interesantes que implementan algo en este método, o incluso más extraño. Pseudocódigo, enlaces y explicaciones serían agradables.

Answer 1

El Melkman algoritmo(para el cálculo de la envolvente convexa de un simple línea poligonal en el tiempo lineal) utiliza un cola de doble extremo (aka deque) para almacenar un casco incremental para los vértices ya procesados .

Input: a simple polyline W with n vertices V[i] 

    Put first 3 vertices onto deque D so that: 
    a) 3rd vertex V[2] is at bottom and top of D 
    b) on D they form a counterclockwise (ccw) triangle 

    While there are more polyline vertices of W to process 
    Get the next vertex V[i] 
    { 
     Note that: 
     a) D is the convex hull of already processed vertices 
     b) D[bot] = D[top] = the last vertex added to D 

     // Test if V[i] is inside D (as a polygon) 
     If V[i] is left of D[bot]D[bot+1] and D[top-1]D[top] 
      Skip V[i] and Continue with the next vertex 

     // Get the tangent to the bottom 
     While V[i] is right of D[bot]D[bot+1] 
      Remove D[bot] from the bottom of D 
     Insert V[i] at the bottom of D 

     // Get the tangent to the top 
     While V[i] is right of D[top-1]D[top] 
      Pop D[top] from the top of D 
     Push V[i] onto the top of D 
    } 

    Output: D = the ccw convex hull of W. 

Fuente: http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm

Joe Mitchell: Melkman’s Convex Hull Algorithm (PDF)

Answer 2

Esta estructura se llama Deque, que es una cola donde los elementos se pueden agregar o eliminar de la cabeza o la cola. Ver más en 1.

Answer 3

Podemos modificar búsqueda en anchura (que por lo general se utiliza para encontrar pathes más cortos en un gráfico con los bordes 1 ponderados) a trabajar con 0-1 gráficos (es decir, gráfico con bordes de 0 y 1 pesos). Podemos hacerlo de la siguiente manera: cuando usamos 1-edge agregamos el vértice a la parte posterior y cuando usamos 0-edge agregamos el vértice al principio.

Answer 4

No estoy seguro de si esto califica, pero puede usar una cola con prioridad doble para aplicar quicksort a un archivo demasiado grande para caber en la memoria. La idea es que en una estrategia rápida regular, elijas un elemento como pivote, luego dividas los elementos en tres grupos: elementos menores que el pivote, elementos iguales al pivote y elementos mayores que el pivote. Si no puede incluir todos los elementos en la memoria a la vez, puede adaptar esta solución de la siguiente manera. En lugar de elegir un solo elemento como pivote, elija una gran cantidad de elementos (por ejemplo, cuantos puede caber en la RAM) e insértelos en una cola de prioridad de doble extremo. Luego, escanee el resto de los elementos de a uno por vez. Si el elemento es menor que el elemento más pequeño de la cola de prioridad de doble extremo, colóquelo en el grupo de elementos más pequeño que todos los pivotes. Si es más grande que el elemento más grande de la cola de prioridad, póngalo en un grupo de elementos mayor que los pivotes. De lo contrario, inserte el elemento en la cola de prioridad de doble extremo y luego expulse el elemento más pequeño o más grande de la cola y colóquelo en el grupo apropiado. Una vez que haya terminado de hacer esto, habrá dividido los elementos en tres partes: un grupo de elementos pequeños que luego se pueden ordenar recursivamente, un grupo de elementos en el medio que ahora están completamente ordenados (ya que si los quita todos) de la cola de prioridad de doble terminación se extraerán en orden ordenado) y un grupo de elementos mayor que los elementos intermedios que también se pueden ordenar.

Para obtener más información sobre este algoritmo y las colas de prioridad de doble extremo en general, considere buscar en this link un capítulo sobre el tema.