Guía para Implementar una Cola con dos Pilas

En el fascinante universo de las estructuras de datos, las pilas (stacks) y las colas (queues) son dos de los pilares fundamentales. Aunque a primera vista puedan parecer similares, operan bajo principios diametralmente opuestos. Una cola sigue la regla FIFO (First-In-First-Out), donde el primer elemento en entrar es el primero en salir, como una fila en el supermercado. Por otro lado, una pila funciona bajo el principio LIFO (Last-In-First-Out), donde el último elemento añadido es el primero que se retira, como una pila de platos. Pero, ¿qué sucede si te enfrentas al desafío de simular el comportamiento de una cola usando únicamente pilas? Este es un problema clásico en entrevistas técnicas y un excelente ejercicio para profundizar en tu comprensión de cómo funcionan estas estructuras. A continuación, te guiaremos paso a paso para que lo domines por completo.

Fundamentos: Pila vs. Cola

Antes de sumergirnos en la implementación, es crucial tener claras las diferencias entre estas dos estructuras de datos. Cada una tiene operaciones y propósitos distintos que las hacen únicas.

La Pila (Stack)

Imagina una pila de libros. Solo puedes añadir un libro nuevo en la parte superior y solo puedes quitar el libro que está en la cima. Esa es la esencia de una pila.

• Principio: LIFO (Último en Entrar, Primero en Salir).
• Operaciones principales:
• push(): Añade un elemento a la cima de la pila.
• pop(): Elimina y devuelve el elemento de la cima.
• peek(): Devuelve el elemento de la cima sin eliminarlo.
• isEmpty(): Comprueba si la pila está vacía.

La Cola (Queue)

Piensa en una cola para comprar entradas de cine. La primera persona que llega es la primera en ser atendida. Así funciona una cola.

• Principio: FIFO (Primero en Entrar, Primero en Salir).
• Operaciones principales:
• enqueue(): Añade un elemento al final de la cola.
• dequeue(): Elimina y devuelve el elemento del frente de la cola.
• peek(): Devuelve el elemento del frente sin eliminarlo.
• isEmpty(): Comprueba si la cola está vacía.

El Desafío: ¿Por Qué Dos Pilas?

El núcleo del problema radica en que una pila invierte el orden de los elementos de forma natural. Si introduces 1, 2 y 3 en una pila, al sacarlos obtendrás 3, 2 y 1. Una cola, en cambio, debe mantener ese orden. ¿Cómo logramos esto? La solución es utilizar una segunda pila como una herramienta auxiliar. Una pila la usaremos para recibir los elementos, y la otra nos ayudará a revertir el orden cuando sea necesario para simular el comportamiento FIFO. Existen dos estrategias principales para lograrlo, cada una con sus propias ventajas y desventajas en términos de rendimiento.

Estrategia 1: Encolado Costoso (Push Lento, Pop Rápido)

En este enfoque, el trabajo pesado se realiza durante la operación de inserción (push o enqueue). El objetivo es que la pila principal (llamémosla s1) siempre mantenga los elementos en el orden correcto de una cola, con el elemento más antiguo en la cima, listo para ser extraído.

¿Cómo funciona?

• Operación push(x): Para añadir un nuevo elemento, seguimos estos pasos:
1. Movemos todos los elementos existentes de la pila s1 a una pila auxiliar, s2.
2. Añadimos el nuevo elemento x a s1, que ahora está vacía.
3. Movemos todos los elementos de vuelta desde s2 a s1.

Este doble trasvase asegura que el nuevo elemento quede en el fondo de la pila, y los elementos más antiguos asciendan hacia la cima.

• Operación pop(): Como s1 siempre tiene el elemento más antiguo en la cima, la operación de extracción es increíblemente simple y rápida: simplemente hacemos un pop de s1.

Análisis de Complejidad

• push(): Esta operación tiene una complejidad de tiempo de O(n), donde 'n' es el número de elementos en la cola. Esto se debe a que cada elemento debe ser movido dos veces (de s1 a s2 y de vuelta).
• pop(): Esta operación es muy eficiente, con una complejidad de tiempo de O(1), ya que solo implica una acción directa sobre la pila.

