Pila 🧱 — Python: Listas

• Pila
• Semántica

El tema de los algoritmos no existe por sí solo. Es importante no solo ser capaz de formular el algoritmo correcto para solucionar un problema, sino que también es vital usar la estructura de datos correcta para trabajar con los datos.

La estructura de datos es un método para organizar y almacenar información. Según la tarea, un tipo de organización puede ser más adecuado que otro. Un ejemplo común es la lista, que es una colección de elementos accesibles por un índice. Aunque parece simple, su almacenamiento en memoria es más complejo. Las listas, una forma especial de arrays, se implementan de diferentes maneras en los lenguajes de programación.

Además de las listas, existen muchas otras estructuras de datos como, por ejemplo, tablas hash, árboles, grafos, pilas, colas y demás. El uso de la estructura de datos adecuada para el problema que se está resolviendo puede simplificar drásticamente el código, eliminando una lógica complicada.

Estudiaremos algunas de las estructuras de datos mencionadas a medida que avanzamos en los cursos y proyectos de Códica. Deberás reforzar tu conocimiento sobre los demás por tu cuenta, consultando libros. Los algoritmos y las estructuras de datos, sin exagerar, son la base sobre la que se construye todo lo demás en el desarrollo.

Es importante distinguir entre tres conceptos:

• Estructura de datos
• Tipo de datos específico (o simplemente "tipo de datos")
• Tipo de datos abstractos (TDA)

Con la estructura de datos todo está claro, se ha proporcionado una definición anteriormente. Un tipo de datos también es bastante simple. Por ejemplo, los números en Python son un tipo de datos. El concepto de "tipo de datos" siempre está vinculado a un lenguaje en particular y puede ser absolutamente cualquier cosa dependiendo de las preferencias de los desarrolladores del lenguaje. En otras palabras, si los desarrolladores de Python decidieran llamar a los números un tipo de datos String, nadie podría prohibírselo, a pesar de lo absurdo que sería tal nombre para los números.

Pero los tipos de datos abstractos son un concepto teórico. Un TDA se define en su totalidad por el conjunto de operaciones que se pueden realizar con él. TDA es abstracto porque no dice nada sobre cómo se almacenan los datos y existe solo en papel y en nuestras mentes. Pero en los lenguajes específicos existen tipos específicos que implementan el TDA. A menudo se confunde el TDA con la idea de "estructura de datos", además, a menudo las estructuras de datos y el TDA tienen el mismo nombre. No es necesario meterte demasiado en estos temas, basta con tener una idea general.

En esta lección, analizaremos uno de los tipos de datos abstractos más sencillos e importantes: la pila (stack).

Pila

Una pila es una colección ordenada de elementos donde siempre se añaden y eliminan desde el mismo extremo, llamado la cima de la pila.

La pila tiene análogos en la vida real. Por ejemplo, un tubo con monedas. Las monedas se añaden al tubo una tras otra. También se extraen en orden inverso. La última moneda que ingresa al tubo es la primera que se saca.

Casi cualquier montón puede considerarse como una pila. Si no aplicamos fuerza física bruta, trabajamos con las pilas de dos formas. O colocamos un nuevo elemento (por ejemplo, un libro) en la cima de la pila, o quitamos el elemento de la cima. Por eso las pilas también se llaman "Last In First Out" (LIFO), es decir, "el último en entrar, el primero en salir".

Antes de entrar en una tarea específica, veamos el papel que juega la pila en la programación. Recuerda cómo se ejecuta cualquier programa. Una función llama a otra que, a su vez, llama a una tercera, y así sucesivamente. Después de que la ejecución llega a la función más profunda, esa función devuelve un valor y comienza el proceso inverso. Primero, las funciones más profundas terminan, luego las que están un nivel más alto, y así sucesivamente hasta que se llega a la función más externa. La llamada a una función es nada más y nada menos que agregar un elemento a la pila, y el retorno es la extracción de la pila. Así es como funciona todo a nivel de hardware. Además, si hay un error durante la ejecución del programa, a menudo se llama a su salida Stack Trace (rastreo de pila).

Otro ejemplo relacionado con la programación es el botón "atrás" en un navegador. El historial de visitas es una pila, cada nuevo enlace que se sigue se añade al historial, y el botón "atrás" extrae del historial el último elemento.

El trabajo con una pila incluye las siguientes operaciones:

• Agregar a la pila (push).
• Tomar de la pila (pop).
• Devolver el elemento en la cima de la pila sin eliminarlo (peek_back).
• Comprobar si está vacía (is_empty).
• Devolver el tamaño (size).

