La cola y la pila son estructuras de datos bastante simples que utilizamos en nuestra codificación diaria. De hecho, se pueden considerar las estructuras más fáciles de mantener datos.

A lo largo del artículo, usaré DS para referirme a la estructura de datos.

Queue es un DS que funciona según el principio FIFO. Los datos que llegan primero pueden salir primero. Hay muchas formas de implementar colas. Somos libres de utilizar matrices, listas vinculadas y muchos otros. Pero aquí, estoy a punto de discutir la implementación de Queue usando otro DS llamado Stack.

Ahora, todos sabemos, Stack es un DS que funciona según el principio LIFO. Siempre pienso en apilar libros uno encima del otro, así que siéntete libre de usar esa analogía si te ayuda a visualizar.

Me encontré con esta pregunta en hackerrank donde nos exigieron que implementáramos Queue usando 2 pilas. Suena simple ¿verdad? Tómate un momento para pensar cómo podríamos lograrlo.

Es posible que se te hayan ocurrido algunas soluciones porque hay muchas maneras de hacerlo. Entonces, ¿por qué no lo intentas directamente?

Pregunta

Ahora, para aquellos que lo intentaron y obtuvieron un "error de tiempo de espera" y para aquellos que no se molestaron en intentarlo, permítanme explicarles la solución más sencilla y sencilla a este problema.

Primero eche un vistazo a cómo se puede implementar la pila.

Como puedes ver, he implementado la pila usando una lista. Inicialmente, el constructor inicializa una lista vacía. Enviamos datos agregándolos al final de la lista. Mientras aparece, si no proporcionamos un índice, aparecerá al final de la lista. Por lo tanto, el último elemento que se inserta es el primero que se extrae.

Ahora, de manera similar para la cola, hemos inicializado dos pilas diferentes. Uno para poner en cola y otro para quitar de cola.

Usamos enqueueStack similar a stack solo para enviar datos al final de la lista. Pero para dequeueStack, sabemos que la función emergente de la pila elimina el elemento del último, así que lo que hacemos es; invertimos el enqueueStack y lo colocamos en dequeueStack. Por lo tanto, el primer elemento de enqueueStack se convierte en el último elemento de dequeueStack, el segundo de enqueueStack se convierte en el penúltimo de dequeueStack y así sucesivamente. Entonces, si usamos la función pop para dequeueStack, eliminará el primer elemento que presionamos, imitando así la cola.

¡No te preocupes si esto te suena confuso ahora mismo! Una vez que veas el código te darás cuenta de lo que estoy hablando. De hecho, ¡échale un vistazo ahora mismo!

Quizás te preguntes para qué sirven esos controles adicionales. Como verificar que dequeueStack esté vacío o no. Si no lo comprobamos inicialmente. Los elementos de enqueueStack por inversión se ubicarán en dequeueStack y lo que sucede es que el elemento de cola de Stacks que se suponía que estaba primero ahora termina siendo el último. Entonces, el primer dequeueStack debe vaciarse como se muestra en el código.

De manera similar, printFront imprime el elemento que se supone que está al principio de la cola.

Después de esta implementación, leemos la entrada de STDIN e imprimimos la salida a STDOUT.

Nuestra entrada es algo así:

Y la función principal completa es:

He intentado implementar esto de la manera más sencilla posible. Podría haber otras formas mejores de implementar esto. ¡Uno de ellos se presenta aquí!