¿Cuál es el punto de implementar una pila usando dos colas?

34

Tengo la siguiente pregunta de tarea:

Implemente los métodos de pila push (x) y pop () usando dos colas.

Esto me parece extraño porque:

  • Una pila es una cola (LIFO)
  • No veo por qué necesitarías dos colas para implementarlo

Busqué alrededor:

y encontré un par de soluciones. Esto es lo que terminé con:

public class Stack<T> {
    LinkedList<T> q1 = new LinkedList<T>();
    LinkedList<T> q2 = new LinkedList<T>();

    public void push(T t) {
        q1.addFirst(t);
    }

    public T pop() {
        if (q1.isEmpty()) {
            throw new RuntimeException(
                "Can't pop from an empty stack!");
        }

        while(q1.size() > 1) {
            q2.addFirst( q1.removeLast() );
        }

        T popped = q1.pop();

        LinkedList<T> tempQ = q1;
        q1 = q2;
        q2 = tempQ;

        return popped;
    }
}

Pero no entiendo cuál es la ventaja sobre el uso de una sola cola; la versión de dos colas parece inútilmente complicada.

Digamos que elegimos que los empujes sean los más eficientes de los 2 (como hice anteriormente), pushseguirían siendo los mismos y popsimplemente requerirían iterar hasta el último elemento y devolverlo. En ambos casos, el pushsería O(1)y el popsería O(n); pero la versión de cola única sería drásticamente más simple. Solo debería requerir un solo bucle for.

¿Me estoy perdiendo de algo? Cualquier idea aquí sería apreciada.

java stack Carcigenicate
fuente
17
Una cola normalmente se refiere a una estructura FIFO mientras que la pila es una estructura LIFO. La interfaz para LinkedList en Java es la de una deque (cola de doble extremo) que permite el acceso tanto a FIFO como a LIFO. Intente cambiar la programación a la interfaz de cola en lugar de la implementación de LinkedList.
12
El problema más habitual es implementar una cola usando dos pilas. Puede encontrar interesante el libro de Chris Okasaki sobre estructuras de datos puramente funcionales.
Eric Lippert
2
A partir de lo que dijo Eric, a veces puede encontrarse en un lenguaje basado en la pila (como DC o un autómata push down con dos pilas (equivalente a una máquina de Turing porque, bueno, puede hacer más)) donde puede encontrarse con Múltiples pilas, pero sin cola.
1
@MichaelT: O también puede encontrarse corriendo en una CPU basada en pila
slebetman
11
"Una pila es una cola (LIFO)" ... uhm, una cola es una línea de espera. Como la línea para usar un baño público. ¿Las líneas en las que espera se comportan alguna vez de manera LIFO? Deje de usar el término "cola LIFO", no tiene sentido.
Mehrdad

Respuestas:

44

No hay ventaja: este es un ejercicio puramente académico.

Una muy hace mucho tiempo, cuando yo era un estudiante de primer año en la universidad tuve un ejercicio similar 1 . El objetivo era enseñar a los estudiantes cómo usar la programación orientada a objetos para implementar algoritmos en lugar de escribir soluciones iterativas usando forbucles con contadores de bucles. En su lugar, combine y reutilice las estructuras de datos existentes para lograr sus objetivos.

Nunca usará este código en Real World TM . Lo que debe eliminar de este ejercicio es cómo "pensar fuera de la caja" y reutilizar el código.

Tenga en cuenta que debe usar la interfaz java.util.Queue en su código en lugar de usar la implementación directamente:

Queue<T> q1 = new LinkedList<T>();
Queue<T> q2 = new LinkedList<T>();

Esto le permite usar otras Queueimplementaciones si lo desea, así como también ocultar 2 métodos LinkedListque pueden activar el espíritu de la Queueinterfaz. Esto incluye get(int)y pop()(mientras su código se compila, hay un error lógico dado las restricciones de su asignación. Declarar sus variables como en Queuelugar de LinkedListlo revelará). Lectura relacionada: Comprender la "programación en una interfaz" y ¿Por qué son útiles las interfaces?

1 Todavía recuerdo: el ejercicio consistía en revertir una pila utilizando solo métodos en la interfaz de pila y sin métodos de utilidad en java.util.Collectionsotras clases de utilidad "estáticas". La solución correcta implica el uso de otras estructuras de datos como objetos temporales de retención: debe conocer las diferentes estructuras de datos, sus propiedades y cómo combinarlas para hacerlo. Sorprendió a la mayoría de mi clase CS101 que nunca había programado antes.

2 Los métodos todavía están allí, pero no puede acceder a ellos sin tipos de conversión o reflexión. Por lo tanto, no es fácil usar esos métodos sin cola.

Comunidad
fuente
1
Gracias. Supongo que eso tiene sentido. También me di cuenta de que estoy usando operaciones "ilegales" en el código anterior (empujando al frente de un FIFO), pero no creo que eso cambie nada. Invertí todas las operaciones, y todavía funciona según lo previsto. Voy a esperar un poco antes de aceptar, ya que no quiero disuadir a otras personas de dar su opinión. Gracias de cualquier forma.
Carcigenicate
19

No hay ventaja Te has dado cuenta correctamente de que usar Colas para implementar una Pila conduce a una complejidad de tiempo horrible. Ningún programador (competente) haría algo como esto en la "vida real".

Pero es posible. Puede usar una abstracción para implementar otra, y viceversa. Una pila se puede implementar en términos de dos colas, y de la misma manera usted podría implementar una cola en términos de dos pilas. La ventaja de este ejercicio es:

  • recapitulas pilas
  • recapitulas las colas
  • te acostumbras al pensamiento algorítmico
  • aprendes algoritmos relacionados con la pila
  • puedes pensar en compensaciones en algoritmos
  • Al darse cuenta de la equivalencia de colas y pilas, conecta varios temas de su curso
  • ganas experiencia práctica en programación

