Base teórica de pilas y colas

Las pilas son estructuras de datos LIFO (Last In, First Out) donde el último elemneto agregado es el primero en salir. Las colas son FIFO (First In, First Out) donde el primer elemento agregdao es el primero en retirarse. Estas propiedades determinan sus aplicaciones prácticas.

Implementación de cola con dos pilas

Para simular una cola usando pilas, se emplean dos pilas: una para inserción y otra para extracción. Cuando se extrae un elemento y la pila de extracción está vacía, se transfieren todos los elementos de la pila de inserción a la de extracción, invirtiendo el orden.

class ColaSimulada:

    def __init__(self):
        self.almacen_entrada = []
        self.almacen_salida = []

    def encolar(self, valor):
        self.almacen_entrada.append(valor)

    def desencolar(self):
        if self.esta_vacia():
            return None
        if not self.almacen_salida:
            while self.almacen_entrada:
                self.almacen_salida.append(self.almacen_entrada.pop())
        return self.almacen_salida.pop()

    def frente(self):
        if self.esta_vacia():
            return None
        if not self.almacen_salida:
            while self.almacen_entrada:
                self.almacen_salida.append(self.almacen_entrada.pop())
        return self.almacen_salida[-1]

    def esta_vacia(self):
        return len(self.almacen_entrada) == 0 and len(self.almacen_salida) == 0

Implementación de pila con una cola

Una sola cola puede emular el comportamiento LIFO de una pila. Para extraer el último elemento agregado (tope de la pila), se rotan los elementos N-1 veces, moviendo el primer elemento al final de la cola en cada iteración. Esto sitúa el elemento deseado en la posición frontal.

from collections import deque

class PilaSimulada:

    def __init__(self):
        self.cola = deque()

    def apilar(self, valor):
        self.cola.append(valor)

    def desapilar(self):
        if self.esta_vacia():
            return None
        for _ in range(len(self.cola) - 1):
            self.cola.append(self.cola.popleft())
        return self.cola.popleft()

    def tope(self):
        if self.esta_vacia():
            return None
        return self.cola[-1]

    def esta_vacia(self):
        return len(self.cola) == 0

Validación de paréntesis balanceados

Este problema requiere verificar que todos los paréntesis se abran y cierran en el orden correcto. Una pila rastrea los paréntesis de apertura esperados. Se procesan los caracteres: si es un paréntesis de apertura, se empuja su correspondiente paréntesis de cierre; si es de cierre, se verifica contra el tope de la pila.

def validar_parentesis(cadena):
    if len(cadena) % 2 != 0:
        return False
    
    pila = []
    pares = {')': '(', ']': '[', '}': '{'}
    
    for caracter in cadena:
        if caracter in pares.values():
            pila.append(caracter)
        elif caracter in pares:
            if not pila or pila.pop() != pares[caracter]:
                return False
        else:
            return False
    
    return len(pila) == 0

Eliminación de duplicados adyacentes

Para reducir una cadena eliminando caracteres duplicados consecutivos, se utiliza una pila como búfer. Se compara cada carácter con el elemento en el tope de la pila. Si coinciden, se desapila (eliminando ambos); de lo contrario, se apila el carácter actual.

def reducir_cadena(cadena):
    buffer = []
    
    for caracter in cadena:
        if buffer and buffer[-1] == caracter:
            buffer.pop()
        else:
            buffer.append(caracter)
    
    return ''.join(buffer)