Programación

Stack

Stack (pilas)

Introducción a las pilas

Una pila es una estructura de datos que opera bajo el principio LIFO (Last In, First Out), lo que significa que el último elemento en entrar es el primero en salir. Este concepto se puede ilustrar con el ejemplo clásico de una torre de platos en un restaurante:

  • Los platos limpios se apilan uno sobre otro.
  • Cuando un cliente necesita un plato, se toma el que está en la parte superior de la torre.

Esta analogía refleja cómo funciona una pila: los elementos se apilan y se desapilan por un mismo extremo, conocido como la cima.

Operaciones fundamentales

Las pilas cuentan con tres operaciones básicas que permiten su manipulación:

  1. Apilar (Push):
    • Introduce un elemento en la pila.
    • En una implementación basada en listas enlazadas, esto equivale a insertar un nodo al principio de la lista.
    • Ejemplo:
      • Pila inicial: Vacía.
      • Se apila el elemento 25 → [25].
      • Se apila el elemento 41 → [41, 25].
  2. Cima (Peek):
    • Devuelve el elemento en la cima de la pila sin eliminarlo.
    • Si la pila está vacía, se puede devolver un valor nulo o lanzar un error.
    • Ejemplo:
      • Pila: [41, 25].
      • Cima: 41.
  3. Desapilar (Pop):
    • Elimina y devuelve el elemento en la cima de la pila.
    • En una implementación con listas enlazadas, esto equivale a eliminar el nodo de la cabeza.
    • Ejemplo:
      • Pila: [41, 25].
      • Se desapila 41 → [25].

Operaciones adicionales

  1. Está vacía:
    • Comprueba si la pila no tiene elementos.
    • Es útil para evitar errores al intentar desapilar o consultar la cima de una pila vacía.
  2. Tamaño:
    • Devuelve el número de elementos en la pila.
    • Permite gestionar el uso de memoria o detectar desbordamientos.

Implementación de pilas

Usando listas enlazadas

  • Cada nodo contiene un valor y un puntero al siguiente nodo.
  • Las operaciones de apilar, desapilar y consultar la cima se realizan sobre la cabeza de la lista.
  • Ventajas:
    • No hay límite predefinido de tamaño.
    • Fácil de implementar.
  • Desventajas:
    • Requiere más memoria debido a los punteros.

Usando arrays

  • Se utiliza un array de tamaño fijo con un puntero que indica la posición del último elemento.
  • Operaciones:
    • Apilar: Insertar en la posición indicada por el puntero y avanzar el puntero.
    • Desapilar: Retroceder el puntero y devolver el elemento en la posición previa.
    • Cima: Consultar el elemento en la posición indicada por el puntero menos uno.
  • Ventajas:
    • Más eficiente en términos de memoria.
  • Desventajas:
    • Tamaño fijo (puede llevar a desbordamientos o desperdicio de memoria).

Casos especiales

  1. Desbordamiento de pila (Stack Overflow):
    • Ocurre cuando se intenta apilar un elemento en una pila implementada con un array que ya está lleno.
    • Solución: Aumentar el tamaño del array o lanzar un error.
  2. Pila vacía:
    • Ocurre cuando se intenta desapilar o consultar la cima de una pila vacía.
    • Solución: Comprobar si la pila está vacía antes de realizar estas operaciones.