Pilas en Java

/**
 * Interfaz genérica para una estructura de datos tipo Pila (Stack).
 * @param <E> Tipo de los elementos almacenados.
 */
public interface Pila<E> {

    /** Inserta un elemento en la cima de la pila. */
    void push(E elemento);

    /** Extrae y devuelve el elemento de la cima. */
    E pop();

    /** Devuelve el elemento de la cima sin eliminarlo. */
    E peek();

    /** Devuelve true si la pila está vacía. */
    boolean isEmpty();

    /** Devuelve el número de elementos en la pila. */
    int size();
}

/**
 * Implementación de Pila usando un array interno.
 * Capacidad fija definida en la construcción.
 */
public class PilaArray<E> implements Pila<E> {

    private static final int CAPACIDAD_DEFAULT = 1000;
    private E[] datos;
    private int top;  // índice de la cima (-1 = vacía)

    /** Constructor con capacidad personalizada. */
    @SuppressWarnings("unchecked")
    public PilaArray(int capacidad) {
        datos = (E[]) new Object[capacidad];
        top = -1;
    }

    /** Constructor por defecto: capacidad de 1000 elementos. */
    public PilaArray() {
        this(CAPACIDAD_DEFAULT);
    }

    @Override
    public void push(E elemento) {
        if (top == datos.length - 1) {
            throw new IllegalStateException("Pila llena: no se puede insertar.");
        }
        datos[++top] = elemento;  // incrementa top y luego inserta
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Pila vacía: no se puede extraer.");
        }
        E elemento = datos[top];
        datos[top] = null;  // ayuda al recolector de basura
        top--;
        return elemento;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Pila vacía: no hay cima.");
        }
        return datos[top];
    }

    @Override
    public boolean isEmpty() {
        return top == -1;
    }

    @Override
    public int size() {
        return top + 1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("Pila [cima → ");
        for (int i = top; i >= 0; i--) {
            sb.append(datos[i]);
            if (i > 0) sb.append(", ");
        }
        sb.append("]");
        return sb.toString();
    }
}

public class DemoPilaArray {
    public static void main(String[] args) {
        PilaArray<String> pila = new PilaArray<>(5);

        pila.push("Java");
        pila.push("Python");
        pila.push("JavaScript");

        System.out.println(pila);            // Pila [cima → JavaScript, Python, Java]
        System.out.println("Cima: " + pila.peek());   // JavaScript
        System.out.println("Tamaño: " + pila.size()); // 3

        String extraido = pila.pop();
        System.out.println("Extraído: " + extraido);  // JavaScript
        System.out.println(pila);            // Pila [cima → Python, Java]
    }
}

/**
 * Nodo genérico para estructuras enlazadas.
 */
public class Nodo<E> {
    private E dato;
    private Nodo<E> siguiente;

    public Nodo(E dato, Nodo<E> siguiente) {
        this.dato = dato;
        this.siguiente = siguiente;
    }

    public E getDato()              { return dato; }
    public Nodo<E> getSiguiente()   { return siguiente; }
    public void setSiguiente(Nodo<E> sig) { this.siguiente = sig; }
}

/**
 * Implementación de Pila usando nodos enlazados.
 * Tamaño dinámico: crece y decrece según las operaciones.
 */
public class PilaEnlazada<E> implements Pila<E> {

    private Nodo<E> top;     // nodo en la cima
    private int longitud;    // número de elementos

    public PilaEnlazada() {
        top = null;
        longitud = 0;
    }

    @Override
    public void push(E elemento) {
        // El nuevo nodo apunta al antiguo top
        top = new Nodo<>(elemento, top);
        longitud++;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Pila vacía: no se puede extraer.");
        }
        E dato = top.getDato();
        top = top.getSiguiente();  // el siguiente se convierte en nueva cima
        longitud--;
        return dato;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Pila vacía: no hay cima.");
        }
        return top.getDato();
    }

    @Override
    public boolean isEmpty() {
        return top == null;
    }

    @Override
    public int size() {
        return longitud;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("Pila [cima → ");
        Nodo<E> actual = top;
        while (actual != null) {
            sb.append(actual.getDato());
            if (actual.getSiguiente() != null) sb.append(", ");
            actual = actual.getSiguiente();
        }
        sb.append("]");
        return sb.toString();
    }
}

import java.util.Stack;

