Estructuras de datos genericos

TEMA 8
EDAs lineales y su jerarquía Java
Implementación de las Edas Lineales
EJERCICIOS RESUELTOS

Ejercicio 1.- Diséñese la clase LEGPila que implementa el interfaz Pila utilizando una
ListaEnlazada. Estúdiese la complejidad temporal de sus métodos.

Solución:
public class LEGPila implements Pila {
// Atributos
protected NodoLEG tope;
// Constructor
public LEGPila() {
tope = null;}
// Inserta x en el tope de la Pila
public void apilar(E x) {
tope = new NodoLEG(x, tope);
}
// SII !esVacia(): elimina el dato del tope de la Pila y lo devuelve
public E desapilar() {
Edato = tope.dato;
tope = tope.siguiente;
return dato;
}
// SII !esVacia(): obtiene el dato que ocupa el tope de la Pila
public E tope() {
return tope.dato;
}
// Comprueba si la Pila está o novacía
public boolean esVacia() {
return (tope == null);
}
}

Todos los métodos son de orden constante.

Ejercicio 2.- Enriquecer el interfaz Pila y las clases ArrayPila y LEGPila con dos
nuevasoperaciones:
 E borraBase(), que borra el dato situado en la base de la Pila
 void topeBase(), que intercambia el dato que ocupa el tope de la Pila con el
que ocupa su base
Solución:
publicinterface PilaExt extends Pila {
E borraBase();
// SII !esVacia(): borra la base
void topeBase();
// SII !esVacia(): intercambia tope y base
}
public class ArrayPilaExt
extends ArrayPilaimplements PilaExt {
public E borraBase() {
// SII !esVacia()
E base = elArray[0];
for (int i = 1; i = talla)
throw new PosicionIncorrecta(“Índice no válido”);
return elArray[indice];
}
public booleanesVacia() {
return (talla == 0);
}
public E borrar(E x) throws ElementoNoEncontrado {
int indice = indiceDe(x);
if (indice == -1) throw new ElementoNoEncontrado(x + “no está”);
E res =elArray[indice];
talla--;
for (int i = indice; i < talla; i++)
elArray[i] = elArray[i+1];
return res;
}
public int talla() {
return talla;
}
@SuppressWarnings(“unchecked”)
public E[] toArray() {...