Contexto

Las estructuras lineales restringidas son piezas angulares de la ingeniería de software:

  • Una Pila (Stack) restringe las operaciones al principio LIFO (Last-In, First-Out): el último elemento ingresado es el primero en salir. Modela la pila de llamadas de la JVM, el mecanismo de deshacer (undo) y la evaluación de expresiones sintácticas.
  • Una Cola (Queue) impone la semántica FIFO (First-In, First-Out): el primer elemento ingresado es el primero en ser procesado. Modela colas de mensajes, spoolers de impresión y algoritmos de recorrido en anchura.

Ambas estructuras exigen que sus operaciones primordiales se ejecuten en tiempo constante O(1).

Consigna

Vas a construir desde cero las implementaciones enlazadas de ambos TADs en Java, garantizando contratos de interfaz, encapsulamiento estricto y resolución algorítmica.

1. Interfaz y Especificación

  1. Pila.java:

    public interface Pila<T> {
        void push(T elemento);
        T pop();
        T peek();
        boolean estaVacia();
        int tamano();
    }
  2. Cola.java:

    public interface Cola<T> {
        void enqueue(T elemento);
        T dequeue();
        T peek();
        boolean estaVacia();
        int tamano();
    }

2. Implementaciones con Nodos Enlazados

  • Diseñá una clase privada Nodo<T> con su carga útil T dato y su enlace Nodo<T> siguiente.
  • En PilaEnlazada<T>:
    • El puntero tope debe referenciar siempre al último nodo ingresado.
    • push(T elemento) inserta un nuevo nodo que pasa a ser el nuevo tope en O(1).
    • pop() desvincula el nodo del tope, actualiza la referencia y devuelve su dato en O(1).
  • En ColaEnlazada<T>:
    • Mantené dos punteros: cabeza (para extracciones) y cola o fin (para inserciones).
    • Ambos métodos, enqueue y dequeue, deben operar estrictamente en O(1).

3. Caso de Uso: Validador de Delimitadores

Implementá la clase ValidadorSintaxis con la firma:

public static boolean esBalanceada(String expresion);

Reglas de validación:

  1. Recorrer la cadena carácter por carácter.
  2. Si se encuentra un delimitador de apertura ((, [, {), apilarlo.
  3. Si se encuentra un delimitador de cierre (), ], }):
    • Si la pila está vacía, no hay apertura correspondiente $\rightarrow$ inválida.
    • Si la cima de la pila no coincide con el tipo de delimitador $\rightarrow$ inválida.
    • Si coincide, desapilar el correspondiente.
  4. Al finalizar la cadena, la expresión solo es válida si la pila quedó totalmente vacía.