¿Cómo implementar una cola con tres pilas?

Encontré esta pregunta en un libro de algoritmos ( Algorithms, 4th Edition de Robert Sedgewick y Kevin Wayne).

Cola con tres pilas. Implemente una cola con tres pilas para que cada operación de cola tome un número constante (en el peor de los casos) de operaciones de pila. Advertencia: alto grado de dificultad.

Sé cómo hacer una cola con 2 pilas, pero no puedo encontrar la solución con 3 pilas. Alguna idea ?

(Ah, y esto no es tarea :))

RESUMEN

• El algoritmo O (1) es conocido por 6 pilas
• El algoritmo O (1) se conoce para 3 pilas, pero el uso de una evaluación diferida que en la práctica corresponde a tener estructuras de datos internas adicionales, por lo que no constituye una solución
• Las personas cercanas a Sedgewick han confirmado que no conocen una solución de 3 paquetes dentro de todas las limitaciones de la pregunta original.

DETALLES

Hay dos implementaciones detrás de este enlace: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

Uno de ellos es O (1) con tres pilas, PERO usa ejecución lenta, lo que en la práctica crea estructuras de datos intermedios adicionales (cierres).

Otro de ellos es O (1) pero usa seis pilas. Sin embargo, funciona sin ejecución perezosa.

ACTUALIZACIÓN: El documento de Okasaki está aquí: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps y parece que en realidad usa solo 2 pilas para la versión O (1) que tiene una evaluación perezosa. El problema es que realmente se basa en una evaluación perezosa. La pregunta es si se puede traducir a un algoritmo de 3 conjuntos sin una evaluación diferida.

ACTUALIZACIÓN: Otro algoritmo relacionado se describe en el documento "Stacks versus Deques" de Holger Petersen, publicado en la 7ma Conferencia Anual sobre Computación y Combinatoria. Puedes encontrar el artículo de Google Books. Consulte las páginas 225-226. Pero el algoritmo no es en realidad una simulación en tiempo real, es una simulación en tiempo lineal de una cola de doble extremo en tres pilas.

gusbro: "Como dijo @Leonel hace unos días, pensé que sería justo consultar con el profesor Sedgewick si conocía una solución o si hubo algún error. Así que le escribí. Acabo de recibir una respuesta (aunque no de él mismo, pero de un colega de Princeton), así que me gusta compartir con todos ustedes. Básicamente dijo que no sabía de algoritmos que usaran tres pilas Y las otras restricciones impuestas (como no usar evaluación perezosa). Sabía que un algoritmo usaba 6 pilas como ya sabemos mirando las respuestas aquí. Así que supongo que la pregunta aún está abierta para encontrar un algoritmo (o demostrar que no se puede encontrar uno) ".

Ok, esto es realmente difícil, y la única solución que se me ocurrió, me recuerda la solución de Kirks para la prueba de Kobayashi Maru (de alguna manera engañada): la idea es que usemos una pila de pilas (y usemos esto para modelar una lista ) Llamo a las operaciones en / dequeue y push y pop, luego obtenemos:

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

(StackX = StackY no es una copia de los contenidos, solo una copia de referencia. Es solo para describirlo fácilmente. También podría usar una matriz de 3 pilas y acceder a ellas a través del índice, allí simplemente cambiaría el valor de la variable de índice ) Todo está en O (1) en términos de operación de pila.

Y sí, sé que es discutible, porque tenemos más de 3 acumulaciones implícitas, pero tal vez les dé buenas ideas a otros.

EDITAR: Ejemplo de explicación:

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

Intenté aquí con un poco de arte ASCII para mostrar Stack1.

Cada elemento está envuelto en una pila de un solo elemento (por lo que solo tenemos una pila de pilas seguras).

Para eliminar, primero sacamos el primer elemento (la pila que contiene aquí los elementos 1 y 2). Luego haga estallar el siguiente elemento y desenvuelva allí el 1. Luego decimos que la primera pila con popa ahora es nuestra nueva Pila1. Para hablar un poco más funcional: estas son listas implementadas por pilas de 2 elementos donde el elemento superior es cdr y el primer elemento superior / inferior es auto . Los otros 2 están ayudando a las pilas.