Ejemplo Práctico

Imaginemos la secuencia: push(10), push(20), pop().

1. Estado inicial:s1 = [], s2 = [].
2. push(10):s1 está vacía, así que añadimos 10. s1 = [10].
3. push(20):
• Movemos 10 de s1 a s2. s1 = [], s2 = [10].
• Añadimos 20 a s1. s1 = [20], s2 = [10].
• Movemos 10 de s2 a s1. s1 = [10, 20], s2 = []. (Nota: el 10 está en la cima).
4. pop(): Sacamos el elemento de la cima de s1. Se devuelve 10. s1 = [20].

Esta estrategia es ideal para escenarios donde las operaciones de extracción (pop) son mucho más frecuentes que las de inserción (push).

Estrategia 2: Encolado Eficiente (Push Rápido, Pop Amortizado)

Esta es la implementación más común y, a menudo, más eficiente. La idea es ser "perezoso" y no reorganizar los elementos en cada inserción. El trabajo de reordenamiento se aplaza hasta que es estrictamente necesario, es decir, cuando se necesita realizar una operación de extracción.

¿Cómo funciona?

Usaremos dos pilas: input para las inserciones y output para las extracciones.

• Operación push(x): Esta operación es muy sencilla. Simplemente añadimos el nuevo elemento a la pila input.
• Operación pop(): Aquí es donde ocurre la magia.
1. Primero, verificamos si la pila output está vacía.
2. Si no está vacía, significa que ya tiene elementos en el orden correcto (el más antiguo en la cima). Simplemente hacemos pop de output.
3. Si outputestá vacía, movemos todos los elementos de la pila input a la pila output. Este único trasvase invierte el orden de los elementos, colocando el más antiguo (el primero que entró en input) en la cima de output.
4. Una vez hecho el trasvase (si fue necesario), hacemos pop de output.

Análisis de Complejidad Amortizada

• push(): Al igual que en la estrategia anterior, es una operación de tiempo constante, O(1).
• pop(): La complejidad de esta operación es lo que se conoce como complejidad amortizada O(1). ¿Qué significa esto? En el peor de los casos, una operación pop individual puede costar O(n) si necesita mover 'n' elementos de input a output. Sin embargo, esta costosa operación solo ocurre cuando output está vacía. Una vez que los elementos se mueven, las siguientes 'n-1' operaciones de pop serán O(1). Si promediamos el costo total a lo largo de una secuencia larga de operaciones, el costo por operación se "amortiza" a O(1). Cada elemento solo se mueve entre pilas una vez en su vida útil.

Ejemplo Práctico

Misma secuencia: push(10), push(20), push(30), pop(), pop().

1. Estado inicial:input = [], output = [].
2. push(10):input = [10], output = [].
3. push(20):input = [10, 20], output = [].
4. push(30):input = [10, 20, 30], output = [].
5. pop():
• output está vacía. Movemos todo de input a output.
• input = [], output = [30, 20, 10].
• Hacemos pop de output. Se devuelve 10. output = [30, 20].
6. pop():
• output no está vacía. Hacemos pop de output.
• Se devuelve 20. output = [30].

Esta estrategia es generalmente preferida porque es más eficiente en escenarios con operaciones de inserción frecuentes o una mezcla equilibrada de inserciones y extracciones.

Tabla Comparativa de Estrategias

Preguntas Frecuentes (FAQ)

Conclusión

Implementar una cola con dos pilas es un brillante ejemplo de cómo se pueden combinar estructuras de datos simples para crear funcionalidades más complejas. Hemos explorado dos métodos distintos, cada uno con sus propias compensaciones de rendimiento. Comprender estas estrategias no solo te prepara para una pregunta de entrevista técnica, sino que también fortalece tus fundamentos como programador. La próxima vez que te enfrentes a un problema que parece requerir una estructura de datos que no tienes, recuerda este ejercicio: con un poco de ingenio, a menudo puedes construir lo que necesitas a partir de las herramientas que ya posees.