Tema 2 Tipos abstractos de datos.
2.3 Cola de nmeros enteros.
Especificacin de TADs. TAD Cola de Enteros.
Definicin 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 extrados por el lado contrario.
Caracterstica: Primer elemento obtenido es el primero introducido
Estructura FIFO (First Input, First Output)
Operaciones:
encolar.
desencolar.
colaVacia.
desencolar
encolar
Especificacin de TADs. TAD Cola de Enteros (I).
Especificacin Semntica
Especificacin Sintctica
inicializarCola
Mtodo previo que deja a disposicin del
programa un TAD cola (de tipo
TadCola) sobre el que se podr operar
posteriormente. (Equivalente a crear o
construir un objeto/instancia.).
void inicializarCola ()
encolar
Mtodo que entrega un elemento (x)
para que quede incorporado al final de la
cola.
void encolar (int x)
desencolar
Mtodo que elimina el elemento de la
cola que ocupa el primer lugar,
devolvindolo como resultado.
int desencolar ()
colaVacia
Mtodo que al ejecutarse devuelve true si
la cola est vaca, y false en caso
contrario.
boolean colaVacia ()
leerCola
Mtodo mediante el que se produce la
carga inicial de elementos de la cola.
void leerCola () throws
NumberFormatException,
IOException
Especificacin de TADs. TAD Cola de Enteros
(II).
Especificacin Semntica
Especificacin Sintctica
imprimirCola
Mtodo que muestra en el
dispositivo de salida (pantalla) el
contenido actual de la cola.
void imprimirCola ()
invertirCola
Mtodo que devuelve la cola con
sus elementos invertidos
void invertirCola ()
numElemCola
Mtodo que devuelve el nmero
de elementos de la cola.
int numElemCola ()
primero
Mtodo que devuelve el primer
elemento de la cola sin
desencolarlo.
int primero ()
quitarPrimero
Mtodo que elimina el primer
elemento de la cola.
void quitarPrimero ()
eliminarCola
Mtodo que recibe una cola (que
puede tener elementos o no) y la
devuelve vaca.
void eliminarCola ()
Excepciones.
Excepcin: circunstancia que produce que una
Operacin Vlida sobre un TAD no pueda ser efectuada.
Ejemplos:
encolar:
Al intentar encolar un nuevo elemento en la cola, sta est llena:
la operacin encolar no debe producir ningn efecto. No se
contempla tratamiento alguno.
desencolar, primero, quitarPrimero, invertirCola:
Al intentar realizar una de estas operaciones, la cola est vaca:
se producir un mensaje de error.
Interfaz del TAD Cola
import java.io.*;
Define los mtodos de
objeto utilizados en la
clase TadCola
public interface Cola {
void inicializarCola ();
void encolar (int x);
int desencolar ();
boolean colaVacia ();
void leerCola () throws NumberFormatException, IOException;
void imprimirCola ();
void invertirCola ();
int numElemCola ();
int primero ();
void quitarPrimero ();
void eliminarCola ();
}
Condiciones normales y excepcionales de la cola
public class PruebaCola1 {
public static void main (String[] args) {
Cola cola1 = new TadCola ();
int elem;
public class PruebaCola2 {
public static void main (String[] args) {
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 nmero"+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 mdulo
recursivo)
Desencolar Encolar llamada recursiva
No se alcanza la condicin de finalizacin Estructura Vaca
Si se conoce el nmero de elementos
Variable auxiliar que determina la condicin de parada
Permite Tratamiento recursivo y iterativo
Invertir una cola
Mtodo (esttico) auxiliar en el tratamiento recursivo de colas.
static void invertir (Cola cola) {
int elem;
if (!cola.colaVacia ()) {
elem = cola.desencolar ();
invertir (cola);
cola.encolar (elem);
}
}
if (!cola.colaVacia () {
elem = cola.desencolar ();
invertir (cola);
elem = 2
elem = 3
elem = 5
elem = 4
cola.encolar (elem);
}
Contar los
elementos de
una cola
public class PruebaContar {
static int contarCola (Cola cola) {
int elem, resul;
if (!cola.colaVacia ()) {
elem = cola.desencolar ();
resul = 1 + contarCola (cola);
cola.encolar (elem);
}
else resul = 0;
return resul;
}
La solucin recursiva es
la nica posibilidad:
mtodo (esttico)
contarCola
static int cuentaCola(Cola cola) {
cola.invertirCola ();
return contarCola (cola);
}
Necesidad de invertir la
cola fuera del mdulo
recursivo: mtodo
(esttico) cuentaCola.
public static void main(String[] args) {
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 nmero de elementos?
Solucin recursiva (requiere inversin de la cola)
Se conoce el nmero de elementos?
Solucin recursiva
Solucin iterativa
Sin conocer el nmero de elementos. Solucin Recursiva
static void copiar (Cola colaO, Cola colaD) {
int elem;
if (!colaO.colaVacia ()) {
elem = colaO.desencolar ();
colaD.encolar (elem);
copiar (colaO, colaD);
colaO.encolar (elem);
}
}
static void copia (Cola colaO, Cola colaD) {
copiar (colaO, colaD);
colaO.invertirCola ();
}
public static void main (String [] args) {
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
colaD
elem = 2
elem = 3
elem = 5
3 2 5 3
elem = 3
colaO.encolar (elem);
}
Conociendo el nmero de elementos. Solucin Recursiva
static void copiaR2 (Cola colaO, Cola colaD, int n) {
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) {
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 2
n=4
n =3
n =2
n=1
elem = 3
elem = 2
elem = 5
elem = 4
Conociendo el nmero de elementos. Solucin iterativa
static void copiaIt (Cola colaO, Cola colaD) {
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) {
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) {
int elem, i, n;
n = cola.numElemCola ();
cola.encolar (dato);
for (i = 1; i <= n; i++) {
elem = cola.desencolar ();
cola.encolar (elem);
}
}
Terminacin anticipada
Precauciones:
Devolver la cola en su estado original
Si hay terminacin anticipada
Todos los elementos deben sufrir el proceso de encolardesencolar
Si no fuese as, el resultado sera una cola con una parte
ordenada y otra invertida
Buscar un elemento (sin conocer n)
static boolean esta (Cola cola, int dato) {
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) {
cola.invertirCola ();
return esta (cola,dato);
}
Se pasa al mdulo
recursivo la cola
invertida
En el mdulo recursivo:
Desencolar-encolar
invierte los elementos
procesados
Resto de elementos
requieren inversin
Buscar un elemento (n conocido, recursivo)
static boolean recorrer (Cola cola, int n) {
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) {
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) {
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) {
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) {
}
int resul;
return dato;
resul = quitarUlt (cola);
}
cola.invertirCola ();
return resul;
}
Ejercicio propuesto: obtener el elemento
final de la cola conociendo el nmero de
elementos
Combinar dos colas. General.
Dos colas ordenadas (c1 y c2) -> c3 ordenada
Se plantean dos posibilidades:
Sin conocer el nmero de elementos
Conociendo el nmero de elementos
Solucin recursiva.
Solucin iterativa.
Combinar dos colas sin conocer el nmero de
elementos.
El mismo algoritmo que con pilas pero devolvera las colas de
entrada invertidas.
public static void main (String [] args) throws NumberFormatException,IOException {
Cola c1 = new TadCola ();
Cola c2 = new TadCola ();
Cola c3 = new TadCola ();
c1.leerCola ();
c2.leerCola ();
c1.invertirCola ();
c2.invertirCola ();
mezclar** (c1, c2, c3, false, false, 0, 0);
}
Combinar dos colas conociendo el nmero de
elementos. Tcnica recursiva.
Tcnica empleada:
Mtodo 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);
Metodo recursivo:
Condicin de terminacin: !((n1 >= 0) && (n2 >= 0))
Tratamiento especfico:
Fase de transicin.
Terminacin anticipada.
Combinar dos colas conociendo el nmero de
elementos. Tcnica 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 segn el caso.
Llamada recursiva con n1-1|n2-1 segn el caso.
Fase de transicin:
Uso de un procedimiento auxiliar que
reordena la cola no finalizada.
Fase de vuelta:
Sin tratamiento.
Combinar dos colas conociendo el nmero de
elementos. Tcnica 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
segn el caso.
Llamada recursiva con n1-1|n2-1 segn el caso.
Fase de transicin:
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.
MDULO 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
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 mdulo 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
elem1 = 4
elem2 = 5
elem2 = 3
5 1 3
Nueva llamada recursiva con n1-1
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 TRANSICIN
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 terminacin anticipada.
Mezcla AND conociendo el nmero de elementos. Tcnica recursiva.
Mdulo inicial (no recursivo).
Contempla situaciones de excepcin.
Invoca (si procede) al mdulo recursivo. (Igual que en
la mezcla AND).
Mdulo recursivo:
Terminacin pesimista: !((n1 >= 0) && (n2 >= 0)).
Anlisis de casos posibles.
Reordenar la cola pendiente (si hay alguna).
Terminacin anticipada: Si elem1 > elem2.
Devuelve false.
Reordenar ambas colas mediante el mtodo auxiliar.
Resto. Similar a la mezcla AND.
