(relacionado con otra pregunta sobre si la pila se puede implementar usando la cola …)
Sí, se puede implementar un “TwoStackQueue” utilizando dos estructuras de datos de Stack, independientemente de cómo se implemente internamente. Por supuesto, hay un costo de rendimiento asociado sobre una cola “nativa”.
Una pila implementa la mayor parte de la funcionalidad de cola, como probablemente te des cuenta. Sin embargo, una pila solitaria no puede iterar a través de sus datos, por lo que se necesita una segunda pila. Piense en sus datos como el líquido que se vierte entre dos recipientes de vidrio. Para construir este “TwoStackQueue”, deberá volver a implementar las funciones Enqueue , Dequeue y Front de Queue.
- Procesadores de señal digital (DSP): cuando alguien escribe un archivo en una tarjeta SD usando un bus spi, ¿cómo sabe dónde debería estar el comienzo de un nuevo archivo?
- Cómo ejecutar cruces en algoritmos genéticos con cromosomas codificados por gráficos
- ¿Cómo pasan su tiempo exactamente los participantes en varios sitios de codificación de algoritmos?
- ¿Es necesario tener datos estacionarios para aplicar algún tipo de algoritmo de aprendizaje automático?
- ¿Cómo eliges un campo interesante en informática?
Hay opciones de rendimiento que puede hacer aquí (como con OneQueueStack), dependiendo de si desea específicamente un Enqueue optimizado (), o un Dequeue optimizado () y Front (), o un sistema global equilibrado y globalmente optimizado.
- Para ir con la primera opción (Enqueue rápido), después de cada operación (ya sea Enqueue o Dequeue), inserta todos los datos de cabeza en una de las pilas, de modo que el dato de cola esté en la parte superior de esa pila. Luego, cuando un nuevo dato es Enqueue (), puede Empujarlo () internamente en esa misma Pila. Si, en cambio, recibe una solicitud Dequeue (), entonces necesita mover todos los datos fuera de esa pila tail = -primero a la otra pila, de modo que la cabeza esté en la parte superior de esa Pila, en ese punto puede Pop () internamente y Dequeue () externamente. Entonces, esto hace que Dequeue () sea bastante costoso – O (N) en realidad. (Caché el valor de la cabeza, por lo que no necesita hacer una rotación completa cuando se llama a Front ().)
- Si opta por la segunda opción (Dequeue rápido), de forma predeterminada, los datos siempre se encuentran en la otra pila, con el valor de la cabeza en la parte superior de la pila. Cuando se llama a Dequeue () (o Front ()), ese dato está disponible de inmediato. Sin embargo, cuando se llama a Enqueue, todos los datos deben transferirse de cabeza a la otra pila, luego se agrega el dato adicional, luego todos los datos se desplazan primero de cola a la pila original, de modo que el valor de la cabeza vuelva a estar en parte superior de la pila lista para funcionar. Entonces, en este caso, como antes, se necesitan dos iteraciones O (N) diferentes, lo que hace que Enqueue () sea costoso.
- Tendría sentido ir con uno de los dos casos anteriores si realmente necesitara que esa llamada de función se optimizara siempre. De lo contrario, el mejor rendimiento general del sistema es ir con el caso equilibrado.
Aquí, usted esencialmente reconoce que a largo plazo hay un número igual de llamadas Enqueue y Dequeue, y también que no necesariamente podemos predecir la secuencia en la que vendrán. Similar a cómo podríamos tratar un ascensor en un edificio de dos pisos, simplemente dejamos nuestro TwoStackQueue en el estado que necesitaba la operación anterior. Con esta opción, si Enqueue-Dequeue-Enqueue-Dequeue, no estamos haciendo cambios de datos especulativos en segundo plano.
Por lo tanto, la respuesta es sí, puede implementar una Cola con dos pilas , y debe elegir si desea garantizar una Enqueue rápida (pero tiene v.slow Dequeue) o garantizar una Dequeue rápida (pero tiene v.slow Enqueue) , o en promedio Dequeue y Enqueue ligeramente lentos, pero el rendimiento general del sistema mejor equilibrado.
