Tema 2 Tipos abstractos de datos. 2.3 Cola de números enteros

Tema 2 Tipos abstractos de datos.

2.3 Cola de números enteros.

Especificación de TAD’s. TAD Cola de Enteros.

Definición del TAD Cola de Enteros:Estructura de Datos que contiene una serie de elementos

de tipo entero en la que dichos elementos son insertados por un lado y son extraídos por el lado contrario. Característica: Primer elemento obtenido es el primero

introducido Estructura FIFO (First Input, First Output)

Operaciones: encolar. desencolar. colaVacia.

3 2 5 3 1desencolar

encolar

Especificación de TAD’s. TAD Cola de Enteros (I).Especificación Semántica Especificación Sintáctica

encolar Método que entrega un elemento (x) para que quede incorporado al final de la cola.

void encolar (int x)

desencolar * Método que elimina el elemento de la cola que ocupa el primer lugar, devolviéndolo como resultado.

int desencolar () throws ColaVacia

colaVacia Método que al ejecutarse devuelve true si la cola está vacía, y false en caso contrario.

boolean colaVacia ()

leerCola Método mediante el que se produce la carga inicial de elementos de la cola.

void leerCola () throws NumberFormatException, IOException

* Se lanza una excepción (CoaVacia) si se intenta utilizar alguna de estas operaciones cuando la cola está vacía

Especificación de TAD’s. TAD Cola de Enteros (II).Especificación Semántica Especificación Sintáctica

imprimirCola Método que muestra en el dispositivo de salida (pantalla) el contenido actual de la cola.

void imprimirCola ()

invertirCola * Método que devuelve la cola con sus elementos invertidos

void invertirCola () throws ColaVacia

numElemCola Método que devuelve el número de elementos de la cola.

int numElemCola ()

primero * Método que devuelve el primer elemento de la cola sin desencolarlo.

int primero () throws ColaVacia

quitarPrimero * Método que elimina el primer elemento de la cola.

void quitarPrimero () throws ColaVacia

eliminarCola Método que recibe una cola (que puede tener elementos o no) y la devuelve vacía.

void eliminarCola ()

Excepciones.

Excepción: circunstancia que produce que una Operación Válida sobre un TAD no pueda ser efectuada.

Ejemplos:encolar:

Al intentar encolar un nuevo elemento en la cola, ésta está llena: la operación encolar no debe producir ningún efecto. No se contempla tratamiento alguno.

desencolar, primero, quitarPrimero, invertirCola: Al intentar realizar una de estas operaciones, la cola

está vacía: se producirá un mensaje de error.

Interfaz del TAD Colaimport java.io.*;

public interface Cola {void inicializarCola ();void encolar (int x);int desencolar () throws ColaVacia ;boolean colaVacia ();void leerCola () throws NumberFormatException, IOException;void imprimirCola ();void invertirCola () throws ColaVacia ;int numElemCola ();int primero () throws ColaVacia ;void quitarPrimero () throws ColaVacia ;void eliminarCola ();

}

Define los métodos de objeto utilizados en la clase TadCola

Condiciones normales y excepcionales de la cola

