Una pila, dos colas

antecedentes

Hace varios años, cuando era estudiante universitario, nos dieron una tarea de análisis amortizado. No pude resolver uno de los problemas. Lo había pedido en teoría teórica , pero no se obtuvieron resultados satisfactorios. Recuerdo que el curso TA insistió en algo que no pudo probar, y dijo que olvidó la prueba, y ... [sabes qué].

Hoy recordé el problema. Todavía estaba ansioso por saberlo, así que aquí está ...

La pregunta

¿Es posible implementar una pila usando dos colas , para que las operaciones PUSH y POP se ejecuten en el tiempo amortizado O (1) ? En caso afirmativo, ¿podría decirme cómo?

Nota: La situación es bastante fácil si queremos implementar una cola con dos pilas (con las operaciones ENQUEUE y DEQUEUE correspondientes ). Por favor, observe la diferencia.

PD: El problema anterior no es la tarea en sí. La tarea no requería límites inferiores; solo una implementación y el análisis del tiempo de ejecución.

No tengo una respuesta real, pero aquí hay algunas pruebas de que el problema está abierto:

• No se menciona en Ming Li, Luc Longpré y Paul MB Vitányi, "El poder de la cola", Structures 1986, que considera varias otras simulaciones estrechamente relacionadas.

• No se menciona en Martin Hühne, "Sobre el poder de varias colas", Theor. Comp. Sci. 1993, un documento de seguimiento.

• No se menciona en Holger Petersen, "Stacks versus Deques", COCOON 2001.

• Burton Rosenberg, "Rápido reconocimiento no determinista de lenguajes libres de contexto utilizando dos colas", Inform. Proc. Letón. 1998, proporciona un algoritmo de dos colas O (n log n) para reconocer cualquier CFL usando dos colas. Pero un autómata pushdown no determinista puede reconocer CFL en tiempo lineal. Entonces, si hubiera una simulación de una pila con dos colas más rápido que O (log n) por operación, Rosenberg y sus árbitros deberían haberlo sabido.

La respuesta a continuación es 'trampa', ya que si bien no usa ningún espacio entre operaciones, las operaciones en sí pueden usar más de espacio. Vea en otra parte de este hilo una respuesta que no tiene este problema.$O(1)$

Si bien no tengo una respuesta a su pregunta exacta, sí encontré un algoritmo que funciona en tiempo en lugar deO(n). Creo que esto es apretado, aunque no tengo una prueba. En todo caso, el algoritmo muestra que intentar probar un límite inferior deO(n)es inútil, por lo que podría ayudar a responder su pregunta.$O(\sqrt{n})$$O(n)$$O(n)$

Presento dos algoritmos, el primero es un algoritmo simple con un tiempo de ejecución para Pop y el segundo con un O ( $O(n)$tiempo de ejecución para Pop. Describo el primero principalmente por su simplicidad para que el segundo sea más fácil de entender.$O(\sqrt{n})$

Para dar más detalles: el primero no utiliza espacio adicional, tiene un peor caso (y amortizado) Push y un O ( n ) peor caso (y amortizado) Pop, pero el comportamiento del peor de los casos no siempre se activa. Dado que no utiliza ningún espacio adicional más allá de las dos colas, es ligeramente "mejor" que la solución ofrecida por Ross Snider.$O(1)$$O(n)$

El segundo usa un solo campo entero (entonces espacio extra), tiene un O ( 1 ) peor caso (y amortizado) Push y un O ( $O(1)$$O(1)$Pop amortizado. Su tiempo de ejecución es, por lo tanto, significativamente mejor que el del enfoque 'simple', pero utiliza algo de espacio extra.$O(\sqrt{n})$

El primer algoritmo

Tenemos dos colas: cola y cola s e c o n d . f i r s t será nuestra 'cola de empuje', mientras que s e c o n d será la cola que ya está en 'orden de pila'.$first$$second$$first$$second$

• El empuje se realiza simplemente colocando el parámetro en cola en .$first$
• El estallido se realiza de la siguiente manera. Si está vacío, simplemente retiramos el s e c o n d y devolvemos el resultado. De lo contrario, revertimos$first$$second$ , anexar todos de s e c o n d a f i r s t y de intercambio f i r s t y s e c o n d . Luego retiramos s e c $first$$second$$first$$first$$second$ y devolver el resultado de la retirada de cola.$second$

Código C # para el primer algoritmo

Esto debería ser bastante legible, incluso si nunca antes has visto C #. Si no sabe qué son los genéricos, simplemente reemplace todas las instancias de 'T' por 'cadena' en su mente, para una pila de cadenas.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            // Reverse first
            for (int i = 0; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();    
            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            // Append second to first
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());

            // Swap first and second
            Queue<T> temp = first; first = second; second = temp;

            return second.Dequeue();
        }
    }
}