La inserción es especialmente complicada, ya que de alguna manera tienes que sumergirte profundamente en las pilas anidadas para agregar otro elemento. Por eso Stack2 está ahí. Stack2 es siempre la pila más interna. Agregar es simplemente presionar un elemento y luego presionar sobre un nuevo Stack2 (y es por eso que no se nos permite tocar Stack2 en nuestra operación de desconexión).

Voy a intentar una prueba para demostrar que no se puede hacer.

Supongamos que hay una cola Q simulada por 3 pilas, A, B y C.

Aserciones

• ASRT0: = Además, suponga que Q puede simular operaciones {queue, dequeue} en O (1). Esto significa que existe una secuencia específica de pila de push / pops para cada operación de cola / cola que se simulará.

• Sin pérdida de generalidad, suponga que las operaciones de la cola son deterministas.

Deje que los elementos en cola en Q se numeren 1, 2, ..., en función de su orden de cola, con el primer elemento en cola en Q definido como 1, el segundo como 2, y así sucesivamente.

Definir

• Q(0) := El estado de Q cuando hay 0 elementos en Q (y, por lo tanto, 0 elementos en A, B y C)
• Q(1) := El estado de Q (y A, B y C) después de 1 operación de cola en Q(0)
• Q(n) := El estado de Q (y A, B y C) después de n operaciones de cola en Q(0)

Definir

• |Q(n)| :=el número de elementos en Q(n)(por lo tanto |Q(n)| = n)
• A(n) := El estado de la pila A cuando el estado de Q es Q(n)
• |A(n)| := la cantidad de elementos en A(n)

Y definiciones similares para las pilas B y C.

Trivialmente

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)| obviamente no tiene límites en n.

Por lo tanto, al menos uno de |A(n)|, |B(n)|o |C(n)|no está acotado en n.

WLOG1, supongamos que la pila A no tiene límites y las pilas B y C están limitadas.

Definir * B_u :=un límite superior de B * C_u :=un límite superior de C *K := B_u + C_u + 1

WLOG2, para un n tal que |A(n)| > K, seleccione K elementos de Q(n). Suponga que 1 de esos elementos está en A(n + x), para todos x >= 0, es decir, el elemento siempre está en la pila A, sin importar cuántas operaciones de cola se realicen.

• X := ese elemento

Entonces podemos definir

• Abv(n) :=El número de elementos en la pila A(n)que está por encima de X

• Blo(n) :=El número de elementos en la pila A(n)que está debajo de X

  | A (n) | = Abv (n) + Blo (n)

ASRT1 :=El número de pops necesarios para eliminar X de Q(n)al menos es al menosAbv(n)

De ( ASRT0) y ( ASRT1), ASRT2 := Abv(n)deben estar delimitados.

Si Abv(n)no está acotado, entonces si se requieren 20 colas para quitar X Q(n), requerirá al menosAbv(n)/20 pops. Lo cual es ilimitado. 20 puede ser cualquier constante.

Por lo tanto,

ASRT3 := Blo(n) = |A(n)| - Abv(n)

debe ser ilimitado.

WLOG3, podemos seleccionar los elementos K desde la parte inferior de A(n), y uno de ellos es A(n + x)para todosx >= 0

X(n) := ese elemento, para cualquier n dado

ASRT4 := Abv(n) >= |A(n)| - K

Cada vez que un elemento se pone en cola en Q(n)...

WLOG4, supongamos que B y C ya están llenos a sus límites superiores. Suponga que X(n)se ha alcanzado el límite superior para los elementos anteriores . Entonces, un nuevo elemento entra en A.

WLOG5, supongamos que como resultado, el nuevo elemento debe ingresar a continuación X(n).

ASRT5 := El número de pops requeridos para poner un elemento debajo X(n) >= Abv(X(n))

De (ASRT4), Abv(n)es ilimitado en n.

Por lo tanto, la cantidad de pops requeridos para poner un elemento debajo X(n)no tiene límites.

Esto contradice ASRT1, por lo tanto, no es posible simular una O(1)cola con 3 pilas.

Es decir

Al menos 1 pila debe ser ilimitada.

Para un elemento que permanece en esa pila, el número de elementos que se encuentran arriba debe estar limitado, o la operación de eliminación de la cola para eliminar ese elemento será ilimitada.

Sin embargo, si el número de elementos por encima está limitado, alcanzará un límite. En algún momento, un nuevo elemento debe entrar debajo de él.

