Fundamentos de Estructuras de Datos: Implementación y Clasificación (Pilas, Colas y Recursividad)

Conceptos Fundamentales de Estructuras de Datos

Una Estructura de Datos es una colección de datos junto con las operaciones permitidas sobre dichos datos.

Clasificación de Estructuras de Datos

• Lineales
  • Secuenciales:
    • Arreglos (Arrays)
    • Matrices
  • No Secuenciales:
    • Listas Lineales (Simples)
    • Listas Doblemente Ligadas
    • Etc.
• No Lineales
  • Árboles
    • Binarios
    • Binarios Balanceados
    • Binarios de Búsqueda (BST)
  • Grafos

Colecciones Genéricas o Parametrizadas

Las colecciones genéricas o parametrizadas permiten forzar la seguridad de los tipos en tiempo de compilación, dentro de las colecciones.

Pila (Stack)

Una Pila es una lista de elementos en la cual puedes insertar y eliminar elementos por uno solo de los extremos, conocido como tope. Son estructuras de tipo LIFO (Last In - First Out: Último en Entrar - Primero en Salir).

Es una colección de datos que solo puede ser accedida por un tope.

Implementación Básica de Pila (Pseudo-código)

int tope = -1;
T[] pila;

boolean estaVacia() {
    if (tope == -1) {
        return true;
    }
    return false;
}

boolean estaLlena() {
    if (tope == pila.length) {
        return true;
    }
    return false;
}

T pop() {
    T dato = null;
    if (estaVacia()) {
        sout("Subdesbordamiento (Underflow)");
    } else {
        dato = pila[tope];
        tope--;
    }
    return dato;
}

void push(T dato) {
    if (estaLlena()) {
        sout("Desbordamiento (Overflow)");
    } else {
        tope++;
        pila[tope] = dato;
    }
}

T peek() {
    T dato = null;
    dato = pila[tope];
    return dato;
}

Recursividad

Se dice que un proceso es recursivo cuando se llama a sí mismo. La recursividad es una de las formas de control más importantes de la programación.

La base (o caso base) no es recursiva y es el punto tanto de partida como de terminación de la definición recursiva.

Cola (Queue)

Una Cola es una colección de objetos que son insertados y removidos de acuerdo al principio FIFO (First-In, First-Out: Primero en Entrar, Primero en Salir).

Tipos de Colas

• Simples
• Circulares
• Dobles (Deque)
• Con Prioridad

Implementación de Cola Simple (ColaS<T>)

T dato;
T[] cola;
int inicio = -1, fin = -1;

void InsertarDato(T dato) {
    if (fin < cola.length - 1) {
        fin = fin + 1;
        cola[fin] = dato;
        if (inicio == -1) {
            inicio = 0;
        }
    } else {
        sout("Desbordamiento (Overflow)");
    }
}

T Eliminar() {
    T dato = null;
    if (inicio != -1) {
        dato = cola[inicio];
        if (inicio == fin) {
            inicio = -1;
            fin = -1;
        } else {
            inicio = inicio + 1;
        }
        return dato;
    } else {
        sout("Subdesbordamiento (Underflow)");
        return null;
    }
}

Implementación de Cola Circular (ColaC<T>)

T dato;
T[] colaCir;
int inicio = -1, fin = -1;

void insertar(T dato) {
    // Condición de cola llena
    if ((fin == colaCir.length - 1 && inicio == 0) || ((fin + 1) == inicio)) {
        sout("Desbordamiento (Overflow)");
    } else {
        if (fin == colaCir.length - 1) {
            fin = 0;
        } else {
            fin = fin + 1;
        }
        colaCir[fin] = dato;
        if (inicio == -1) {
            inicio = 0;
        }
    }
}

T eliminar() {
    T dato = null;
    if (inicio == -1) {
        sout("Subdesbordamiento (Underflow)");
    } else {
        dato = colaCir[inicio];
        if (inicio == fin) {
            inicio = -1;
            fin = -1;
        } else if (inicio == colaCir.length - 1) {
            inicio = 0;
        } else {
            inicio = inicio + 1;
        }
    }
    return dato;
}

Cola Doble (Deque)

Una Cola Doble (Deque) es una colección ordenada de ítems similar a la cola. Tiene dos extremos, frente y final, y los ítems permanecen posicionados en la colección. Permite inserciones y eliminaciones por ambos extremos.

Implementación de Cola Doble (Pseudo-código)

Object[] ArregloC;
int frente = 0, fondo = 0;
int numE;
int capacidadE = 5;

boolean estaVacia() {
    return (fondo < frente);
}

void insertar(Object x) {
    if (fondo == -1) {
        fondo++;
        ArregloC[fondo] = x;
    } else {
        fondo++;
        if (fondo == capacidadE) {
            sout("No hay espacio (Desbordamiento)");
        } else {
            ArregloC[fondo] = x;
        }
    }
}

void eliminar() {
    if (estaVacia()) {
        sout("La cola está vacía (Subdesbordamiento)");
    } else {
        // Desplazamiento de elementos para simular eliminación por el frente
        for (int i = frente; i < fondo; i++) {
            ArregloC[i] = ArregloC[i + 1];
        }
        ArregloC[fondo] = null;
        fondo--;
    }
}

Cola de Prioridad (ColaP)

Una Cola de Prioridad es una colección de elementos donde cada elemento tiene asociado un valor susceptible de ordenación denominado prioridad.

Una cola de prioridad se caracteriza por admitir inserciones de nuevos elementos y la consulta y eliminación del elemento de mínima prioridad.

Ejemplo de Clase Comparable para Prioridad (Java)

public class Persona implements Comparable<Persona> {
    private String nombre;
    // 1: normal, 2: tercera edad, 3: embarazada
    private int tipo; 

    public Persona(String nombre, int tipo) {
        this.nombre = nombre;
        this.tipo = tipo;
    }

    public String getNombre() {
        return nombre;
    }

    public void setNombre(String nombre) {
        this.nombre = nombre;
    }

    public int getTipo() {
        return tipo;
    }

    public void setTipo(int tipo) {
        this.tipo = tipo;
    }

    public int compareTo(Persona o) {
        if (tipo < o.getTipo()) {
            return 1; 
        } else if (tipo > o.getTipo()) {
            return -1; 
        } else {
            return 0; 
        }
    }
}