Análisis

Obviamente, Push funciona en el tiempo . Pop puede tocar todo dentro de f i r s t y s e c o n d una cantidad constante de veces, por lo que tenemos O ( n ) en el peor caso. El algoritmo exhibe este comportamiento (por ejemplo) si uno empuja n elementos en la pila y luego realiza repetidamente una sola operación Push y una sola operación Pop en sucesión.$O(1)$$first$$second$$O(n)$$n$

El segundo algoritmo

Tenemos dos colas: cola y cola s e c o n d . f i r s t será nuestra 'cola de empuje', mientras que s e c o n d será la cola que ya está en 'orden de pila'.$first$$second$$first$$second$

Esta es una versión adaptada del primer algoritmo, en el que no "barajamos" inmediatamente el contenido de en s e c o $first$ . En cambio, si f i r s t contiene un número suficientemente pequeño de elementos en comparación con s e c o n d (es decir, la raíz cuadrada del número de elementos en s e c o n d ), solo reorganizamos f i r s t en orden de pila y no lo fusiones$second$$first$$second$$second$$first$ .$second$

• Se sigue presionando simplemente colocando el parámetro en cola en .$first$
• El estallido se realiza de la siguiente manera. Si está vacío, simplemente retiramos el s e c o n d y devolvemos el resultado. De lo contrario, reorganizamos los contenidos de f i r s t para que estén en orden de pila. Si | f i r s t | < $first$$second$$first$simplemente retiramosfirsty devolvemos el resultado. De lo contrario, añadimosseconda$|first| < \sqrt{|second|}$$first$$second$ , intercambiamos f i r s t y s e c o n d , retiramos de la cola s e c o n d y devolvemos el resultado.$first$$first$$second$$second$

Código C # para el primer algoritmo

Esto debería ser bastante legible, incluso si nunca antes has visto C #. Si no sabe qué son los genéricos, simplemente reemplace todas las instancias de 'T' por 'cadena' en su mente, para una pila de cadenas.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    int unsortedPart = 0;
    public void Push(T value) {
        unsortedPart++;
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            for (int i = nrOfItemsInFirst - unsortedPart - 1; i >= 0; i--)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - unsortedPart; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            unsortedPart = 0;
            if (first.Count * first.Count < second.Count)
                return first.Dequeue();
            else {
                while (second.Count > 0)
                    first.Enqueue(second.Dequeue());

                Queue<T> temp = first; first = second; second = temp;

                return second.Dequeue();
            }
        }
    }
}

Análisis

Obviamente, Push funciona en el tiempo .$O(1)$

