Cómo implementar una cola con tres pilas?

Ok, esto es realmente difícil, y la única solución que se me ocurrió, me recuerda de la solución de Kirks a la prueba de Kobayashi Maru (de alguna manera engañada): La idea es que usemos pila de pilas (y utilicemos esto para modelar una lista). Llamo a las operaciones en / dequeue y push y pop, entonces 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 del contenido, solo una copia de la referencia. Es sólo para describirlo fácil. También podría usar una matriz de 3 pilas y acceder a ellas a través de index, allí lo haría simplemente cambie el valor de la variable índice). Todo está en O (1) en términos de operación de pila.

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

EDITAR: Explicación ejemplo:

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

Probé 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 typesafe).

Usted ve para eliminar primero pop el primero elemento (la pila que contiene aquí los elementos 1 y 2). Luego pop el siguiente elemento y desenvolver allí el 1. Después decimos que el primer stack poped es ahora nuestro nuevo Stack1. Para hablar un poco más funcional - estas son listas implementadas por pilas de 2 elementos donde el elemento superior ist cdr y el primer elemento/por debajo de la parte superior es car. Los otros 2 están ayudando a las pilas.

Esp complicado es la inserción, 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 entonces simplemente empujar un elemento y luego empujar ontop un nuevo Stack2 (y es por eso que no se nos permite tocar Stack2 en nuestra operación de desqueue).

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

Supongamos que hay una cola Q que se simula con 3 pilas, A, B y C.

Aserciones

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

• Sin pérdida de generalidad, supongamos que las operaciones de cola son determinista.

Que los elementos en cola en Q sean numerados 1, 2, ..., basado en 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)| := 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)| := el número 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)| es obviamente ilimitado en n.

Por lo Tanto, al menos uno de |A(n)|, |B(n)| o |C(n)| es acotada en n.

WLOG1, supongamos que la pila A es ilimitada y las pilas B y C son 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). Supongamos 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á por debajo de X

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

ASRT1 := El número de COP necesario para eliminar X de Q(n) es al menos Abv(n)

De (ASRT0) y (ASRT1), ASRT2 := Abv(n) debe estar acotada.

Si Abv(n) es ilimitado, entonces si se requieren 20 dequeues para dequeue X de Q(n), requerirá al menos Abv(n)/20 aparecer. 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 todos x >= 0

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

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

Siempre que un elemento esté en cola en Q(n)...

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

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

ASRT5 := El número de COP necesario para poner un elemento por debajo de X(n) >= Abv(X(n))

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

Por lo tanto, el número de COP requerido para poner un elemento por debajo de X(n) no está limitado.

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

Es decir,

Al menos 1 pila debe ser ilimitada.

Para un elemento que permanece en esa pila, el número de elementos por encima de él debe estar acotado, o la operación de desqueue para eliminar ese elemento no estará acotada.

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

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

Para introducir un nuevo elemento debajo de él, ya que hay un número ilimitado de elementos encima de él, se requiere un número ilimitado de pops para poner el nuevo elemento debajo de él.

Y así la contradicción.

Hay 5 sentencias WLOG (Sin pérdida de generalidad). En cierto sentido, se pueden entender intuitivamente como verdaderas (pero dado que son 5, puede tomar algún 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 WLOG en cuestión. Con la paranoia de un programador por los errores, por favor verifique las declaraciones 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. 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 (mantenga un registro de cómo afecta el peor caso de dequeue 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 ( en el peor caso de 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 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 enlazada con 4 nodos, cada uno apuntando al a la derecha, y valores de retención 1, 2, 3 y 4

• S2 = popped (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 = popped(popped (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 listas enlazadas para retener referencias.

Edit: Me refiero solo a los algoritmos de lista enlazada 2 y 3 que hacen uso de esta propiedad de listas enlazadas, como las leí primero (parecían más simples). Esto no pretende mostrar que son o no son aplicables, solo para explicar que las listas enlazadas 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 enlazada resuelve un problema diferente. Esta estrategia se puede utilizar para implementar colas en tiempo real en Lisp (O al menos Lisp que insisten en construir todo desde listas enlazadas): Refiérase a "Operaciones de Cola en Tiempo Real en Pure Lisp" (enlazadas a través de antti.enlaces de huima). También es una buena manera de diseñar listas inmutables con O (1) tiempo de operación y estructuras compartidas (inmutables).

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) de lo 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 verse como un problema, si está utilizando un lenguaje imperativo con una matriz basado en pila (más rápido), usted va a tener solo amortizado tiempo constante de todos modos.