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
-
Pila.java:public interface Pila<T> { void push(T elemento); T pop(); T peek(); boolean estaVacia(); int tamano(); } -
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 útilT datoy su enlaceNodo<T> siguiente. - En
PilaEnlazada<T>:- El puntero
topedebe 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).
- El puntero
- En
ColaEnlazada<T>:- Mantené dos punteros:
cabeza(para extracciones) ycolaofin(para inserciones). - Ambos métodos,
enqueueydequeue, deben operar estrictamente en O(1).
- Mantené dos punteros:
3. Caso de Uso: Validador de Delimitadores
Implementá la clase ValidadorSintaxis con la firma:
public static boolean esBalanceada(String expresion);
Reglas de validación:
- Recorrer la cadena carácter por carácter.
- Si se encuentra un delimitador de apertura (
(,[,{), apilarlo. - 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.
- Al finalizar la cadena, la expresión solo es válida si la pila quedó totalmente vacía.