Una pila, dos colas

59

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.

MS Dousti
fuente
2
Supongo que solo puede usar una cantidad limitada de espacio que no sean las dos colas (O (1) u O (log n)). A mí me parece imposible, porque no tenemos forma de revertir el orden de una secuencia de entrada larga. Pero, por supuesto, esto no es una prueba, a menos que pueda convertirse en un reclamo riguroso ...
Tsuyoshi Ito
@ Tsuyoshi: Tienes razón sobre el supuesto de espacio limitado. Y sí, eso fue lo que le dije a ese TA (obstinado), pero él se negó :(
MS Dousti
2
@ Tsuyoshi: No creo que deba asumir un límite en el espacio en general, solo debe suponer que no puede almacenar los objetos empujados y expulsados ​​de la pila en ningún lugar que no sean las dos colas (y probablemente un número constante de variables)
Kaveh
@SadeqDousti En mi opinión, la única forma en que esto sería posible es si usas una implementación de lista enlazada de una cola y usas algunos punteros para apuntar siempre a la parte superior de la "pila"
Charles Addis
2
Parece que el TA podría haber querido decir "Implementar una cola usando dos pilas", lo cual es posible precisamente en "O (1) tiempo amortizado".
Thomas Ahle

Respuestas:

45

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.

David Eppstein
fuente
44
+1 para excelentes referencias. Sin embargo, hay algunos aspectos técnicos: algunos de los documentos, como el primero, no consideran el problema de simular una pila utilizando dos colas (por mucho que pueda decir del resumen). Otros consideran el análisis del peor de los casos, no el costo amortizado.
MS Dousti
13

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(norte)O(norte)O(norte)

Presento dos algoritmos, el primero es un algoritmo simple con un tiempo de ejecución para Pop y el segundo con un O ( O(norte)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(norte)

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(norte)

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(norte)

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'.FyorstsmiConortereFyorstsmiConortere

  • El empuje se realiza simplemente colocando el parámetro en cola en .Fyorst
  • 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, revertimosFyorstsmiConortere , 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 oFyorstsmiConortereFyorstFyorstsmiConortere y devolver el resultado de la retirada de cola.smiConortere

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)FyorstsmiConortereO(norte)norte

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'.FyorstsmiConortereFyorstsmiConortere

Esta es una versión adaptada del primer algoritmo, en el que no "barajamos" inmediatamente el contenido de en s e c o nFyorst . 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 fusionessmiConortereFyorstsmiConorteresmiConortereFyorst .smiConortere

  • Se sigue presionando simplemente colocando el parámetro en cola en .Fyorst
  • 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 | < FyorstsmiConortereFyorstsimplemente retiramosfirsty devolvemos el resultado. De lo contrario, añadimossecondaEl |FyorstEl |<El |smiConortereEl |FyorstsmiConortere , 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.FyorstFyorstsmiConorteresmiConortere

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(norte)El |FyorstEl |<El |smiConortereEl |, luego barajamos en orden de pila en O ( | f i r s t | ) = O ( Fyorsttiempo. Si| first| O(El |FyorstEl |)=O(norte), entonces debemos haber tenido al menos|first||second| llama a Push. Por lo tanto, solo podemos golpear este caso cadan llamadas a Push y Pop. El tiempo real de ejecución para este caso esO(n), por lo que el tiempo amortizado esO( nnO(n).O(nn)=O(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(n)first

Alex ten Brink
fuente
Edité los primeros párrafos para que mi respuesta se formulara como una respuesta real a la pregunta.
Alex ten Brink
66
¡Está utilizando una matriz (inversor) para invertir! No creo que se te permita hacer esto.
Kaveh
Es cierto, uso espacio adicional mientras ejecuto los métodos, pero pensé que estaría permitido: si desea implementar una cola usando dos pilas de forma directa, debe invertir una de las pilas en un punto, y hasta Sé que necesita espacio adicional para hacerlo, por lo que, dado que esta pregunta es similar, pensé que se permitiría usar espacio adicional durante la ejecución de un método, siempre y cuando no use espacio adicional entre las llamadas a métodos.
Alex ten Brink el
66
"si quieres implementar una cola usando dos pilas de forma directa, debes invertir una de las pilas en un punto, y hasta donde sé, necesitas espacio adicional para hacerlo" --- No lo necesitas. Hay una manera de hacer que el costo amortizado de Enqueue sea 3 y el costo amortizado de Dequeue sea 1 (es decir, ambos O (1)) con una celda de memoria y dos pilas. La parte difícil es realmente la prueba, no el diseño del algoritmo.
Aaron Sterling el
Después de pensarlo un poco más, me doy cuenta de que estoy engañando y mi comentario anterior es realmente erróneo. He encontrado una manera de rectificarlo: pensé en dos algoritmos con los mismos tiempos de ejecución que los dos anteriores (aunque Push es ahora la operación que lleva mucho tiempo y Pop ahora se realiza en tiempo constante) sin usar espacio adicional. Publicaré una nueva respuesta una vez que la haya escrito toda.
Alex ten Brink el
12

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(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(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 cfirstsecondfirstsecondfirst contendrá los elementos en la parte inferior de la pila. El tamaño de f i rsecondfirst .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 .firstfirstfirst
  • 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 cfirstsecondsecondfirstfirstsecond (la parte superior de la pila) terminan en la cabeza de s efirst .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.firstfirstsecond

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(n)luego Push tomaO(|first|<|second|tiempo. Si| first| O(n)entonces Push tardaO(n)tiempo, pero después de esta operaciónfirstestará vacío. TomaráO(|first||second|O(n)firsttiempo antes de que volvamos a este caso, por lo que el tiempo amortizado esO( nO(n)tiempo.O(nn)=O(n)

Alex ten Brink
fuente
sobre cómo eliminar una respuesta, eche un vistazo a meta.cstheory.stackexchange.com/q/386/873 .
MS Dousti
No puedo entender la línea first.Enqueue(first.Dequeue()). ¿Has escrito mal algo?
MS Dousti
Gracias por el enlace, actualicé mi respuesta original en consecuencia. En segundo lugar, agregué muchos comentarios a mi código que describen lo que está sucediendo durante la ejecución de mi algoritmo, espero que aclare cualquier confusión.
Alex ten Brink el
Para mí, el algoritmo era más legible y más fácil de entender antes de la edición.
Kaveh
9

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.Θ(N)

La secuencia del peor caso consiste en operaciones PUSH, seguidas de N PUSH operaciones yN operaciones POP, nuevamente seguidas porN PUSH operaciones yN operaciones POP, etc. Es decir:N

PUSHN(PUSHNPOPN)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.NN/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: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/2N/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 los2N/2 operaciones de pila.2N

En ambos casos, requerimos al menos tiempo (operaciones de cola) para manejar 2 N/2 operaciones de pila. Porque podemos repetir este proceso2N veces, necesitamosNNveces para procesar3Noperaciones de pila en total, dando un límite inferior deΩ(NN/23Ntiempo amortizado por operación.Ω(N)

Shaun Harker
fuente
NN
nQ1N/2Q22nn4:1+2++n+n2norte
¿Aparentemente la respuesta de Peter contradice este límite inferior?
Joe
PUSHNPOPNO(N)
O(N)
6

O(lgn)pushpoppopO(lgn)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 ...

Peter Boothe
fuente
Argh! Debería haber buscado una pregunta actualizada o relacionada. Los documentos a los que se vinculó en su respuesta anterior postulaban una relación entre k pilas y k + 1 pilas. ¿Este truco termina poniendo el poder de las colas k entre las pilas k y k + 1? Si es así, es una especie de nota al margen. De cualquier manera, gracias por vincularme a su respuesta, así que no perdí mucho tiempo escribiendo esto para otro lugar.
Peter Boothe
1

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).

Alfa
fuente
0

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.

  • Asi
  • 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.

Ross Snider
fuente
44
Seguramente, puedo usar una sola cola con la misma complejidad de tiempo de caso peor y sin la complicación, esencialmente tratando la cola como una lista circular con un elemento de cola adicional que representa la parte superior de la pila.
Dave Clarke
¡Parece que puedes! Sin embargo, parece que se necesita más de una cola clásica para simular una pila de esta manera.
Ross Snider
0

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.

oosterwal
fuente
Su segundo algoritmo es útil para comprender el más involucrado de Alex.
hengxin
0

kΘ(norte1/ /k)

k
norte
O(1)

En una dirección (es decir, límite superior), el yoΘ(norteyo/ /k)Θ(norteyo/ /k)O(1)yo+1O(norte1/ /k)yo-1Θ(norte1/ /k)

En la otra dirección (es decir, límite inferior), podemos seguir agregando elementos hasta que metrometroΩ(metronorte1/ /k)o(norte1/ /k)Ω(norte1/ /k)o(norte2/ /k)ko(norte)

Θ(Iniciar sesiónnorte)

Dmytro Taranovsky
fuente
-3

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; }}

Pradeepkumar
fuente
2
¿Te perdiste la parte de la pregunta sobre el tiempo amortizado O (1)?
David Eppstein