Estructuras de datos en Python: Pilas (stacks)

Las pilas o stacks son una estructura de datos fundamental que sigue el principio LIFO (último en entrar, primero en salir). Son esenciales en muchos algoritmos.

En este artículo, aprenderás cómo implementar una pila en Python, incluyendo sus operaciones y características principales.

¿Qué es una pila o stack?

Una pila es una estructura de datos donde el acceso está restringido a un solo extremo de la secuencia. Los elementos se empujan (push) hacia la pila para añadirlos y se extraen (pop) de la pila para retirarlos. Las pilas son muy utilizadas en algoritmos de informática y resultan especialmente útiles para tareas de análisis sintáctico (parsing).

Las características fundamentales de una pila incluyen las siguientes:

• LIFO (Last In, First Out): El último elemento que entró es el primero que sale.
• Acceso restringido: Solo puedes acceder al elemento de la cima (top) de la pila.
• Tamaño dinámico: La pila crece o decrece conforme añades o eliminas elementos.

En Python, las pilas no están integradas como una estructura de datos primitiva, pero puedes implementarla fácilmente usando el tipo collections.deque, que proporciona operaciones eficientes de inserción y eliminación en ambos extremos.

Operaciones comunes en una pila

En la tabla siguiente tienes un resumen de las operaciones que soportará tu pila:

Implementación de una pila en Python

A continuación encontrarás un ejemplo de implementación de una pila en Python:

from collections import deque
from typing import Any, Iterable, Iterator, Optional

class Stack:
    """Implement a Stack (LIFO) abstract data type."""

    def __init__(
        self,
        iterable: Optional[Iterable[Any]] = None,
        /,
    ) -> None:
        self._data: deque = deque()
        if iterable is not None:
            self._data.extend(iterable)

    def push(self, item: Any) -> None:
        """Push an item onto the stack."""
        self._data.append(item)

    def pop(self) -> Any:
        """Remove and return an item from the top of the stack."""
        try:
            return self._data.pop()
        except IndexError:
            raise IndexError("pop from an empty stack") from None

    def top(self) -> Any:
        """Return the item at the top of the stack."""
        try:
            return self._data[-1]
        except IndexError:
            raise IndexError("top from an empty stack") from None

    def is_empty(self) -> bool:
        """Return True if the stack is empty, False otherwise."""
        return len(self._data) == 0

    def __len__(self) -> int:
        return len(self._data)

    def __contains__(self, item: Any) -> bool:
        return item in self._data

    def __repr__(self) -> str:
        return f"{self.__class__.__name__}({list(self._data)})"

    __str__ = __repr__

    def __iter__(self) -> Iterator:
        yield from self._data

    def __reversed__(self) -> Iterator:
        yield from reversed(self._data)

El atributo ._data es un objeto deque del módulo collections que almacena los elementos de la pila. La clase deque proporciona operaciones de inserción y eliminación en tiempo constante O(1) en ambos extremos.

Los métodos principales te permiten ofrecer las siguientes funcionalidades:

• .push(): añade un elemento a la cima de la pila usando .append().
• .pop(): elimina y devuelve el elemento de la cima de la pila. Lanza IndexError si la pila está vacía.
• .top(): devuelve el elemento de la cima sin eliminarlo. Lanza IndexError si la pila está vacía.
• .is_empty(): comprueba si la pila está vacía.

Los métodos especiales te permiten ofrecer las siguientes funcionalidades:

• .__len__(): devuelve el número de elementos en la pila.
• .__contains__(): comprueba si un elemento está en la pila y devuelve True o False.
• .__iter__() y .__reversed__(): permiten iterar sobre los elementos de la pila en orden normal o inverso.
• .__repr__() y .__str__(): devuelven representaciones de cadena legibles.

Ejemplo de uso de la pila

En esta sección verás ejemplos prácticos de cómo crear y manipular instancias de tu clase Stack.

Inicialización

Para crear una Stack, puedes hacerlo sin argumentos o pasando un iterable:

>>> stack = Stack()
>>> stack
Stack([])

>>> stack = Stack([1, 2, 3])
>>> stack
Stack([1, 2, 3])

Empujar y extraer elementos

Puedes empujar elementos a la cima y extraerlos en orden LIFO:

>>> stack = Stack()
>>> stack.push(1)
>>> stack.push(2)
>>> stack.push(3)
>>> stack
Stack([1, 2, 3])

>>> stack.pop()
3
>>> stack.pop()
2
>>> stack
Stack([1])

Si intentas extraer un elemento de una pila vacía, obtendrás un error:

>>> stack = Stack()
>>> stack.pop()
Traceback (most recent call last):
    ...
IndexError: pop from an empty stack

Consultar la cima

El método .top() te permite ver el elemento en la cima sin eliminarlo:

>>> stack = Stack([1, 2, 3])
>>> stack.top()
3
>>> stack
Stack([1, 2, 3])

Longitud y pertenencia

Puedes consultar la longitud de la pila y verificar si un elemento está contenido en ella:

>>> stack = Stack([10, 20, 30])

>>> len(stack)
3
>>> stack.is_empty()
False

>>> 20 in stack
True
>>> 99 in stack
False

Iteración

Los métodos .__iter__() y .__reversed__() permiten iterar sobre la pila tanto hacia adelante como hacia atrás:

>>> stack = Stack([1, 2, 3])

>>> for item in stack:
...     print(item)
...
1
2
3

>>> for item in reversed(stack):
...     print(item)
...
3
2
1

Conclusión

Has aprendido cómo implementar una pila que proporciona operaciones esenciales como empujar y extraer elementos siguiendo el principio LIFO, consultar la cima, verificar pertenencia e iterar sobre sus elementos. Este conocimiento te sirve de base para entender algoritmos que dependen de pilas, como la evaluación de expresiones, el recorrido de grafos en profundidad y la gestión de historial de acciones.