Dado que siempre podemos elegir el elemento antiguo entre uno de los pocos elementos más bajos de esa pila, puede haber un número ilimitado de elementos por encima (en función del tamaño ilimitado de la pila ilimitada).

Para ingresar un nuevo elemento debajo de él, dado que hay un número ilimitado de elementos encima, se requiere un número ilimitado de elementos emergentes para colocar el nuevo elemento debajo de él.

Y de ahí la contradicción.

Hay 5 declaraciones WLOG (sin pérdida de generalidad). En cierto sentido, pueden entenderse intuitivamente como verdaderas (pero dado que son 5, puede llevar algún tiempo). La prueba formal de que no se pierde la generalidad se puede derivar, pero es extremadamente larga. Se omiten.

Admito que tal omisión podría dejar las declaraciones del WLOG en cuestión. Con la paranoia de un programador por errores, verifique las declaraciones de WLOG si lo desea.

La tercera pila también es irrelevante. Lo que importa es que hay un conjunto de pilas limitadas y un conjunto de pilas ilimitadas. El mínimo necesario para un ejemplo es de 2 pilas. El número de pilas debe ser, por supuesto, finito.

Por último, si tengo razón en que no hay pruebas, entonces debería haber una prueba inductiva más fácil disponible. Probablemente basado en lo que sucede después de cada cola (haga un seguimiento de cómo afecta el peor de los casos dado el conjunto de todos los elementos en la cola).

Nota: Esto está destinado a ser un comentario a la implementación funcional de colas en tiempo real (tiempo constante en el peor de los casos) con listas enlazadas individualmente. No puedo agregar comentarios debido a la reputación, pero sería bueno si alguien pudiera cambiar esto a un comentario agregado a la respuesta de antti.huima. Por otra parte, es algo largo para un comentario.

@ antti.huima: las listas vinculadas no son lo mismo que una pila.

• s1 = (1 2 3 4) --- una lista vinculada con 4 nodos, cada uno apuntando al de la derecha, y con los valores 1, 2, 3 y 4

• s2 = reventado (s1) --- s2 es ahora (2 3 4)

En este punto, s2 es equivalente a popped (s1), que se comporta como una pila. ¡Sin embargo, s1 todavía está disponible como referencia!

• s3 = reventado (reventado (s1)) --- s3 es (3 4)

Todavía podemos echar un vistazo a s1 para obtener 1, mientras que en una implementación de pila adecuada, el elemento 1 se ha ido de s1.

¿Qué significa esto?

• s1 es la referencia a la parte superior de la pila
• s2 es la referencia al segundo elemento de la pila
• s3 es la referencia a la tercera ...

¡Las listas enlazadas adicionales creadas ahora sirven como referencia / puntero! Un número finito de pilas no puede hacer eso.

Por lo que veo en los documentos / código, todos los algoritmos hacen uso de esta propiedad de las listas vinculadas para retener referencias.

Editar: Me refiero solo a los algoritmos de listas enlazadas 2 y 3 que hacen uso de esta propiedad de las listas enlazadas, ya que las leí primero (parecían más simples). Esto no pretende mostrar que son o no aplicables, solo para explicar que las listas vinculadas no son necesariamente idénticas. Leeré el que tiene 6 cuando esté libre. @Welbog: Gracias por la corrección.

La pereza también puede simular la funcionalidad del puntero de manera similar.

El uso de la lista vinculada resuelve un problema diferente. Esta estrategia se puede utilizar para implementar colas en tiempo real en Lisp (o al menos Lisps que insisten en construir todo desde listas enlazadas): consulte "Operaciones de cola en tiempo real en Lisp puro" (enlazado a través de los enlaces de antti.huima). También es una buena manera de diseñar listas inmutables con tiempo de operación O (1) y estructuras compartidas (inmutables).

Puedes hacerlo en tiempo constante amortizado con dos pilas:

------------- --------------
            | |
------------- --------------

Agregar O(1)y eliminar es O(1)si el lado del que quieres tomar no está vacío y de lo O(n)contrario (divide la otra pila en dos).

El truco consiste en ver que la O(n)operación solo se realizará cada O(n)vez (si se divide, por ejemplo, en mitades). Por lo tanto, el tiempo promedio para una operación es O(1)+O(n)/O(n) = O(1).

Si bien esto puede parecer un problema, si está utilizando un lenguaje imperativo con una pila basada en una matriz (la más rápida), de todos modos solo habrá amortizado el tiempo constante.