Pop funciona en tiempo amortizado. Hay dos casos: si| first| <$O(\sqrt{n})$$|first| < \sqrt{|second|}$, luego barajamos en orden de pila en O ( | f i r s t | ) = O ( $first$tiempo. Si| first| ≥$O(|first|) = O(\sqrt{n})$, entonces debemos haber tenido al menos$|first| \geq \sqrt{|second|}$ llama a Push. Por lo tanto, solo podemos golpear este caso cada$\sqrt{n}$ llamadas a Push y Pop. El tiempo real de ejecución para este caso esO(n), por lo que el tiempo amortizado esO($\sqrt{n}$$O(n)$.$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

Nota final

Es posible eliminar la variable adicional a costa de hacer Pop an operación, haciendo que Pop reorganicefirsten cada llamada en lugar de hacer que Push haga todo el trabajo.$O(\sqrt{n})$$first$

Después de algunos comentarios sobre mi respuesta anterior, me quedó claro que estaba haciendo más o menos trampa: usé espacio adicional ( espacio extra en el segundo algoritmo) durante la ejecución de mi método Pop.$O(\sqrt{n})$

El siguiente algoritmo no utiliza ningún espacio adicional entre métodos y solo espacio adicional durante la ejecución de Push y Pop. Empujar tiene una O ( $O(1)$tiempo de ejecución amortizado y Pop tiene unO(1)peor tiempo de ejecución (y amortizado).$O(\sqrt{n})$$O(1)$

Nota para los moderadores: no estoy completamente seguro de si mi decisión de hacer que esta sea una respuesta separada es correcta. Pensé que no debería eliminar mi respuesta original ya que aún podría ser de alguna relevancia para la pregunta.

El algoritmo

Tenemos dos colas: cola y cola s e c o n d . f i r s t será nuestro 'caché', mientras que s e c o n d será nuestro 'almacenamiento' principal. Ambas colas siempre estarán en 'orden de pila'. f i r s t contendrá los elementos en la parte superior de la pila y s e c o n s t siempre será como máximo la raíz cuadrada de s e $first$$second$$first$$second$$first$ contendrá los elementos en la parte inferior de la pila. El tamaño de f i $second$$first$ .$second$

• El empuje se realiza 'insertando' el parámetro al comienzo de la cola de la siguiente manera: colocamos el parámetro en cola para , y luego quitamos y volvemos a poner en cola todos los demás elementos en f i r s t . De esta manera, el parámetro termina al comienzo de f i r s t .$first$$first$$first$
• Si hace más grande que la raíz cuadrada de s e c o n d , colocamos todos los elementos de s e c o n d sobre f i r s t uno por uno y luego intercambiamos f i r s t y s e c o n d . De esta manera, los elementos de f i r $first$$second$$second$$first$$first$$second$ (la parte superior de la pila) terminan en la cabeza de s $first$ .$second$
• El pop se realiza quitando el valor de y devolviendo el resultado si f i r s t no está vacío, y de lo contrario, quitando el valor de s e c o n d y devolviendo el resultado.$first$$first$$second$

Código C # para el primer algoritmo

Este código debería ser bastante legible, incluso si nunca antes has visto C #. Si no sabe qué son los genéricos, simplemente reemplace todas las instancias de 'T' por 'cadena' en su mente, para una pila de cadenas.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        // I'll explain what's happening in these comments. Assume we pushed
        // integers onto the stack in increasing order: ie, we pushed 1 first,
        // then 2, then 3 and so on.

        // Suppose our queues look like this:
        // first: in 5 6 out
        // second: in 1 2 3 4 out
        // Note they are both in stack order and first contains the top of
        // the stack.

        // Suppose value == 7:
        first.Enqueue(value);
        // first: in 7 5 6 out
        // second: in 1 2 3 4 out

        // We restore the stack order in first:
        for (int i = 0; i < first.Count - 1; i++)
            first.Enqueue(first.Dequeue());
        // first.Enqueue(first.Dequeue()); is executed twice for this example, the 
        // following happens:
        // first: in 6 7 5 out
        // second: in 1 2 3 4 out
        // first: in 5 6 7 out
        // second: in 1 2 3 4 out

        // first exeeded its capacity, so we merge first and second.
        if (first.Count * first.Count > second.Count) {
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());
            // first: in 4 5 6 7 out
            // second: in 1 2 3 out
            // first: in 3 4 5 6 7 out
            // second: in 1 2 out
            // first: in 2 3 4 5 6 7 out
            // second: in 1 out
            // first: in 1 2 3 4 5 6 7 out
            // second: in out

            Queue<T> temp = first; first = second; second = temp;
            // first: in out
            // second: in 1 2 3 4 5 6 7 out
        }
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else
            return first.Dequeue();
    }
}

Análisis