public class PruebaCola1 {public static void main (String [ ] args) throws ColaVacia {

Cola cola1 = new TadCola (); int elem;

cola1.inicializarCola ();cola1.encolar (8);cola1.encolar (7);cola1.encolar (9);cola1.encolar (11);elem = cola1.desencolar ();elem = cola1.desencolar ();System.out.println (“Sale el

número"+elem);cola1.eliminarCola ();

}}

public class PruebaCola2 {public static void main (String [ ] args) throws ColaVacia {

Cola cola1 = new TadCola (); int i, j;

cola1.inicializarCola ();for (i = 1; i< 10; i++)

cola1.encolar (i); j = cola1.desencolar ();System.out.println ("Hemos sacado "+j);for (i = 1; i< 10; i++) {

j = cola1.desencolar (); System.out.println (“Sacamos "+j);

}cola1.eliminarCola ();

}}

Estrategias con Colas

Desencolar – llamada recursiva – Encolar Devuelve la cola invertidaPara usar este esquema, se debe invertir previa o

posteriormente los elementos de la cola (fuera del módulo recursivo)

Desencolar – Encolar – llamada recursivaNo se alcanza la condición de finalización Estructura

Vacía

Si se conoce el número de elementosVariable auxiliar que determina la condición de

paradaPermite Tratamiento recursivo y iterativo

Invertir una colaMétodo (estático) auxiliar en el tratamiento recursivo

de colas.

static void invertir (Cola cola) throws ColaVacia {int elem;

if (!cola.colaVacia ()) {elem = cola.desencolar ();invertir (cola);cola.encolar (elem);

}}

if (!cola.colaVacia () {elem = cola.desencolar ();

invertir (cola);

elem = 2elem = 3 elem = 5 elem = 4

cola.encolar (elem);

}

3 2 5 4 42 5

44 5

45 4

4 5 24 5 2 3

Contar los elementos de una cola

public class PruebaContar {

static int contarCola (Cola cola) throws ColaVacia {int elem, resul;if (!cola.colaVacia ()) {

elem = cola.desencolar (); resul = 1 + contarCola (cola); cola.encolar (elem);

}else resul = 0;return resul;

}

static int cuentaCola(Cola cola) throws ColaVacia {cola.invertirCola ();return contarCola (cola);

}

public static void main(String [ ] args)throws ColaVacia {

Cola c = new TadCola ();c.leerCola ();System.out.println ("La cola tiene “+cuentaCola (c)+"

elementos");c.imprimirCola ();

}}

La solución recursiva es la única posibilidad: método (estático) contarCola

Necesidad de invertir la cola fuera del módulo recursivo: método (estático) cuentaCola.

Obtener una cola a partir de otra

Estrategias para trabajar con colas:¿No se conoce el número de elementos?

Solución recursiva (requiere inversión de la cola)¿Se conoce el número de elementos?

Solución recursiva Solución iterativa

Sin conocer el número de elementos. Solución Recursiva

static void copiar (Cola colaO, Cola colaD) throws ColaVacia {int elem;

if (!colaO.colaVacia ()) {elem = colaO.desencolar ();colaD.encolar (elem);copiar (colaO, colaD);colaO.encolar (elem);

}}

static void copia (Cola colaO, Cola colaD) throws ColaVacia {

copiar (colaO, colaD); colaO.invertirCola ();}

public static void main (String [ ] args) throws ColaVacia { Cola cO = new TadCola (); Cola cD = new TadCola ();

cO.leerCola (); copia (cO, cD);System.out.println ("Cola origen:");

cO.imprimirCola (); System.out.println ("Cola destino:"); cD.imprimirCola ();}

if (! colaO.colaVacia ()) {elem = colaO.desencolar ();colaD.encolar (elem);copiar (colaO, colaD);

elem = 3

colaO.encolar (elem);

}

33 5

3

3 5 23 5 2 3

elem = 2

32 5

3 2

elem = 5

35

23 5 23 5 3

elem = 3

3 2 5 3

3

colaO

colaD

static void copiaR2 (Cola colaO, Cola colaD, int n) throws ColaVacia {

int elem;

if (n > 0) {

elem = colaO.desencolar ();

colaD.encolar (elem);


copiar2 (colaO, colaD, n-1);

}

}

Conociendo el número de elementos. Solución Recursiva

public static void main (String [ ] args) throws ColaVacia { Cola cO = new TadCola (); Cola cD = new TadCola (); cO.leerCola ();

copiaR2 (cO, cD, cO.numElemCola ());System.out.println ("Cola origen:");


if (n > 0) {elem = colaO.desencolar ();colaD.encolar (elem);colaO.encolar (elem);CopiaR2 (colaO, colaD, n-1);

}

n =3

elem = 2

n = 4

elem = 3

n =2

elem = 5

n = 1

elem = 4

3 2 5 4

3

colaO

colaD

32 5 4

3

32 5 4

3 25 4

2

3 25 4

3 2 54

3 2 5

2 5 43

3 2 5

3 2 54

4

static void copiaIt (Cola colaO, Cola colaD) throws ColaVacia {

int elem, i, n;

n = colaO.numElemCola ();

for (i = 1; i <= n; i++) {

elem = colaO.desencolar ();

colaD.encolar (elem);


}

}

Conociendo el número de elementos. Solución iterativa

public static void main (String [ ] args) throws ColaVacia { Cola cO = new TadCola (); Cola cD = new TadCola (); cO.leerCola ();

copiaIt (cO, cD);System.out.println ("Cola origen:");


Insertar un elemento al principio de la colastatic void InsertarPI (Cola cola, int dato) throws ColaVacia {

int elem, i, n;

n = cola.numElemCola ();

cola.encolar (dato);

for (i = 1; i <= n; i++) {

elem = cola.desencolar ();


}

}

Terminación anticipada

Precauciones: Devolver la cola en su estado originalSi hay terminación anticipada

Todos los elementos deben sufrir el proceso de encolar-desencolar

Si no fuese así, el resultado sería una cola con una parte ordenada y otra invertida

Buscar un elemento (sin conocer n)static boolean esta (Cola cola, int dato) throws ColaVacia {

int elem; boolean resul;

if (!cola.colaVacia ()) {elem = cola.desencolar ();if (elem == dato) {

resul = true;cola.invertirCola ();

}else resul = esta (cola, dato);

cola.encolar (elem);}

else resul = false;return resul;

}

static boolean estaR1 (Cola cola, int dato) throws ColaVacia {cola.invertirCola ();return esta (cola,dato);

}

Se pasa al módulo recursivo la cola invertida

En el módulo recursivo:Desencolar-encolar

invierte los elementos procesados

Resto de elementos requieren inversión

Buscar un elemento (n conocido, recursivo)static boolean recorrer (Cola cola, int n) throws ColaVacia {

boolean resul;int elem;if (n > 0) {

elem = cola.desencolar ();cola.encolar (elem);resul = recorrer (cola, n-1);

}else resul = true;

return resul;}

static boolean estaR2 (Cola cola, int n, int dato) throws ColaVacia {int elem;boolean resul;

if (n > 0) {elem = cola.desencolar ();cola.encolar(elem);if (elem == dato)

resul = recorrer (cola, n-1); else resul = estaR2 (cola, n-1, dato);

}else resul = false;

return resul;}

Buscar un elemento (n conocido, iterativo)static boolean estaIt (Cola cola, int dato) throws ColaVacia {

int n,elem,i;

boolean resul;

resul = false;

n = cola.numElemCola();

while ((n > 0) && (!resul)) {



if (elem == dato)

resul = true;

n = n-1;

}

for (i = 1; i <= n; i++)

{



}

return resul;

}

Obtener elemento final de una cola

static int quitarUlt (Cola cola) throws ColaVacia {int elem,dato = -9999;if (!cola.colaVacia ()) {

elem = cola.desencolar ();if (!cola.colaVacia ()) {

dato = quitarUlt (cola); cola.encolar (elem);

}else dato = elem;

}return dato;

}

Ejercicio propuesto: obtener el elemento final de la cola conociendo el número de elementos

static int quitarUltimoR1 (Cola cola) throws ColaVacia {int resul;resul = quitarUlt (cola);cola.invertirCola ();return resul;

}

Combinar dos colas. General.

Dos colas ordenadas (c1 y c2) -> c3 ordenadaSe plantean dos posibilidades:

Sin conocer el número de elementosConociendo el número de elementos

Solución recursiva. Solución iterativa.

Combinar dos colas sin conocer el número de elementos.

El mismo algoritmo que se utiliza con las pilas devolvería las colas invertidas o desordenadas: Las tres colas se invierten en el módulo de llamada.

static void llamadaMezclar** (Cola c1, Cola c2, Cola c3) throws ColaVacia {mezclar** (c1, c2, c3, false, false, 0, 0);c1.invertirCola ();c2.invertirCola ();c3.invertirCola ();

}

En el caso de la mezcla AND, cuando se produce terminación anticipada hay que invertir lo que quede de la cola con elementos mayores.

Técnica empleada:Método inicial (si procede) no recursivo.

Prepara los dos elementos primeros de cada cola (desencolar-encolar).

Prototipo: mezcla** (cola1, cola2, cola3, elem1, elem2, n1-1, n2-1);

Método recursivo: Condición de terminación: !((n1 >= 0) && (n2 >= 0)) Tratamiento específico:

Fase de transición. Terminación anticipada.

Combinar dos colas conociendo el número de elementos. Técnica recursiva.

Fase de ida: Comparar elem1 y elem2.Si elem1 = elem2, encolar en c3. [Si se puede] desencolar –encolar

elem1|2 de c1|c2 según el caso.Llamada recursiva con n1-1|n2-1

según el caso. Fase de transición:

Uso de un procedimiento auxiliar que reordena la cola no finalizada.

Fase de vuelta:Sin tratamiento.

Combinar dos colas conociendo el número de elementos. Técnica recursiva. Mezcla AND.

Fase de ida: Comparar elem1 y elem2.Encolar en c3 elem1|2 .[Si se puede] desencolar –encolar elem1|2

de c1|c2 según el caso.Llamada recursiva con n1-1|n2-1 según el

caso. Fase de transición:

Encolar en c3 el elemento en pendienteUso de un procedimiento auxiliar que:

Reordena la cola no finalizada.Encola en c3.

Fase de vuelta:Sin tratamiento.

Combinar dos colas conociendo el número de elementos. Técnica recursiva. Mezcla OR.

2 4 6

1 3 5

Si quedan por tratar en ambas ( (n1 >= 0) && (n2 >= 0)) se obtienen los valores de elem1 y elem2:

elem1 = cola1.desencolar ();

cola1.encolar (elem1);

elem2 = cola2.desencolar ();

cola2.encolar (elem2);

Se llama al módulo recursivo con n1-1 y n2-1:mezclaOR_R2 (cola1, cola2, cola3, elem1, elem2, n1-1, n2-1);

24 6

13 5

elem1 = 2

elem2 =1

Si ((n1 >= 0) && (n2 >= 0))Comparo elementos Si elem2 < elem1 cola3.encolar( elem2)

24 6

1 35

1

elem1 = 2

elem2 = 3

Nueva llamada recursiva con n2-1mezclarOR_R2 (c1, c2, c3, elem1, elem2, n1, n2-1) n1 = 2; n2 = 1

mezclaOR_R2 (c1, c2, c3, elem1, elem2, n1-1, n2-1) n1 = 2, n1 = 2,

Se obtiene un nuevo valor para elem2if (n2>0) {

cola2.desencolar (elem2);cola2.encolar (elem2);

}

MÓDULO NO RECURSIVO

c3.inicializarCola();

n1 = c1.numElemCola ();

n2 = c2.numElemCola ();

n1=3n2=3

2 46

15

1

elem1 = 4

elem2 = 3

mezclaOR_R2 (cola1, cola2, cola3, elem1, elem2, n1, n2-1) n1=2;n2=1

2

3

2

5

6

1

4

1

elem1 = 4

elem2 = 5

Nueva llamada recursiva con n2-1

mezclaOR_R2 (cola1, cola2, cola3, elem1, elem2, n1-1, n2) n1=1;n2=1

2

3

3

Si ((n1 >= 0) && (n2 >= 0))Comparo elementos

if (elem1 < elem2) cola3.encolar (elem1);


elem1 = cola1.desencolar ();cola1.encolar (elem1);

}


Si ((n1 >= 0) && (n2 >= 0))comparo elementos

if (elem2 < elem1) cola3.encolar (elem2);


elem2 = cola2.desencolar ();cola2.encolar (elem2);

}

2 6

51

4

1

elem1 = 6

elem2 = 5


2

3

3 4 1


2

n2 = 0 → No se puede realizar el proceso de desencolar/encolar sobre cola2

3 4 5

mezclaOR_R2 (cola1,cola2,cola3,elem1,elem2,n1,n2-1) n1=1;n2=0


if (elem1 < elem2) cola3.encolar (elem1)


elem1 = cola1.desencolar ();cola1.encolar ();

}

mezclaOR_R2 (cola1,cola2,cola3,elem1,elem2,n1-1,n2) n1=0;n2=0


if (elem2 < elem1) cola3.encolar (elem2)

FASE DE TRANSICIÓN→ Se encola el elemento pendiente (si queda alguno) en cola3→ Se llama a un procedimiento auxiliar que copia una cola en otra y restaura la pendiente

if (n1 > 0) {

elem = cola1.desencolar ();cola1.encolar (elem);

cola3.encolar (elem);copiarcola (cola1, cola3, n-1);

}

1 2 3 4 5 6

mezclaOR_R2 (cola1, cola2, cola3, elem1, elem2, n1-1, n2) n1 = 0; n2 = -1

Módulo inicial (no recursivo).Contempla situaciones de excepción.Invoca (si procede) al módulo recursivo. (Igual que en la

mezcla AND). Módulo recursivo:

Terminación pesimista: !((n1 >= 0) && (n2 >= 0)).

Análisis de casos posibles. Reordenar la cola pendiente (si hay alguna).

Terminación anticipada: Si elem1 > elem2. Devuelve false. Reordenar ambas colas mediante el método auxiliar.

Resto. Similar a la mezcla AND.

Combinar dos colas con terminación anticipada.Mezcla AND conociendo el número de elementos. Técnica recursiva.

Documents

Tema 2 Tipos abstractos de datos. 2.3 Cola de números enteros