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.
desencolar
3
2
5
3
1
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 Cola
import java.io.*;
Define los métodos de
objeto utilizados en la
clase TadCola
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 ();
}
Condiciones normales y excepcionales de la cola
public class PruebaCola1 {
public static void main (String [ ] args)
throws ColaVacia {
Cola cola1 = new TadCola ();
int elem;
public class PruebaCola2 {
public static void main (String [ ] args)
throws ColaVacia {
Cola cola1 = new TadCola ();
int i, j;
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 ();
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 invertida
 Para usar este esquema, se debe invertir previa o
posteriormente los elementos de la cola (fuera del módulo
recursivo)
 Desencolar – Encolar – llamada recursiva
 No se alcanza la condición de finalización Estructura Vacía
 Si se conoce el número de elementos
 Variable auxiliar que determina la condición de parada
 Permite Tratamiento recursivo y iterativo
Invertir una cola
 Mé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);
3
2
5
4
2
5
4
elem = 2
elem = 3
5
4
elem = 5
4
elem = 4
cola.encolar (elem);
}
4
5
2
3
4
5
2
4
5
4
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;
}
La solución recursiva es
la única posibilidad:
método (estático)
contarCola
static int cuentaCola(Cola cola) throws ColaVacia {
cola.invertirCola ();
return contarCola (cola);
}
Necesidad de invertir la
cola fuera del módulo
recursivo: método
(estático) cuentaCola.
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 ();
}
}
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);
colaO
3
2
5
3
2
5
3
2
3
5
3
3
2
3
colaD
3
elem = 2
elem = 3
5
elem = 5
3 2 5 3
elem = 3
colaO.encolar (elem);
}
3
5
2
3
3
5
2
3
5
3
Conociendo el número de elementos. Solución Recursiva
static void copiaR2 (Cola colaO, Cola colaD, int n) throws ColaVacia {
int elem;
if (n > 0) {
elem = colaO.desencolar ();
colaD.encolar (elem);
colaO.encolar (elem);
copiar2 (colaO, colaD, n-1);
}
}
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:");
cO.imprimirCola ();
System.out.println ("Cola destino:");
cD.imprimirCola ();
}
colaO
if (n > 0) {
elem = colaO.desencolar ();
colaD.encolar (elem);
colaO.encolar (elem);
CopiaR2 (colaO, colaD, n-1);
}
3 2 5 4
2 5 4 3
5 4 3 2
4 3 2 5
2 5 4 3
5 4 3 2
4 3 2 5
3 2 5 4
3 2 5
3 2 5 4
colaD
3
3 2
n=4
n =3
n =2
n=1
elem = 3
elem = 2
elem = 5
elem = 4
Conociendo el número de elementos. Solución iterativa
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);
colaO.encolar (elem);
}
}
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:");
cO.imprimirCola ();
System.out.println ("Cola destino:");
cD.imprimirCola ();
}
Insertar un elemento al principio de la cola
static 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 ();
cola.encolar (elem);
}
}
Terminación anticipada
 Precauciones:
 Devolver la cola en su estado original
 Si hay terminación anticipada


Todos los elementos deben sufrir el proceso de encolardesencolar
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;
 Se pasa al módulo
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;
recursivo la cola invertida
 En el módulo recursivo:
 Desencolar-encolar
invierte los elementos
procesados
 Resto de elementos
requieren inversión
}
static boolean estaR1 (Cola cola, int dato) throws ColaVacia {
cola.invertirCola ();
return esta (cola,dato);
}
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)) {
elem = cola.desencolar ();
cola.encolar (elem);
if (elem == dato)
resul = true;
n = n-1;
}
for (i = 1; i <= n; i++)
{
elem = cola.desencolar ();
cola.encolar (elem);
}
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;
static int quitarUltimoR1 (Cola cola) throws ColaVacia {
}
int resul;
return dato;
resul = quitarUlt (cola);
}
cola.invertirCola ();
return resul;
}
Ejercicio propuesto: obtener el elemento
final de la cola conociendo el número de
elementos
Combinar dos colas. General.
 Dos colas ordenadas (c1 y c2) -> c3 ordenada
 Se plantean dos posibilidades:
 Sin conocer el número de elementos
 Conociendo 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.
