Simulación mutua de pilas y colas

Implementar una cola utilizando dos pilas y una pila utilizando dos colas son preguntas clásicas de diseño en entrevistas. Evalúan su comprensión de los invariantes de ambas estructuras de datos y su capacidad para mantener la garantía de una estructura utilizando las operaciones básicas de otra. Los entrevistadores también utilizan estos problemas como introducción a la complejidad amortizada.

La idea clave es que las pilas son LIFO y las colas son FIFO. Para convertir una en otra debe invertir el orden; pasar los elementos de una pila a otra produce el orden de inserción original, que es FIFO.

El enfoque diferido utiliza una pila inbox para las operaciones push y una pila outbox para las operaciones pop. Cuando se llama a dequeue, si outbox está vacía, transfiera todos los elementos de inbox a outbox; esta inversión restaura el orden FIFO. Si outbox no está vacía, extraiga directamente de ella. Las transferencias se realizan de forma diferida, amortizando el coste de transferencia O(n) entre muchas operaciones.

Cada elemento se transfiere de inbox a outbox como máximo una vez. Extraer de outbox cuesta O(1) y las transferencias solo se realizan cuando outbox está vacía; por tanto, el trabajo total de n operaciones push y n operaciones pop es como máximo de 2n operaciones de pila: O(n) en total y O(1) amortizado por operación. Esto significa que algunas operaciones individuales pueden costar O(n) en el peor caso, pero el coste medio es O(1).

Implementar una pila con dos colas resulta menos natural porque las colas son FIFO. El enfoque de extracción diferida mantiene una cola principal y una cola temporal. En push, encole el elemento en la cola principal (O(1)). En pop o peek, desencole todos los elementos salvo el último en la cola temporal, guarde el último elemento y, después, intercambie las colas. Esto cuesta O(n) por operación pop, pero O(1) por operación push.

Una implementación elegante con una sola cola consiste en que, al realizar push, se encole el elemento nuevo y después se rote la cola para colocar dicho elemento al frente. Rotar significa desencolar y volver a encolar todos los elementos que ya estaban allí antes de la operación push. Así, pop y peek cuestan O(1) (simplemente desencolan o consultan el elemento del frente). Push cuesta O(n): el intercambio contrario al de la versión con dos colas.

Para una cola a partir de dos pilas: push O(1), pop/peek O(1) amortizado; prefiera esta opción cuando las operaciones pop sean frecuentes. Para una pila a partir de dos colas: push O(1), pop O(n); prefiera esta opción cuando las operaciones push sean mucho más frecuentes que las operaciones pop. Para una pila a partir de una cola: push O(n), pop O(1); prefiera esta opción cuando predominen las operaciones pop. Exponga explícitamente estas ventajas y desventajas en una entrevista para demostrar que piensa más allá de «funciona».

Cuando los elementos 1, 2 y 3 se insertan en una pila (inbox), quedan ordenados de abajo arriba como 1, 2 y 3. Al extraerlos todos en una segunda pila (outbox), se invierte el orden: outbox tiene el 3 abajo y el 1 arriba. Extraer elementos de outbox devuelve primero el 1, después el 2 y finalmente el 3, exactamente en el orden de inserción FIFO. Por eso exactamente dos inversiones (dos pilas) restauran FIFO, mientras que una sola pila produciría LIFO.

LeetCode 232 es el problema directo de «cola a partir de dos pilas». La solución esperada es la transferencia diferida a outbox. En una entrevista, indique que cada elemento se mueve de inbox a outbox como máximo una vez, por lo que todas las operaciones tienen un coste amortizado O(1). Mencione que las llamadas individuales a pop pueden costar O(n) en el peor caso (cuando outbox está vacía), pero que el promedio entre n operaciones es O(1).

LeetCode 225 es el problema de la «pila a partir de colas». La solución más clara es rotar la cola al realizar push. Después de insertar el elemento x, rote la cola moviendo detrás de x todos los elementos que ya estaban allí. Esto cuesta O(n) por operación push, pero hace que top y pop cuesten O(1). Exponga esta ventaja y desventaja, y confirme que se ajusta a las restricciones (por ejemplo, una carga de trabajo con pocas operaciones push o muchas operaciones pop).

Un reto de diseño relacionado consiste en implementar tres pilas usando un solo array. Un enfoque divide el array en tres secciones fijas del mismo tamaño. Un enfoque más flexible utiliza almacenamiento intercalado con punteros: hace crecer cada pila dentro de su región y copia los elementos cuando las fronteras colisionan. Esto pone a prueba la gestión dinámica de arrays y se plantea en entrevistas para puestos sénior. El enfoque de secciones fijas es más sencillo, pero desperdicia espacio si las pilas crecen de forma desigual.

Los problemas de simulación mutua enseñan un principio más general: cualquier estructura de datos puede construirse a partir de otra si se cuenta con suficiente almacenamiento intermedio y operaciones de inversión. El coste de la simulación depende de las operaciones que se optimicen: siempre se puede hacer que push sea O(1) o que pop sea O(1), pero conseguir que ambas sean O(1) requiere amortización o varias estructuras auxiliares.

En una entrevista, pregunte siempre: «¿Qué operaciones son más frecuentes?». Esto guía la elección de la variante de implementación y demuestra una forma de pensar propia de un nivel sénior sobre los requisitos operativos.

Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección aprendió que: una cola implementada con dos pilas consigue un pop amortizado O(1) al transferir elementos de inbox a outbox de forma diferida, una pila implementada con una cola consigue un pop O(1) al rotar la cola en cada push (push O(n)) y la elección de qué operación hacer O(1) depende del patrón de uso. A continuación explorará los componentes internos de los mapas hash y la gestión de colisiones.