algorithm - nodos - pilas y colas en c++

¿Cómo implementar una cola con tres pilas?

Question

Me encontré con 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 (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 :))

Answer 1

Nota: Esto debe ser un comentario para la implementación funcional de colas en tiempo real (caso de peor tiempo constante) 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 por 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 manteniendo 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 para 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 al tercero ...

¡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 enlazadas para retener referencias.

Editar: me refiero solo a los algoritmos de las 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 estoy 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 enlazada resuelve un problema diferente. Esta estrategia se puede usar 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 Pure Lisp" (enlazado a través de los enlaces de antti.huima). También es una buena forma de diseñar listas inmutables con O (1) tiempo de operación y estructuras compartidas (inmutables).

Answer 2

Ok, esto es realmente difícil, y la única solución que pude encontrar, me recuerda la solución de Kirks a la prueba Kobayashi Maru (de alguna manera engañada): La idea es que usemos pilas de pilas (y usamos 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. 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 stack-operation-terms.

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

EDITAR: Ejemplo de explicación:

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

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

Cada elemento está envuelto en una sola pila de elementos (por lo que solo tenemos una pila de pilas segura).

Como veis para eliminar, primero mostramos el primer elemento (la pila que contiene el elemento 1 y 2). A continuación, extraiga el siguiente elemento y desenvuelva el 1. Luego, diremos que la primera pila de pope es ahora nuestra nueva Stack1. Para hablar un poco más funcional, estas listas se implementan mediante pilas de 2 elementos donde el elemento superior es cdr y el primer elemento / arriba es el coche . Los otros 2 están ayudando a las pilas.

Esp complicado es la inserción, ya que de alguna manera tiene que sumergirse profundamente en las pilas anidadas para agregar otro elemento. Es por eso que Stack2 está ahí. Stack2 es siempre la pila más interna. Agregar es simplemente presionar un elemento y luego presionar un nuevo Stack2 (y es por eso que no podemos tocar Stack2 en nuestra operación de dequeue).

Answer 3

Puedes hacerlo en tiempo constante amortizado con dos pilas:

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

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

El truco es ver que la operación O(n) solo se realizará cada O(n) tiempo (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 arreglos (el más rápido), de todos modos solo habrá amortizado el tiempo constante.

Answer 4

RESUMEN

• El algoritmo O (1) es conocido por 6 pilas
• El algoritmo O (1) es conocido por 3 acumulaciones, pero el uso de 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 están al tanto de una solución de 3 acumulaciones 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 diferida, que en la práctica crea estructuras de datos intermedias adicionales (cierres).

Otro de ellos es O (1) pero usa Pilas SEIS. Sin embargo, funciona sin ejecución diferida.

ACTUALIZACIÓN: El artículo de Okasaki está aquí: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps y parece que en realidad solo usa 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 pilas sin 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 de Computación y Combinatoria. Puede encontrar el artículo de Google Books. Consulte las páginas 225-226. Pero el algoritmo no es en realidad simulación en tiempo real, es simulación en tiempo lineal de una cola de doble extremo en tres pilas.

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

Answer 5

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.

Afirmaciones

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

• Sin pérdida de generalidad, supongamos que las operaciones de 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 que se pone en cola en Q se define 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)| := |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)| := |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 tiene límites en n.

WLOG1 , supongamos que la pila A no está limitada 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 una n tal que |A(n)| > K |A(n)| > K , selecciona elementos K de Q(n) . Supongamos que 1 de esos elementos está en A(n + x) , para todo x >= 0 , es decir, el elemento siempre está en la pila A sin importar cuántas operaciones de cola se hagan.

• 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) := la cantidad de elementos en la pila A(n) que está debajo de X

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

ASRT1 := El número de pops requerido para delecuar X de Q(n) es al menos Abv(n)

Desde ( ASRT0 ) y ( ASRT1 ), ASRT2 := Abv(n) debe estar limitado.

Si Abv(n) no tiene límites, entonces si se requieren 20 dequeues para eliminar a X de Q(n) , se requerirá al menos Abv(n)/20 pops. Que no tiene límites 20 puede ser cualquier constante.

Por lo tanto,

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

debe ser ilimitado.

WLOG3 , podemos seleccionar los elementos K de la parte inferior de A(n) , y uno de ellos está en A(n + x) para todo x >= 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. Supongamos que se ha alcanzado el límite superior para los elementos por encima de X(n) . Entonces, un nuevo elemento entra en A.

WLOG5 , suponga que como resultado, el nuevo elemento debe ingresar debajo de X(n) .

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

De (ASRT4) , Abv(n) no tiene límites en n.

Por lo tanto, el número de pops necesarios para poner un elemento debajo de X(n) no tiene límites.

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

Es decir

Al menos 1 pila debe ser ilimitada.

Para un elemento que permanezca en esa pila, el número de elementos encima de él debe estar limitado, o la operación de eliminación de la cola para eliminar ese elemento no tendrá límites.

Sin embargo, si el número de elementos arriba está limitado, entonces alcanzará un límite. En algún punto, un nuevo elemento debe ingresar debajo de él.

Como 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 encima (según el 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 pops para colocar el nuevo elemento debajo de él.

Y así la contradicción.

Hay 5 declaraciones WLOG (sin pérdida de generalidad). En cierto sentido, se puede entender intuitivamente que son verdaderas (pero dado que son 5, podría llevar algo de tiempo). La prueba formal de que no se pierde ninguna generalidad puede derivarse, pero es extremadamente larga. Se omiten.

Admito que tal omisión podría dejar las declaraciones de WLOG en cuestión. Con la paranoia de un programador para los 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 2 pilas. La cantidad de pilas debe ser, por supuesto, finita.

Por último, si estoy en lo cierto de 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 (lleve un registro de cómo afecta el peor caso de dequeue dado el conjunto de todos los elementos en la cola).