En realidad, este es un gran ejercicio. Debería hacerlo yo mismo ahora :)

amon
fuente
3
@JohnKugelman Gracias por su edición, pero realmente quise decir "horrible complejidad del tiempo". Para una pila basada en una lista vinculada push, peeky las popoperaciones están en O (1). Lo mismo para una pila basada en matriz redimensionable, excepto que pushestá en O (1) amortizado, con O (n) en el peor de los casos. En comparación con eso, una pila basada en la cola es muy inferior con O (n) push, O (1) pop and peek, o alternativamente O (1) push, O (n) pop and peek.
amon
1
"horrible complejidad temporal" y "enormemente inferior" no es exactamente correcto. La complejidad amortizada sigue siendo O (1) para push y pop. Hay una pregunta divertida en TAOCP (vol1?) Sobre eso (básicamente tienes que demostrar que la cantidad de veces que un elemento puede cambiar de una pila a otra es constante). El rendimiento en el peor de los casos para una operación es diferente, pero rara vez escucho a alguien hablar sobre el rendimiento de O (N) para insertar ArrayLists, no el número generalmente interesante.
Voo
5

Definitivamente hay un propósito real para hacer una cola con dos pilas. Si usa estructuras de datos inmutables de un lenguaje funcional, puede ingresar a una pila de elementos que se pueden empujar y extraer de una lista de elementos emergentes. Los elementos poppables se crean cuando todos los elementos se han desplegado, y la nueva pila poppable es el reverso de la pila empujable, donde la nueva pila empujable ahora está vacía. Es eficiente

¿En cuanto a una pila hecha de dos colas? Eso podría tener sentido en un contexto en el que tiene un montón de colas grandes y rápidas disponibles. Definitivamente es inútil como este tipo de ejercicio Java. Pero podría tener sentido si esos son canales o colas de mensajes. (es decir: N mensajes en cola, con una operación O (1) para mover elementos (N-1) en el frente a una nueva cola.)

Robar
fuente
Hmm ... esto me hizo pensar en usar registros de desplazamiento como la base de la computación y sobre la arquitectura de la correa / fábrica
slebetman
wow, la CPU Mill es realmente interesante. Una "máquina de cola" con seguridad.
Rob
2

El ejercicio se ideó innecesariamente desde un punto de vista práctico. El punto es forzarlo a usar la interfaz de la cola de una manera inteligente para implementar la pila. Por ejemplo, su solución "Una cola" requiere que itere sobre la cola para obtener el último valor de entrada para la operación "pop" de la pila. Sin embargo, una estructura de datos de cola no permite iterar sobre los valores, está restringido para acceder a ellos en el primero en entrar, primero en salir (FIFO).

Destruktor
fuente
2

Como otros ya notaron: no hay una ventaja en el mundo real.

De todos modos, una respuesta a la segunda parte de su pregunta, por qué no simplemente usar una cola, está más allá de Java.

En Java, incluso la Queueinterfaz tiene un size()método y todas las implementaciones estándar de ese método son O (1).

Eso no es necesariamente cierto para la lista ingenua / canónica vinculada que implementaría un programador de C / C ++, que solo mantendría punteros al primer y último elemento y cada elemento un puntero al siguiente elemento.

En ese caso size()es O (n) y debe evitarse en bucles. O la implementación es opaca y solo proporciona el mínimo add()y mínimo remove().

Con tal implementación, primero tendría que contar el número de elementos transfiriéndolos a la segunda cola, transferir los n-1elementos nuevamente a la primera cola y devolver el elemento restante.

Dicho esto, probablemente no inventarías algo como esto si vives en tierra de Java.

Thraidh
fuente
Buen punto sobre el size()método. Sin embargo, en ausencia de un size()método O (1) , es trivial que la pila realice un seguimiento de su tamaño actual. Nada para detener una implementación de una cola.
cmaster
Todo depende de la implementación. Si tiene una cola, implementada solo con punteros directos y punteros al primer y último elemento, aún podría escribir un algoritmo que elimine un elemento, lo guarde en una variable local, agregue el elemento previamente en esa variable a la misma cola hasta que el El primer elemento se ve de nuevo. Esto solo funciona si puede identificar de forma exclusiva un elemento (por ejemplo, mediante un puntero) y no solo algo con el mismo valor. O (n) y solo usa add () y remove (). De todos modos, es más fácil optimizar que encontrar una razón para hacerlo, excepto pensar en algoritmos.
Thraidh
0

Es difícil imaginar un uso para tal implementación, es cierto. Pero la mayor parte del punto es demostrar que se puede hacer .

En términos de usos reales de estas cosas, sin embargo, puedo pensar en dos. Un uso para esto es implementar sistemas en entornos restringidos que no fueron diseñados para ello : por ejemplo, los bloques redstone de Minecraft representan un sistema completo de Turing, que la gente ha utilizado para implementar circuitos lógicos e incluso CPUs completas. En los primeros días de los juegos guiados por guiones, muchos de los primeros bots de juegos también se implementaron de esta manera.

Pero también puede aplicar este principio a la inversa, asegurando que algo no sea ​​posible en un sistema cuando no lo desee . Esto puede surgir en contextos de seguridad: por ejemplo, los sistemas de configuración potentes pueden ser una ventaja, pero todavía hay grados de potencia que preferiría no dar a los usuarios. Esto restringe lo que puede permitir que haga el lenguaje de configuración, para que no sea subvertido por un atacante, pero en este caso, eso es lo que desea.

El más cuchara
fuente