ZCOLA CON LISTA SIMPLE ENLAZADA

Vista previa del material en texto

COLA LINEAL CON UNA LISTA SIMPLEMENTE ENLAZADA
OPERACIONES PERMITIDAS EN UNA COLA
VER EL ELEMENTO DEL frente
ELIMINAR EL ELEMENTO DEL frente
INSERTAR UN ELEMENTO POR EL fin
VERIFICAR SI LA COLA ESTÁ VACÍA
VERIFICAR SI LA COLA ESTÁ LLENA (SI PUEDE LLENARSE)
IMPLEMENTACIÓN DE UNA COLA
UNA COLA PUEDE REPRESENTARSE MEDIANTE:
UN VECTOR
UNA LISTA ENLAZADA
IMPLEMENTACION DE UNA COLA CON UNA LISTA ENLAZADA
 
FRENTE dato sig dato sig dato sig FIN
 
ver() retorna frente.dato
eliminar() hace frente = frente.sig
Insertar(x) inserta un nuevo nodo al final, a partir de fin
9
10
11 
12
CLASE NODO
class Nodo {
// campos
int dato;
Nodo sig;
// constructor por defecto
public Nodo ()
{ dato = 0; sig = null; }
// constructor ordinario
public Nodo (int vd)
{ dato = vd; sig = null; }
}
dato sig
	Nodo
	dato
sig
	Constructor por defecto
Constructor ordinario
CLASE COLA
class Cola {
// campos
Nodo frente, fin;
// constructor
public Cola ()
{ frente = fin = null; }
// verifica si la cola está vacía
public boolean colaVacia()
{ return (frente == null) && (fin == null); }
	Cola
	frente
fin
	Constructor por defecto
colaVacia()
ver()
eliminar()
insertar(x)
Cola vacía:
frente fin
null
null
CLASE COLA
// ver el elemento del FRENTE
public int ver ()
{ return frente.dato; }
// eliminar el elemento del FRENTE
public void eliminar()
{ if (!colaVacia() ) {
 if(frente== fin) { // COLA CON 1 NODO
 fin = null;
 }
 frente = frente.sig; 
 }
}
CASO 1: COLA CON 1 NODO
frente sig
null
null
 fin
x
null
20
5
 frente
5
X
null
20
CASO 2: CON MÁS DE 1 NODO
frente sig
frente fin
null
 fin
 fin
CLASE COLA
// insertar un elemento por el FIN 
public void insertar (int x)
{ // Crear un nuevo nodo
 Nodo nuevo = new Nodo (x);
 // Conectar el nuevo nodo al FINAL
 if (colaVacia()) { // COLA VACÍA
 frente=nuevo; fin=nuevo;}
 else { // COLA NO VACÍA
 fin.sig = nuevo; fin = nuevo; }
 } 
 } 
}
null
null
 frente
x
frente fin
null
CASO 1: COLA VACÍA
 fin
nuevo
null
20
5
null
x
nuevo
 fin
 frente sig
 sig
CASO 2: COLA NO VACÍA
CLASE OPERACIONES
class Operaciones {
// INSERTAR N ELEMENTOS
public Cola insertarN(Cola co)
{	System.out.print("Nº de elementos= ");
	int n=Leer.datoInt();
	int d;
	for(int c=1; c<=n; ++c)
	{System.out.print("Dato"+c+"= ");
	d=Leer.datoInt();
	co.insertar(d);
 }
return co;
}
	Operaciones
	
	insertarN(p)
mostrar(p)
CLASE OPERACIONES
// MOSTRAR
public Cola mostrar(Cola co)
{ Cola caux=new Cola(); // SE CREA UNA COLA AUXILIAR VACIA: caux
 int d;
 while(!co.colaVacia())
 { d=co.ver();
	System.out.println(" "+d);
	co.eliminar(); 
	caux.insertar(d); 
 }
 return caux; // caux ES IGUAL A co ORIGINAL
}
// LOS METODOS DE LA CLASE OPERACIONES SON INDEPENDIENTES DE LA IMPLEMENTACIÓN DE LA CLASE COLA: SON LOS MISMOS QUE PARA UNA COLA IMPLEMENTADA CON UN VECTOR
CLASE OPERACIONES
// main():
Cola c=new Cola(); 
Operaciones op = new Operaciones();
c= op.insertarN(c);
c= op.mostrar(c); 
PROBLEMAS
2. DEFINIR UNA COLA CON UNA LISTA SIMPLEMENTE ENLAZADA CON DATO double
INSERTAR N NODOS
MOSTRAR
ELIMINAR LOS ELEMENTOS MAYORES AL PROMEDIO
INSERTAR UN ELEMENTO DESPUES DEL MENOR ELEMENTO