Combinar dos colas conociendo el número de
elementos. Técnica recursiva.
 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. Mezcla AND.
 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 OR.
 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 pendiente
 Uso de un procedimiento auxiliar que:


Reordena la cola no finalizada.
Encola en c3.
 Fase de vuelta:
 Sin tratamiento.
MÓDULO NO RECURSIVO
mezclaOR_R2 (c1, c2, c3, elem1, elem2, n1-1, n2-1)
n1 = 2, n1 = 2,
n1 = c1.numElemCola ();
Si ((n1 >= 0) && (n2 >= 0))
n2 = c2.numElemCola ();
Comparo elementos
n1=3
Si quedan por tratar en
Si elem2 < elem1
ambas ( (n1 >= 0) && (n2 >= 0))
n2=3
cola3.encolar( elem2)
se obtienen los valores de
elem1 y elem2:
c3.inicializarCola();
2 4 6
elem1 = cola1.desencolar ();
cola1.encolar (elem1);
1 3 5
elem2 = cola2.desencolar ();
cola2.encolar (elem2);
4 6 2
1
elem1 = 2
Se obtiene un nuevo valor para elem2
if (n2>0) {
cola2.desencolar (elem2);
cola2.encolar (elem2);
}
elem2 =1
4 6 2
3 5 1
elem1 = 2
elem2 = 3
5 1 3
Se llama al módulo recursivo con n1-1 y n2-1:
mezclaOR_R2 (cola1, cola2, cola3, elem1, elem2, n1-1, n2-1);
Nueva llamada recursiva con n2-1
mezclarOR_R2 (c1, c2, c3, elem1, elem2, n1, n2-1)
n1 = 2; n2 = 1
mezclaOR_R2 (cola1, cola2, cola3, elem1, elem2, n1, n2-1)
n1=1;n2=1
n1=2;n2=1
Si ((n1 >= 0) && (n2 >= 0))
Comparo elementos
if (elem1 < elem2)
cola3.encolar (elem1);
1 2
Si ((n1 >= 0) && (n2 >= 0))
comparo elementos
if (elem2 < elem1)
cola3.encolar (elem2);
1 2 3
Se obtiene un nuevo valor para elem1
if (n1>0) {
elem1 = cola1.desencolar ();
cola1.encolar (elem1);
}
6 2 4
mezclaOR_R2 (cola1, cola2, cola3, elem1, elem2, n1-1, n2)
Se obtiene un nuevo valor para elem2
if (n2>0) {
elem2 = cola2.desencolar ();
cola2.encolar (elem2);
}
6 2 4
elem1 = 4
elem2 = 3
5 1 3
Nueva llamada recursiva con n1-1
elem1 = 4
elem2 = 5
1 3 5
Nueva llamada recursiva con n2-1
mezclaOR_R2 (cola1,cola2,cola3,elem1,elem2,n1,n2-1) mezclaOR_R2 (cola1,cola2,cola3,elem1,elem2,n1-1,n2)
n1=1;n2=0
n1=0;n2=0
Si ((n1 >= 0) && (n2 >= 0))
Comparo elementos
if (elem1 < elem2)
cola3.encolar (elem1)
1 2 3 4
Si ((n1 >= 0) && (n2 >= 0))
Comparo elementos
if (elem2 < elem1)
cola3.encolar (elem2)
1 2 3 4 5
Se obtiene un nuevo valor para elem1
if (n1>0) {
elem1 = cola1.desencolar ();
cola1.encolar ();
}
n2 = 0
→ No se puede realizar el proceso de
desencolar/encolar sobre cola2
Nueva llamada recursiva con n2-1
2 4 6
elem1 = 6
elem2 = 5
1 3 5
Nueva llamada recursiva con n1-1
mezclaOR_R2 (cola1, cola2, cola3, elem1, elem2, n1-1, n2)
n1 = 0; n2 = -1
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
Combinar dos colas con terminación anticipada.
Mezcla AND conociendo el número de elementos. Técnica
recursiva.
 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.
Descargar

Estructuras de Datos. TAD's.