Obviamente, Pop funciona en el tiempo en el peor de los casos.$O(1)$

Push funciona en tiempo amortizado. Hay dos casos: si| first$O(\sqrt{n})$luego Push tomaO$|first| < \sqrt{|second|}$tiempo. Si| first| $O(\sqrt{n})$entonces Push tardaO(n)tiempo, pero después de esta operaciónfirstestará vacío. TomaráO($|first| \geq \sqrt{|second|}$$O(n)$$first$tiempo antes de que volvamos a este caso, por lo que el tiempo amortizado esO($O(\sqrt{n})$tiempo.$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

Afirmo que tenemos costo amortizado por operación. El algoritmo de Alex da el límite superior. Para probar el límite inferior, doy una secuencia de movimientos PUSH y POP en el peor de los casos.$\Theta(\sqrt{N})$

La secuencia del peor caso consiste en operaciones PUSH, seguidas de $N$ PUSH operaciones y$\sqrt{N}$ operaciones POP, nuevamente seguidas por$\sqrt{N}$ PUSH operaciones y$\sqrt{N}$ operaciones POP, etc. Es decir:$\sqrt{N}$

$PUSH^N (PUSH^{\sqrt{N}} POP^{\sqrt{N}})^{\sqrt{N}}$

Considere la situación después de las operaciones iniciales de PUSH. No importa cómo funcione el algoritmo, al menos una de las colas debe tener al menos N / 2 entradas.$N$$N/2$

Ahora considere la tarea de tratar con el (primer conjunto de) PUSH y operaciones POP. Cualquier táctica algorítmica debe caer en uno de dos casos:$\sqrt{N}$

En el primer caso, el algoritmo usará ambas colas. La mayor de estas colas tiene al menos entradas, por lo que debemos incurrir en un costo de al menos N / 2 operaciones de cola para eventualmente recuperar incluso un solo elemento que ENCUENTRAMOS y luego necesitamos DESCONECTAR de esta cola más grande.$N/2$$N/2$

En el segundo caso, el algoritmo no usa ambas colas. Esto reduce el problema a simular una pila con una sola cola. Incluso si esta cola está inicialmente vacía, no podemos hacerlo mejor que usar la cola como una lista circular con acceso secuencial, y parece sencillo que debemos usar al menos operaciones de cola en promedio para cada uno de los2$\sqrt{N}/2$ operaciones de pila.$2\sqrt{N}$

En ambos casos, requerimos al menos tiempo (operaciones de cola) para manejar 2 $N/2$ operaciones de pila. Porque podemos repetir este proceso$2\sqrt{N}$ veces, necesitamosN$\sqrt{N}$veces para procesar3Noperaciones de pila en total, dando un límite inferior deΩ($N\sqrt{N}/2$$3N$tiempo amortizado por operación.$\Omega(\sqrt{N})$

$O(\lg n)$$push$$pop$$pop$$O(\lg n)$$pop$ se solicita y la cola de salida está vacía, realiza una secuencia de mezclas perfectas para invertir la cola de entrada y almacenarla en la cola de salida.

$O(1)$

Que yo sepa, esta es una idea nueva ...

Sin usar espacio adicional, ¿tal vez usando una cola priorizada y forzando cada nuevo impulso para darle una prioridad más grande que la anterior? Sin embargo, todavía no sería O (1).

No puedo obtener las colas para implementar una pila en tiempo constante amortizado. Sin embargo, se me ocurre una forma de obtener dos colas para implementar una pila en el peor de los casos en el tiempo lineal.

• $A$$B$
• Cada vez que hay una operación de inserción, voltee el bit e inserte el elemento en la cola que el bit ahora demarca. Haga estallar todo desde la otra cola y empújelo a la cola actual.
• Una operación emergente despega al frente de la cola actual y no toca el bit de estado externo.

Por supuesto, podemos agregar otro bit de estado externo que nos dice si la última operación fue un push o un pop. Podemos retrasar el movimiento de todo de una cola a otra hasta que obtengamos dos operaciones de inserción seguidas. Esto también hace que la operación pop sea un poco más complicada. Esto nos da O (1) complejidad amortizada para la operación pop. Lamentablemente, el empuje sigue siendo lineal.

Todo esto funciona porque cada vez que se realiza una operación de inserción, el nuevo elemento se coloca al principio de una cola vacía y la cola completa se agrega al final de la misma, invirtiendo efectivamente los elementos.

Si desea obtener operaciones de tiempo constante amortizadas, probablemente tendrá que hacer algo más inteligente.

Hay una solución trivial, si su cola permite la carga frontal, que solo requiere una cola (o, más específicamente, eliminar). ¿Quizás este es el tipo de cola que el TA del curso en la pregunta original tenía en mente?

Sin permitir la carga frontal, aquí hay otra solución:

Este algoritmo requiere dos colas y dos punteros, los llamaremos Q1, Q2, primario y secundario, respectivamente. Tras la inicialización, Q1 y Q2 están vacíos, los puntos primarios a Q1 y los puntos secundarios a Q2.

La operación PUSH es trivial, consiste simplemente en:

*primary.enqueue(value);

La operación POP está un poco más involucrada; requiere poner en cola todos menos el último elemento de la cola primaria en la cola secundaria, intercambiando los punteros y devolviendo el último elemento restante de la cola original:

while(*primary.size() > 1)
{
    *secondary.enqueue(*primary.dequeue());
}

swap(primary, secondary);
return(*secondary.dequeue());

No se realiza ninguna comprobación de límites, y no es O (1).

Mientras escribo esto, veo que esto podría hacerse con una sola cola usando un ciclo for en lugar de un ciclo while, como lo ha hecho Alex. De cualquier manera, la operación PUSH es O (1) y la operación POP se convierte en O (n).

Aquí hay otra solución que usa dos colas y un puntero, llamados Q1, Q2 y queue_p, respectivamente:

Tras la inicialización, Q1 y Q2 están vacías y queue_p apunta a Q1.

Nuevamente, la operación PUSH es trivial, pero requiere un paso adicional de apuntar queue_p a la otra cola:

*queue_p.enqueue(value);
queue_p = (queue_p == &Q1) ? &Q2 : &Q1;

La operación de operación POP es similar a la anterior, pero ahora hay n / 2 elementos que deben rotarse a través de la cola:

queue_p = (queue_p == &Q1) ? &Q2 : &Q1;
for(i=0, i<(*queue_p.size()-1, i++)
{
    *queue_p.enqueue(*queue_p.dequeue());
}
return(*queue_p.dequeue());

La operación PUSH sigue siendo O (1), pero ahora la operación POP es O (n / 2).

Personalmente, para este problema, prefiero la idea de implementar una cola (deque) de doble extremo y llamarla pila cuando queramos.

$k$$Θ(n^{1/k})$

$k$
$n$
$O(1)$

En una dirección (es decir, límite superior), el $i$$Θ(n^{i/k})$$Θ(n^{i/k})$$O(1)$$i+1$$O(n^{1/k})$$i-1$$Θ(n^{1/k})$

En la otra dirección (es decir, límite inferior), podemos seguir agregando elementos hasta que $m$$m$$Ω(mn^{1/k})$$o(n^{1/k})$$Ω(n^{1/k})$$o(n^{2/k})$$k$$o(n)$

$Θ(\log n)$

Se puede implementar una pila usando dos colas usando la segunda cola como abuffer. Cuando los elementos se empujan a la pila, se agregan al final de la cola. Cada vez que aparece un elemento, los n - 1 elementos de la primera cola deben moverse al segundo, mientras se devuelve el elemento restante. La clase pública QueueStack implementa ts IStack {private IQueue q1 = new Queue (); IQueue privado q2 = nueva cola (); public void push (E e) {q1.enqueue (e) // O (1)} public E pop (E e) {while (1 <q1.size ()) // O (n) {q2.enqueue ( q1.dequeue ()); } sw apQueues (); return q2.dequeue (); } p rivate void swapQueues () {IQueue Q = q2; q2 = q1; q1 = Q; }}