Las dos primeras son básicas, las demás son necesarias de vez en cuando. En Python, puedes crear una pila basada en listas. Para ello, se utilizan los métodos append(), pop() y la función len().

stack = []

stack.append(3)
print(stack) # => [ 3 ]
stack.append('Winterfall')
print(stack) # => [ 3, 'Winterfall' ]
stack.append(True)
print(stack) # => [ 3, 'Winterfall', True ]

element1 = stack.pop()
print(element1) # => True
print(stack) # => [ 3, 'Winterfall' ]

element2 = stack.pop()
print(element2) # => Winterfall
print(stack) # => [ 3 ]

Ten en cuenta que los métodos pop() y append() modifican la lista original. pop() no solo cambia la lista, sino que también devuelve el elemento que se quitó de la pila.

Consideraremos un problema cuya solución es trivial al usar una pila. Por cierto, a menudo se plantea este problema en las entrevistas para comprobar cómo de bien conoces las estructuras de datos básicas.

Problema:

Necesitas implementar una función que compruebe si los paréntesis están equilibrados. Es decir, que cada paréntesis de apertura tenga un paréntesis de cierre: (), ((()())). Aquí hay unos ejemplos de paréntesis desequilibrados: (, ((), )(. Para verificar el equilibrio, no es suficiente contar la cantidad, el orden en que aparecen también es importante.

Este problema tiene una solución simple sin necesidad de una pila, pero una pila también sirve bien (e incluso es más clara)

La solución con una pila se ve así:

1. Si tenemos un elemento de apertura, lo metemos en la pila.
2. Si es de cierre, sacamos de la pila el último elemento (obviamente, el último añadido). Si la pila está vacía, es decir, no hay ningún paréntesis de apertura, significa que la expresión no cumple con el formato requerido.
3. Si hemos llegado al final de la cadena y la pila está vacía, entonces todo está bien. Si quedan elementos en la pila, entonces la verificación falló. Esto puede suceder si había paréntesis de apertura al principio de la cadena, pero no había paréntesis de cierre al final.

Vamos a desglosarlo línea por línea:

def check_is_balanced(expression):
    # Inicializamos la pila
    stack = []
    # Pasamos por cada símbolo en la cadena
    for symbol in expression:
        # Vemos si es de apertura o de cierre
        # Si el símbolo es de apertura
        if symbol == '(':
            # Lo añadimos a la pila
            stack.append(symbol)
        # Si el símbolo es de cierre
        elif symbol == ')':
            # Intentamos sacar de la pila el último elemento
            # Si la pila está vacía, significa que no se encontró un paréntesis de apertura 
            # para el de cierre
            # Esto significa que no hay equilibrio, devolvemos False
            if not stack:
                return False
            stack.pop()

    # Comprobamos si la pila está vacía
    # Si quedan elementos en la pila, entonces no todos los paréntesis de apertura están cerrados,
    # lo que significa que no hay equilibrio
    return len(stack) == 0

Supongamos que la siguiente cadena llegó como entrada a la función: ((). A continuación, se describe los pasos clave en la ejecución de la función de comprobación:

1. El primer paréntesis ( se añade a la pila, ya que es de apertura.
2. El siguiente paréntesis ( también se añade a la pila por la misma razón.
3. El último ) es de cierre, se extrae de la pila el último paréntesis añadido.
4. Aún queda un elemento en la pila, lo que significa que no hay equilibrio.

Semántica

Puede que te sientas tentado a usar estas funciones en tu práctica diaria. Por ejemplo, para extraer el último elemento de una lista. A pesar de que el método pop() realmente permite hacer esto, tal uso es altamente desaconsejable por varias razones:

1. El efecto secundario de esta operación es la modificación de la lista original. Incluso si la lista no se va a utilizar después, este tipo de código introduce problemas potenciales y te obligará a reescribirlo en el futuro.

2. Se rompe la semántica. Cada herramienta debe usarse para su función específica, de lo contrario, nacerá un código que declara una cosa, pero en realidad hace otra. Cualquier programador experimentado que ve pop() inmediatamente asume que la lista se utiliza como una pila en esta parte del programa. Si este no es el caso, se requerirán esfuerzos mentales adicionales para entender lo que está pasando.

Para extraer el último elemento, es mejor usar la recuperación de elementos por índice.

items = ['primero', 'segundo', 'tercero']
items[-1] # 'tercero'