Estructura de datos - S1 Estuctura de datos lineales

Estructuras de datos lineales

Estructuras de datos y algoritmos

Empezar

Índice

Estructuras de datos lineales

01 - Colecciones o bolsas

05 - Colas

02 - Conjuntos

06 - Colas de prioridad

03 - Listas y Vectores

07 - Mapas

04 - Pilas

Estructuras de datos lineales

01

Colecciones o bolsas

Estructuras de datos lineales

La colección es un ADT que permite almacenar grupos de objetos llamados elementos

• pueden estar repetidos
• no es preciso almacenar ninguna relación de orden o secuencia

También se llaman bolsas

Colecciones o bolsas

Estructuras de datos lineales

Operaciones básicas de las colecciones

+ info

Estructuras de datos lineales

Las colecciones en Java

Las colecciones se representan en java por la interfaz

• No existe ninguna clase que la implemente directamente
• Puede usarse un conjunto o lista, ya que son extensiones de ella
• si queremos guardar elementos repetidos usar una lista

• O definir tu propia implementación

Los métodos que modifican la colección suelen retornar un booleano: • true, si se ha modificado • false, si no se ha modificado

Estructuras de datos lineales

La interfaz Collection

// Bulk operations boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); //optional boolean removeAll(Collection<?> c); //optional boolean retainAll(Collection<?> c); //optional void clear(); //optional // Array operations Object[] toArray(); <T> T[] toArray(T[] a); }