public class DemoStackJDK {
    public static void main(String[] args) {
        Stack<Integer> pila = new Stack<>();

        // push: añadir elementos
        pila.push(10);
        pila.push(20);
        pila.push(30);

        System.out.println("Pila: " + pila);           // [10, 20, 30]
        System.out.println("Cima: " + pila.peek());     // 30
        System.out.println("Tamaño: " + pila.size());   // 3

        // pop: extraer elemento de la cima
        int extraido = pila.pop();
        System.out.println("Extraído: " + extraido);    // 30
        System.out.println("Pila: " + pila);            // [10, 20]

        // search: buscar posición desde la cima (1 = cima)
        int posicion = pila.search(10);
        System.out.println("Posición de 10: " + posicion);  // 2

        // empty: comprobar si está vacía
        System.out.println("¿Vacía? " + pila.empty());  // false
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

public class DemoDeque {
    public static void main(String[] args) {
        Deque<String> pila = new ArrayDeque<>();

        // push: inserta en la cima (equivale a addFirst)
        pila.push("Primero");
        pila.push("Segundo");
        pila.push("Tercero");

        System.out.println("Pila: " + pila);          // [Tercero, Segundo, Primero]
        System.out.println("Cima: " + pila.peek());    // Tercero

        // pop: extrae de la cima (equivale a removeFirst)
        String extraido = pila.pop();
        System.out.println("Extraído: " + extraido);   // Tercero

        // Iterar (desde la cima hacia la base)
        System.out.println("Recorrido:");
        for (String elemento : pila) {
            System.out.println("  → " + elemento);
        }
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Verifica si los paréntesis, corchetes y llaves de una expresión
 * están correctamente balanceados usando una pila.
 */
public class EvaluadorParentesis {

    /**
     * Verifica si la cadena tiene delimitadores balanceados.
     * @param expresion Cadena a evaluar
     * @return true si está balanceada, false en caso contrario
     */
    public static boolean estaBalanceada(String expresion) {
        Deque<Character> pila = new ArrayDeque<>();

        for (char c : expresion.toCharArray()) {
            // Si es un delimitador de apertura, lo apilamos
            if (c == '(' || c == '[' || c == '{') {
                pila.push(c);
            }
            // Si es un delimitador de cierre, verificamos
            else if (c == ')' || c == ']' || c == '}') {
                if (pila.isEmpty()) {
                    return false;  // cierre sin apertura
                }
                char apertura = pila.pop();
                if (!sonPareja(apertura, c)) {
                    return false;  // no coinciden
                }
            }
            // Cualquier otro carácter se ignora
        }

        return pila.isEmpty();  // no deben quedar aperturas sin cerrar
    }

    /** Verifica si un par de delimitadores coinciden. */
    private static boolean sonPareja(char apertura, char cierre) {
        return (apertura == '(' && cierre == ')')
            || (apertura == '[' && cierre == ']')
            || (apertura == '{' && cierre == '}');
    }

    public static void main(String[] args) {
        String[] pruebas = {
            "{[()]}",           // ✅ balanceada
            "((()))",           // ✅ balanceada
            "{[(])}",           // ❌ cruce de delimitadores
            "((())",            // ❌ falta cierre
            "public static void main(String[] args) {}", // ✅
            "",                 // ✅ cadena vacía = balanceada
        };

        for (String expr : pruebas) {
            boolean resultado = estaBalanceada(expr);
            System.out.printf("%-50s → %s %s%n",
                "\"" + expr + "\"",
                resultado ? "✅" : "❌",
                resultado ? "Balanceada" : "No balanceada");
        }
    }
}

/* Salida esperada:
 * "{[()]}"                                    → ✅ Balanceada
 * "((()))"                                    → ✅ Balanceada
 * "{[(])}"                                    → ❌ No balanceada
 * "((())"                                     → ❌ No balanceada
 * "public static void main(String[] args) {}" → ✅ Balanceada
 * ""                                          → ✅ Balanceada
 */

// ❌ Error: pop sin verificar
Deque<Integer> pila = new ArrayDeque<>();
int valor = pila.pop();  // NoSuchElementException

// ✅ Correcto: verificar antes
if (!pila.isEmpty()) {
    int valor = pila.pop();
}
// O usar pollFirst() que devuelve null si está vacía
Integer valor = pila.pollFirst();

// ❌ Stack permite acceso por índice (rompe LIFO)
Stack<String> pila = new Stack<>();
pila.push("A");
pila.push("B");
pila.push("C");
String medio = pila.get(1);  // "B" — ¡acceso directo al medio!

// ✅ ArrayDeque no expone acceso por índice
Deque<String> pila2 = new ArrayDeque<>();
pila2.push("A");
pila2.push("B");
pila2.push("C");
// pila2.get(1);  // ¡Error de compilación! No existe el método

// ❌ ArrayDeque no acepta null
Deque<String> pila = new ArrayDeque<>();
pila.push(null);  // NullPointerException

// ✅ Si necesitas almacenar null, usa LinkedList como Deque
Deque<String> pila = new java.util.LinkedList<>();
pila.push(null);  // Funciona (pero es mala práctica)