public interface Collection<E> extends Iterable<E> { // Basic operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(E element); //optional boolean remove(Object element); //optional Iterator<E> iterator();

Estructuras de datos lineales

Parámetros genéricos comodín

El carácter ? en los parámetros genéricos se usa como comodín: - ?: para indicar cualquier clase - ? extends E: para indicar a E, o cualquier subclase de E

+ info

Estructuras de datos lineales

Constructores de las colecciones

Aunque no aparece en la interfaz (las interfaces no tienen constructores), las clases que implementan la colección disponen de dos constructores• constructor sin parámetros: crea la colección vacía • constructor con un parámetro que es una colección: crea la nueva colección con una copia de los valores del argumento

Estructuras de datos lineales

Constructores de las colecciones

La clase Collections tiene muchas operaciones para manejar colecciones • singleton: retorna un conjunto no modificable de un solo elemento • singletonList: ídem, retornando una lista • singletonMap: ídem, retornando un mapa Dispone también de operaciones para obtener colecciones no modificables vacías: •emptySet •emptyList •emptyMap

Estructuras de datos lineales

Operaciones con múltiples datos

Estructuras de datos lineales

Operaciones con arrays

Se prefiere la segunda versión, por ser más segura

+ info

Estructuras de datos lineales

Ejemplos de uso

Una aplicación de una colección es almacenar una lista de visitas a un lugar• una misma persona puede visitar el lugar varias veces • no interesa el orden en el que se hacen • interesa si alguien ha visitado el lugar o no, y cuántas veces Ejercicio: • Crear una clase capaz de almacenar en un atributo una colección de nombres de personas (Strings) • Escribir un método para añadir una visita • Escribir un método para saber cuántas visitas ha hecho una persona (que deje la colección igual que estaba)

Estructuras de datos lineales

02

Conjuntos

Estructuras de datos lineales

Un conjunto es un ADT que permite almacenar grupos de objetos llamados elementos de modo que• no pueden estar repetidos • no es preciso almacenar ninguna relación de orden o secuencia Además suelen tener operaciones para operar con ellos • intersección • unión • diferencia

Conjuntos

Estructuras de datos lineales

Operaciones básicas de los conjuntos

+ info

Estructuras de datos lineales

Operaciones básicas de los conjuntos (cont.)

+ info

Estructuras de datos lineales

Conjuntos en Java: La interfaz Set

//Bulk operations boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); //optional boolean removeAll(Collection<?> c); //optional boolean retainAll(Collection<?> c); //optional void clear(); //optional // Array operations Object[] toArray(); <T> T[] toArray(T[] a); }

public interface Set<E> extends Collection<E> { // Basic operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(E element); //optional boolean remove(Object element); //optional Iterator<E> iterator();

Estructuras de datos lineales

La interfaz Set

Puede verse que la interfaz es idéntica a la de las colecciones Las operaciones intersección, unión y diferencia se pueden realizar así:

Estructuras de datos lineales

Implementación de los conjuntos

La implementación más usual y eficiente es HashSet • utiliza una tabla de troceado (hash) para guardar los elementos • es muy eficiente - las operaciones de pertenencia, inserción y borrado suelen ser O(1) • no ordena los elementos

Estructuras de datos lineales

La clase del elemento debe disponer de un método hashCode() para convertir un objeto de esa clase en un dato numérico llamado clavepublic int hashCode() El principal problema es la resolución de colisiones • Cuando dos datos tienen la misma clave la eficiencia se reduce • El método hashCode() debe distribuir las claves de modo muy homogéneo Veremos las implementaciones más adelante • de momento, usaremos el hashCode()de la clase String

Las tablas de troceado

Estructuras de datos lineales

Tamaño de la tabla

Las tablas de troceado deben tener espacio suficiente para guardar todos los elementos con holgura• se intenta que esté ocupada al 75% como máximo Cuando se añaden elementos, si se supera el límite de ocupación, se recrea la tabla usando una más grande• es una operación compleja (O(n)) • hay que copiar todos los elementos a la nueva tabla La clase HashSet tiene un constructor al que se le pasa el tamaño inicial de la tabla (int)• Si conocemos el tamaño máximo, podemos evitar la operación de recrear la tabla

Estructuras de datos lineales

Ejemplo de función de troceado

Ejemplo de uso de los conjuntos

Estructuras de datos lineales

03

Listas y Vectores

Estructuras de datos lineales

Una lista es una secuencia de objetos ordenados, en la que se dispone de un iterador especial, con el que se puede:• insertar o eliminar elementos en cualquier posición • recorrer los elementos de la lista hacia adelante y opcionalmente, hacia atrás • etc. Algunas listas (denominadas Vectores) disponen de acceso posicional eficiente, con un índice, como en las tablas El orden es el que define la secuencia de elementos; no necesariamente es su orden natural

Listas y Vectores

Estructuras de datos lineales

Operaciones básicas de las listas

El iterador de lista es un objeto que permite recorrer los elementos de la lista y operar con ellaDispone de un cursor que se sitúa entre dos elementos: previo y próximo

+ info

Estructuras de datos lineales

Operaciones básicas de los iteradores de lista

+ info

Estructuras de datos lineales

Operaciones de acceso posicional

Hay listas llamadas vectores, que se usan como una tabla Dependiendo de la implementación de la lista, el acceso puede ser O(1) (vectores) u O(n) (listas secuenciales) - luego hay que sumarle el tiempo de la operación solicitada

+ info

Estructuras de datos lineales

La interfaz List de Java

public interface List<E> extends Collection<E> { // Positional access E get(int index); E set(int index, E element); //optional boolean add(E element); //optional void add(int index, E element); //optional E remove(int index); //optional boolean addAll(int index, Collection<? extends E> c); //optional // Search int indexOf(Object o); int lastIndexOf(Object o);

// Iteration ListIterator<E> listIterator(); ListIterator<E> listIterator(int index); // Range-view List<E> subList(int from, int to); }

+ info

Estructuras de datos lineales

public interface ListIterator<E> extends Iterator<E> { boolean hasNext(); E next(); boolean hasPrevious(); E previous(); int nextIndex(); int previousIndex(); void remove(); //optional void set(E e); //optional void add(E e); //optional }

La interfaz ListIterator de Java

+ info

Estructuras de datos lineales

Implementaciones de las listas

Hay dos implementaciones de listas en las colecciones Java: • ArrayList: Es una lista implementada en un array - el acceso posicional es muy eficiente: O(1) - las operaciones de inserción y extracción de cualquier posición (excepto al final) son O(n)- necesita recrear el array, cuando se queda pequeño - se le puede dar el tamaño inicial • LinkedList: Es una lista implementada mediante una estructura doblemente enlazada- cada elemento tiene una referencia al previo y siguiente - el acceso posicional es O(n) - la inserción y extracción con el iterador de listas es O(1)

Ejemplos con listas

Estructuras de datos lineales

Escribir un algoritmo que reemplace todos los elementos de una lista que coincidan con un elemento, por otro elementoEscribir una clase que represente una baraja de cartas españolas, con las siguientes operaciones • constructor: inicialmente la baraja contiene las 40 cartas ordenadas • barajar: para cada carta i desde la última hasta la segunda se intercambia esa carta con la de la casilla de índice aleatorio entre 0 e i • repartir: retorna una lista que contiene las num últimas cartas de la baraja, y las elimina de la baraja Hacer un programa de prueba para la baraja

Ejemplo 1

Ejemplo 2

Estructuras de datos lineales

04

Pilas

Estructuras de datos lineales

Una pila (o stack) es una lista especial en la que todos los elementos se insertan o extraen por un extremo de la lista (LIFO) La implementación • implementa estas operaciones eficientemente • aprovecha las limitaciones para simplificar

Pilas

Estructuras de datos lineales

Operaciones básicas de las pilas

+ info

Estructuras de datos lineales

Las colecciones Java no disponen de ninguna interfaz específica para las pilasComo implementación puede usarse una LinkedList, pues dispone de operaciones para insertar y extraer elementos por un extremopublic E getFirst(); public E removeFirst(); public void addFirst(E o); Los dos primeros lanzan NoSuchElementException si la pila está vacía

Interfaz Java para la Pila

+ info

Estructuras de datos lineales

Interfaz Pila propia

La hacemos sin iterador, para simplificar import java.util.*; public interface Pila<E> { void apila(E e); E desapila() throws NoSuchElementException; void hazNula(); E cima() throws NoSuchElementException; boolean estaVacia(); int tamano(); }

Estructuras de datos lineales

Estructuras de datos lineales

/** * Añade un elemento a la pila */ public void apila(E e) { p.addFirst(e); } /** * Elimina y retorna un elemento de la pila */ public E desapila() throws NoSuchElementException { return p.removeFirst(); }

import java.util.*; public class PilaEnlazada<E> implements Pila<E> { // la pila private LinkedList<E> p; /** * Constructor de la pila; la crea vacía */ public PilaEnlazada() { p=new LinkedList<E>(); }

Estructuras de datos lineales

Estructuras de datos lineales

/** * Indica si la pila está vacía o no */ public boolean estaVacia() { return p.isEmpty(); } /** * Retorna el número de elementos */ public int tamano(){ return p.size(); } }

/*** Deja la pila vacía */ public void hazNula(){p.clear(); }/*** Retorna el primer elemento */ public E cima()throws NoSuchElementException {return p.getFirst(); }

Estructuras de datos lineales

Ejemplo del uso de las pilas

Estructuras de datos lineales

05

Colas

Estructuras de datos lineales

Una cola es una lista especial en la que todos los elementos se insertan por un extremo de la lista y se sacan por el otro extremo (FIFO)• No confundir con la cola de prioridad Al igual que en las pilas, la implementación • implementa estas operaciones eficientemente • aprovecha las limitaciones para simplificar

Colas

Estructuras de datos lineales

Operaciones básicas de las colas

+ info

Estructuras de datos lineales

La interfaz Queue

public interface Queue<E> extends Collection<E> { E element(); boolean offer(E e); E peek(); E poll(); E remove(); }

+ info

Estructuras de datos lineales

Implementaciones de las colas

La implementación de las colas en Java es la LinkedList, que implementa la interfaz Queue• las operaciones de inserción y extracción son O(1) Puede ser conveniente hacer nuestra propia implementación para conseguir más sencillez y eficiencia

Ejemplos con colas

Estructuras de datos lineales

Escribir una clase para controlar el acceso de clientes a un servicio • Se guardará una cola de espera de clientes y otra cola de clientes ya atendidos • Cada cliente tiene un nombre, un número de móvil • Junto al cliente se guarda su fecha y hora de llegada, y su fecha y hora de atenciónOperaciones• añadir un cliente • atender a un cliente • obtener el tiempo medio de espera de los clientes que aún no han sido atendidos • obtener el tiempo medio de espera de los clientes ya atendidos • mostrar el estado de las colas Escribir también un programa de pruebaPara la fecha y hora usar la clase predefinida Calendar

Ejemplo

Estructuras de datos lineales

06

Colas de prioridad

Estructuras de datos lineales

Las colas de prioridad permiten alterar el orden de salida de los elementos de una cola• no es necesario seguir un orden FIFO • el orden se puede basar en una función de comparación Las operaciones de las colas de prioridad son las mismas que las de las colas• con un comportamiento diferente La interfaz Queue de Java se puede usar también para colas de prioridad

Colas

Estructuras de datos lineales

Implementación de colas de prioridad

En Java existe la clase PriorityQueue que • implementa la interfaz Queue • se comporta como una cola de prioridad • usa compareTo, o un comparador, para ordenar los elementos por su prioridad - los ordena de menor a mayor (sale primero el menor elemento) - para los que son iguales, el orden es arbitrario • usa para su implementación un montículo binario, consiguiendo así operaciones con eficiencia O(log n) o mejor

Estructuras de datos lineales

Constructores de PriorityQueue

PriorityQueue() - Crea la cola para ordenar sus elementos con compareTo() PriorityQueue(Collection<? extends E> c) - Crea la cola para ordenar sus elementos con compareTo(), y conteniendo inicialmente los elementos de la colección c PriorityQueue(int initialCapacity) - Crea la cola para ordenar sus elementos con compareTo(), y con la capacidad inicial indicada PriorityQueue(int initialCapacity, Comparator<? super E> comparator) - Crea la cola con la capacidad inicial indicada, y para ordenar sus elementos de acuerdo con el comparador indicado

Estructuras de datos lineales

Ejemplo con cola de prioridad

Escribir una clase para controlar el acceso de clientes a un servicio con varios grados de urgencia• Se guardará una cola de espera de clientes, ordenados por prioridad • Cada cliente tiene un nombre, un número de móvil • Junto al cliente se guarda su urgencia Operaciones • añadir un cliente • atender a un cliente • mostrar el estado de las colas Escribir también un programa de prueba

Ejemplo

Estructuras de datos lineales

07

Mapas

Estructuras de datos lineales

Un mapa es una función de unos elementos de un tipo clave, en otros elementos de un tipo destinoEs una generalización del array • el array es una tabla de valores en la que el índice es un entero • el mapa es una tabla de valores en la que el índice es de cualquier tipo (la clave)El mapa no puede tener claves repetidas • pero dos claves pueden referirse al mismo valor Las claves deben ser objetos inmutables (no cambiar)

Mapas

Estructuras de datos lineales

Operaciones básicas de los mapas

+ info

Estructuras de datos lineales

La interfaz Map

// Collection Views public Set<K> keySet(); public Collection<V> values(); public Set<Map.Entry<K,V>> entrySet(); // Interface for entrySet elements public interface Entry { K getKey(); V getValue(); V setValue(V value); } } Hay dos constructores, uno que crea un mapa vacío y otro que crea una copia de otro mapa

public interface Map<K,V> { // Basic operations V put(K key, V value); V get(Object key); V remove(Object key); boolean containsKey(Object key); boolean containsValue(Object value); int size(); boolean isEmpty(); // Bulk operations void putAll(Map<? extends K, ? extends V> m); void clear();

+ info

Estructuras de datos lineales

“Vistas” del mapa

Es posible ver el mapa desde diversos puntos de vista, para iterar sobre él• keySet(): retorna una vista del mapa como un conjunto de claves • values(): retorna una vista del mapa como una colección de valores del tipo destino (posiblemente repetidos) • entrySet(): retorna la vista del mapa como un conjunto de parejas clave-valor; son objetos de la clase interna EntryLas vistas admiten las operaciones del conjunto o colección correspondiente, excepto add()• se puede iterar • se puede borrar: la relación se borra del mapa

+ info

Estructuras de datos lineales

Implementaciones de los mapas

Las implementaciones generales de los mapas en Java son: • HashMap: mapa implementado mediante una tabla de troceado - operaciones comunes son habitualmente O(1) • TreeMap: mapa implementado mediante un árbol binario - operaciones comunes son O(log n) - los datos se ordenan por su clave • LinkedHashMap: mapa implementado mediante una tabla de troceado (tabla hash) en la que el orden de inserción se almacena además mediante una lista doblemente enlazada- operaciones comunes son habitualmente O(1) - ordenación por el orden de inserción de las claves

Ejemplos con mapas

Estructuras de datos lineales

Mapa para tipos enumerados

La clase EnumMap es una implementación especial de los mapas adaptada a claves de un tipo enumeradoTiene la misma eficiencia que un array • internamente es un array • permite manejar los enumerados con fiabilidad • mantienen la ordenación natural de las claves

Ejemplo con EnumMap

private void intercambia(int i,int j) { String car=mazo.get(i); mazo.set(i,mazo.get(j)); mazo.set(j,car); } public void barajar() { Random rnd=new Random(); for (int i=mazo.size()-1; i>=1; i--) { intercambia(i, rnd.nextInt(i+1)); } }

import java.util.*; public class Baraja { // constantes estáticas private static String[] palo= {"Bastos", "Copas", "Oros", "Espadas"}; private static String[] carta= {"As", "Dos", "Tres", "Cuatro", "Cinco", "Seis", "Siete", "Sota", "Caballo", "Rey"}; // la baraja es una lista de cartas private ArrayList<String> mazo;

/** * Repartir num cartas */ public List<String> repartir(int num) { int numCartas=mazo.size(); List<String> vistaDeMano = mazo.subList(numCartas - num, numCartas); List<String> mano = new ArrayList<String>(vistaDeMano); vistaDeMano.clear(); return mano; } }

//** * Constructor de la baraja */ public Baraja() { mazo= new ArrayList<String>(40); for (String p: palo) { for (String c: carta) { mazo.add(c+" de "+p); } } }

Notas:

Las operaciones básicas son idénticas a las de las colecciones, con la excepción de añade: • constructor: Crea el conjunto con cero elementos • añade: Si elElemento ya pertenece al conjunto retorna false. En caso contrario, añade el parámetro elElemento al conjunto y retorna true. Si elElemento es incompatible con los elementos que se almacenan en este conjunto lanza una excepción • borra: Si existe en el conjunto al menos una instancia de elElemento, la borra del conjunto y retorna true. En otro caso, retorna false • hazNulo: Elimina todos los elementos del conjunto, dejándolo vacío • pertenece: Si existe en el conjunto al menos una instancia de elElemento, retorna true. En otro caso, retorna false • estaVacio: Si el conjunto está vacío retorna true. En otro caso, retorna false • tamaño: Retorna un entero que dice cuántos elementos hay en el conjunto • iterador: Retorna un iterador asociado al conjunto, para poder recorrer sus elementos

Usar una pila para invertir el orden de una listapublic static <E> void invierte(List<E> lista) { PilaEnlazada<E> pila=new PilaEnlazada<E>(); // pasar los elementos de la lista a la pila for (E e:lista) { pila.apila(e); } lista.clear(); // pasar los elementos de la pila a la lista while (!pila.estaVacia()) { lista.add(pila.desapila()); } }

Notas:

• constructor: Crea la colección con cero elementos • añade: Añade el parámetro elElemento a la colección. Si elElemento es incompatible con los elementos que se almacenan en esta colección lanza una excepción • borra: Si existe en la colección al menos una instancia de elElemento, la borra de la colección y retorna true. En otro caso, retorna false • hazNula: Elimina todos los elementos de la colección, dejándola vacía • pertenece: Si existe en la colección al menos una instancia de elElemento, retorna true. En otro caso, retorna false • estaVacia: Si la colección está vacía retorna true. En otro caso, retorna false • tamaño: Retorna un entero que dice cuántos elementos hay en la colección • iterador: Retorna un iterador asociado a la colección, para poder recorrer sus elementos

Notas:

Las operaciones básicas que se realizan sobre una pila suelen ser las siguientes: • constructor: Crea la pila con cero elementos • apila: Añade el parámetro elElemento a la cima de la pila. Si elElemento es incompatible con los elementos que se almacenan en esta colección lanza una excepción • desapila: Elimina de la pila el elemento que está en la cima y lo retorna. Si no hay ningún elemento, lanza una excepción • hazNula: Elimina todos los elementos de la colección, dejándola vacía • iterador: retorna un iterador para recorrer los elementos de la pila. No siempre se pone un iterador, sólo si es necesario • cima: Retorna el elemento que está en la cima de la pila, sin eliminarlo. Si no hay ningún elemento, lanza una excepción • estaVacia: Si la pila está vacía retorna true. En otro caso, retorna false • tamaño: Retorna un entero que dice cuántos elementos hay en la pila

Notas:

Un 'mapa' M es una función de unos elementos de un tipo clave, en otros elementos de otro (o el mismo) tipo denominado destino. Es una generalización del concepto de array para manejar índices (claves) no necesariamente enteras. Se representa como M(clave)=valor. En ocasiones el mapa se puede indicar a través de una expresión matemática. Sin embargo en otras ocasiones es preciso almacenar para cada posible clave el valor de M(clave). En este caso se puede utilizar el tipo abstracto de datos denominado 'mapa', para el que se definen las siguientes operaciones: • constructor: Crea el mapa con cero relaciones. • asignaValor: Asigna a la clave indicada, el valor dado. • obtenValor: Retorna el valor asociado a la clave indicada, o lanza un error si para esa clave no existe valor asociado. • borra: Borra la clave indicada y su valor asociado del mapa, o lanza un error si esa clave no está en el mapa • hazNulo: Borra todas las relaciones del mapa, dejándolo vacío • contieneClave: Retorna true si el mapa contiene la clave indicada, y false en caso contrario • tamaño: Retorna el número de relaciones clave-valor válidas que existen en el mapa • estaVacio: Retorna true si el mapa no tiene relaciones, y false en caso contrario.

import java.util.*; public class Alumno implements Comparable <Alumno> { private String nombre; private String dni; /** * Troceado */ public int hashCode() { return this.dni.hashCode(); } ... }

Notas:

La lista o vector se manipula como si fuese una tabla, con todos los elementos numerados con un índice que comienza en cero Las operaciones básicas que se pueden hacer con un iterador de lista son: • obtenElemento: Retorna el elemento que ocupa el índice indicado. Lanza indiceIncorrecto si el índice se refiere a una casilla inexistente. Es O(1) en un vector, y O(n) en una lista secuencial. • cambiaElemento: Modifica el elemento que ocupa el índice indicado sustituyéndolo por nuevoElemento. Retorna el elemento que estaba anteriormente en esa casilla de la lista. Lanza indiceIncorrecto si el índice se refiere a una casilla inexistente. Es O(1) en un vector, y O(n) en una lista secuencial. • añade: Añade elElemento a la lista en la casilla índice, moviendo ese elemento y todos los siguientes una casilla hacia adelante. Lanza indiceIncorrecto si el índice se refiere a una casilla inexistente. Es O(n) tanto en vectores como el listas secuenciales • borra: Borra el elemento que ocupa la casilla índice, desplazando todos los siguientes una casilla hacia atrás. Lanza indiceIncorrecto si el índice se refiere a una casilla inexistente. Es O(n) tanto en vectores como el listas secuenciales. • busca: Retorna el índice de la casilla donde se encuentra elElemento, o -1 si no se encuentra. Es O(n) tanto en vectores como el listas secuenciales.

void atiende() { salida=Reloj.ahora(); } } // colas del servicio private Queue<DatosCliente> colaEspera; private Queue<DatosCliente> colaAtendidos; /**Constructor de ColaEspera */ public Cola Espera() { colaEspera=new LinkedList<DatosCliente>(); colaAtendidos=new LinkedList<DatosCliente>(); }

public double tiempoEsperaNoAtendidos() { long tiempo=0; int num=0; long ahora=Reloj.ahora(); for (DatosCliente datos: colaEspera) { tiempo=tiempo + ahora-datos.entrada; num++; } if (num==0) { return 0.0; } else { return (((double) tiempo)/num)/1000.0; } }

Ejemplo: cola de espera

import java.util.Calendar; /** * Clase que permite obtener la fecha y hora actual, * en milisegundos desde la época */ public class Reloj { public static long ahora() { return Calendar.getInstance().getTimeInMillis(); } }

/** * Nuevo cliente; se mete en la cola de espera */ public void nuevoCliente(Cliente c) { DatosCliente datos=new DatosCliente(c); colaEspera.add(datos); }

public double tiempoEsperaAtendidos() { long tiempo=0; int num=0; for (DatosCliente datos: colaAtendidos) { tiempo=tiempo+datos.salida-datos.entrada; num++; } if (num==0) { return 0.0; } else { return (((double) tiempo)/num)/1000.0; } }}

import java.util.*; public class ColaEspera { /** Clase interna para almacenar todos los * datos de un cliente */ private static class DatosCliente { Cliente c; long entrada, salida; // milisegundos /** Constructor; pone la hora de entrada*/ DatosCliente (Cliente c) { this.c=c; entrada=Reloj.ahora(); }

/** * Atender cliente: se saca de la cola de * espera y se mete en la de atendidos; * retorna el cliente atendido */ public Cliente atenderCliente() throws NoSuchElementException { DatosCliente datos=colaEspera.remove(); datos.atiende(); colaAtendidos.add(datos); return datos.c; }

Notas:

La relación entre los métodos de la interfaz ListIterator y las operaciones del ADT IteradorDeLista son: Además, hay algunas operaciones en la interfaz Java que no estaban en el ADT: • nextIndex: retorna el índice de la casilla próxima al cursor, o -1 si no existe • previousIndex: retorna el índice de la casilla previa al cursor, o -1 si no existe

Escribir una clase que relacione cada dia de la semana con un objeto de la clase Menu, que representa el menú de la comida• El dia de la semana es un objeto de una clase enumerada

public enum DiaSemana { lunes, martes, miercoles, jueves, viernes, sabado, domingo } public class Menu { // atributos private String primerPlato; private String segundoPlato; private String postre;

import java.util.*; public class MenuSemanal { // mapa de menús private EnumMap<DiaSemana,Menu> menu; /** * Constructor */ public MenuSemanal() { menu=new EnumMap<DiaSemana,Menu> (DiaSemana.class); }

/** poner el menú de un día concreto */ public void ponMenu(DiaSemana dia, Menu comida) { menu.put(dia,comida); } /** * Consultar el menú de un día */ public Menu consultaMenu(DiaSemana dia) { return menu.get(dia); } }

public Menu(String primerPlato, String segundoPlato, String postre) { this.primerPlato=primerPlato; this.segundoPlato=segundoPlato; this.postre=postre; } public String toString() { return "1º: "+primerPlato+", 2º: "+ segundoPlato+", postre: "+postre; } }

Notas:

La interfaz Queue, junto a la operación add() heredada de la colección, dispone de operaciones para encolar, desencolar, o consultar el primer elemento de la cola (el próximo que se va a desencolar). De cada una de ellas dispone de dos versiones, una que lanza una excepción si hay un fallo, y otra que retorna un valor especial si la acción solicitada no puede realizarse. • offer(): retorna true si ha conseguido encolar el elemento y false si no (por ejemplo, si la cola es limitada, y el elemento no cabe) • poll(): desencola y retorna un elemento si existe; si no existe, retorna null • peek(): retorna sin desencolarlo el primer elemento si existe (el que se desencolaría con peek); si no existe, retorna null • add(): intenta encolar el elemento e, y en caso de que no pueda (por ejemplo, si la cola es limitada, y el elemento no cabe) lanza IllegalStateException • remove(): desencola y retorna un elemento si existe; si no existe, lanza NoSuchElementException • element(): retorna sin desencolarlo el primer elemento si existe (el que se desencolaría con peek); si no existe, lanza NoSuchElementException Las colas Java no deben usarse para almacenar elementos que sean null, ya que entonces los métodos poll() y peek() no funcionarían bien.

En el libro de visitas del apartado anterior, añadir un método para mostrar todos los elementos duplicados (aquellos con más de una visita)Hacer un método para obtener un conjunto con todas las visitas, pero sin duplicidades

// construimos noRepetidos y duplicados for(String nombre: bolsa) { boolean esNuevo=noRepetidos.add(nombre); if (! esNuevo) { duplicados.add(nombre); } } // mostramos la lista de duplicados for (String nombre:duplicados) { System.out.println(nombre); } }

/*** Mostrar una lista de las personas* duplicadas, una sola vez cada persona */ public void muestraDuplicadosUnaVez(){// conjunto de visitas sin repeticiones// capacidad igual al tamaño de la bolsa/0.75 HashSet<String> noRepetidos= new HashSet<String>(bolsa.size()*100/75); // conjunto de visitas repetidas // capacidad inicial sin especificar HashSet<String> duplicados= new HashSet<String>();

/** * Retorna un conjunto sin duplicados */ public Set<String> sinDuplicados() { return new HashSet<String>(bolsa); }

Notas:

Las operaciones básicas de las listas son: • constructor: Crea la lista vacía • hazNula: Elimina todos los elementos de la lista, dejándolo vacía • estaVacia: Si la lista está vacía retorna true. En otro caso, retorna false • tamaño: Retorna un entero que dice cuántos elementos hay en la lista • iteradorDeLista: Retorna un iterador de lista asociado a la lista, para poder recorrer sus elementos

Notas:

La interfaz Map define las operaciones que pueden realizarse con los mapas en Java. La relación entre las operaciones abstractas de los mapas y los métodos de la interfaz Map se indica en la siguiente tabla

Notas:

La relación entre los métodos de la interfaz Collection y las operaciones del ADT Colección son: El método add debe retornar true, o lanzar una excepción si no se inserta el elemento

Notas:

La relación entre los métodos de la clase LinkedList y las operaciones del ADT Pila son:

Notas:

• intersección: Retorna un conjunto que contiene los elementos comunes al conjunto actual y a otroConjunto. • unión: Retorna un conjunto que contiene los elementos del conjunto actual y los de otroConjunto. • diferencia: Retorna un conjunto que contiene los elementos del conjunto actual que no pertenecen a otroConjunto. • incluidoEn: Retorna true si todos los elementos del conjunto original pertenecen a otroConjunto, y false en caso contrario.

Notas:

Además, el mapa tiene las siguientes operaciones adicionales: • containsValue(): Retorna true si el mapa contiene el valor indicado, al menos una vez, y false en caso contrario • putAll(): Añade al mapa todas las relaciones del mapa m. el efecto es como invocar put() para cada pareja clave valor del mapa m. • ketSet(): retorna una vista del mapa como un conjunto de claves • values(): retorna una vista del mapa como una colección de valores, posiblemente repetidos • entrySet(): retorna una vista del mapa como un conjunto de parejas clave-valor, de la clase interna Entry. El método entrySet() retorna un objeto de la interfaz interna Entry, que representa una pareja clavevalor. Dispone de los siguientes métodos • getKey(): retorna la clave • getValue(): retorna el valor • setValue(): cambia el valor haciéndolo igual a value, y retorna el valor anterior. El cambio se refleja en el mapa original.Mientras se usa una vista el mapa no debe cambiar, excepto a través de esa vista.

1. Crear una agenda que relacione nombres de personas con su número de teléfono• probar las diferentes vistas del mapa para iterar sobre él de varias formas 2. Implementar un diccionario

public int consulta (String nombre) { Integer tel= agenda.get(nombre); if (tel==null) { return 0; } else { return tel.intValue(); } } /** * Saber si un nombre esta en el diccionario */ public boolean estaIncluido(String nombre) { return agenda.containsKey(nombre); }

/** * Añadir un nombre con su teléfono */ public void anadeTelefono (String nombre, int telefono) { agenda.put(nombre, new Integer(telefono)); } /** * Consultar un nombre; retorna el telefono, * o 0 si el nombre no existe */

import java.util.*; public class AgendaTelefonica { // la agenda se guarda en un mapa private Map<String,Integer> agenda; /** * Constructor que deja la agenda vacía */ public AgendaTelefonica() { agenda = new HashMap<String,Integer>(); }

Mostrar lista

Ejemplo: libro de visitas

public void anadeVisita(String nombre) { bolsa.add(nombre); } public int numeroVisitas(String nombre) { int contador=0; for(String n: bolsa) { if (n.equals(nombre)) { contador++; } } return contador; } }

import java.util.*; public class LibroVisitas { // lista de visitas private Collection<String> bolsa; /** * Constructor que deja el libro vacío */ public LibroVisitas() { bolsa=new LinkedList<String>(); }

/** * Nuevo cliente; se mete en la cola de espera */ public void nuevoCliente (Cliente c, Urgencia urg) { DatosCliente datos=new DatosCliente(c,urg); colaEspera.add(datos); } /** * Atender cliente: se saca de la cola de * espera; retorna el cliente atendido */

/** * Constructor de DatosCliente */ DatosCliente (Cliente c, Urgencia urg) { this.c=c; this.urg=urg; } /* * Comparación de clientes por su urgencia */ public int compareTo(DatosCliente otro) { return this.urg.compareTo(otro.urg); } } // final de la clase DatosCliente

/** * Clase enumerada que representa la * urgencia de un cliente */ public enum Urgencia { baja, media, alta }

import java.util.*; /public class ColaEsperaConUrgencia { /** * Clase interna para almacenar los datos * de un cliente con urgencia */ private static class DatosCliente implements Comparable <DatosCliente> { Cliente c; Urgencia urg;

// cola del servicio private Queue<DatosCliente> colaEspera; /** * Constructor de ColaEspera */ public ColaEsperaConUrgencia() { colaEspera=new PriorityQueue<DatosCliente>(); }

Atender cliente

Cliente en espera

Notas:

La relación entre los métodos de la interfaz List (incluyendo los heredados de Collection) y las operaciones del ADT Lista son: La interfaz List contiene otros métodos adicionales a los del ADT listas: • add(E): Añade el elemento indicado al final de la lista. • addAll: Añade todos los elementos de la colección que se pasa como parámetro a partir de la casilla index, moviendo ese elemento y los posteriores hacia adelante un número de casillas igual al de elementos insertados • lastIndexOf: Igual que indexOf(), pero buscando desde el final de la lista. • listIterator(index): retorna un iterador de lista, pero con el cursor situado justo antes de la casilla index. • subList: retorna una vista parcial de la lista, entre los índices indicados, desde fromIndex inclusive hasta toIndex excluido. No es una nueva lista. La lista original no debe cambiar mientras se usa esta sublista (a no ser que el cambio se haga a través de la sublista.

Ejemplos:

String[] a= v.toArray(new String[v.size()]); String[] a= v.toArray(new String[0]);

public static <E> void reemplazaGenerico (List<E> list, E valor, E nuevoValor) { ListIterator<E> it = list.listIterator(); while (it.hasNext()) { E elem=it.next(); if (valor == null ? elem==null : valor.equals(elem)) { it.set(nuevoValor); } } }

Notas:

Las operaciones básicas que se realizan sobre una cola suelen ser las siguientes: • constructor: Crea la pila con cero elementos • encola: Añade el parámetro elElemento al extremo de inserción de la cola. Si elElemento es incompatible con los elementos que se almacenan en esta colección lanza una excepción • desencola: Elimina de la cola el elemento que está en el extremo de extracción y lo retorna. Si no hay ningún elemento, lanza una excepción • hazNula: Elimina todos los elementos de la cola, dejándola vacía • estaVacia: Si la cola está vacía retorna true. En otro caso, retorna false • tamaño: Retorna un entero que dice cuántos elementos hay en la cola

Notas:

Inicialmente el iterador de lista tiene el cursor situado antes del primer elemento Las operaciones básicas que se pueden hacer con un iterador de lista son: • añade: Añade elElemento a la lista entre los elementos previo y próximo, si existen; si no existen, lo añade como el único elemento de la lista. El cursor queda situado justo después del nuevo elemento. • borra: borra el último elemento obtenido de la lista con previo() o proximo(). Si no hay tal elemento, lanza estadoIncorrecto. • cambiaElemento: modifica el último elemento obtenido de la lista con previo() o proximo() sustituyéndolo por el nuevoElemento. Si no hay tal elemento, o si se ha llamado a borra() o añade() después de previo() o proximo(), lanza estadoIncorrecto. • hayPrevio: Retorna true si existe un elemento previo al cursor y false en caso contrario. • hayProximo: Retorna true si existe un elemento proximo al cursor y false en caso contrario. • previo: Retorna el elemento previo al cursor, y hace que éste retroceda un elemento en la lista. Si no existe elemento previo, lanza noExiste. • proximo: Retorna el elemento próximo al cursor, y hace que éste avance un elemento en la lista. Si no existe elemento próximo, lanza noExiste. Observar que si se llama a previo() después de llamar a proximo() se obtiene el mismo elemento.