Estructuras de datos y algoritmos
Oscar Bedoya.
[email protected]
http://eisc.univalle.edu.co/~oscarbed/Estructuras/
Edificio 331, 2º piso, E.I.S.C.
Cola
Definición
Una cola es un conjunto ordenado de elementos
de un tipo base. Los elementos se insertan a la
cola por la parte posterior y se sacan por la parte
delantera
Cola
Definición
TDA
Cola
Descripción:
El TDA Cola se caracteriza porque el primero en entrar es el
primero en salir (Estructura FIFO)
Invariante:
Cola=(elem, cab, col), elem=<elem0, elem1, . . . , elemn-1> л
( i,
0 <= i < n, elemi  Tipo) л elem0=col л elemn-1 =cab
Cola
Operaciones:
Cola (Constructor)
Meter
Sacar
Imprimir cola
Buscar elemento en la cola
Es una cola vacía?
Cola
A
W
cola
cabecera
Cola
A
W
cola
cabecera
X
A
W
cola
cabecera
Cola
X
A
W
cola
cabecera
X
A
cola
cabecera
Cola
•Crear cola
Al crear una lista, se
crean el nodo cola y
el nodo cabecera.
cola
cabecera
Ambos tienen como
dato null y como
siguiente null.
Cola
•Meter( La cola está vacía)
•Se crea un nuevo nodo con el
dato que se desee colocar y con
siguiente null
cola
cabecera
W
cola
cabecera
•El campo siguiente del nodo
cabecera pasa de ser null a ser el
nodo que estamos insertado
•El campo siguiente del nodo
cola pasa de ser null a ser el
nodo que estamos insertado
Cola
•Meter( La cola no está vacía)
•Se crea un nuevo nodo con el
dato que se desee colocar y con
siguiente, al siguiente del nodo
cabecera
W
cola
•El campo siguiente del nodo
cabecera pasa de ser null a ser el
nodo que estamos insertado
cabecera
X
W
cola
cabecera
Cola
•Sacar
X
W
cola
cabecera
X
cola
cabecera
Cola
•Imprimir datos
Cola
•Está una cola vacía?
Cuando la cola está vacía el
campo siguiente de la cabecera
es null y el campo siguiente de
la cola es null
cola
cabecera
Cola
class Nodo{
Object dato;
Nodo siguiente;
Nodo(Object o)
{
dato=o;
siguiente=null;
}
Nodo(Object o, Nodo n)
{
dato=o;
siguiente=n;
}
}
Cada nodo se
representa por medio
de dos campos:
Campo dato: contiene
el valor del nodo
Campo siguiente:
indica cuál es el nodo
con el que se enlaza
Cola
class Cola{
Nodo cabecera;
Nodo cola;
Cola()
{
cabecera=new Nodo(null);
cola=new Nodo(null);
}
}
Al crear una lista, se
crean el nodo cola y el
nodo cabecera.
Ambos tienen como
dato null y como
siguiente null.
Cola
public boolean estaVacia(){
if (cabecera.siguiente==null)
•Está una cola
vacía?
{
return true;
}
else
{
return false;
}
}
Cuando la cola está
vacía el campo
siguiente de la
cabecera es null. El
campo siguiente de
la cola también es
null
Cola
void meter(Object o)
{
Nodo nuevo=new Nodo(null);
if ( estaVacia() )
{
nuevo=new Nodo(o);
nuevo.siguiente=null;
cabecera.siguiente=nuevo;
cola.siguiente=nuevo;
}
•Se crea un nuevo nodo
con el dato que se desee
colocar y con siguiente
null
•El campo siguiente del
nodo cabecera pasa de ser
null a ser el nodo que
estamos insertado
•El campo siguiente del
nodo cola pasa de ser null
a ser el nodo que estamos
insertado
Cola
else
{
nuevo=new Nodo(o);
nuevo.siguiente=cabecera.siguiente;
cabecera.siguiente=nuevo;
}
}
•Se crea un nuevo nodo
con el dato que se desee
colocar y con siguiente, al
siguiente del nodo
cabecera
•El campo siguiente del
nodo cabecera pasa de ser
null a ser el nodo que
estamos insertado
Cola
public void sacar()
{
Nodo borrar=cola.siguiente;
if(cabecera.siguiente==cola.siguiente){
cabecera.siguiente=null;
cola.siguiente=null;
}
else{
Nodo aux=cabecera;
while( aux.siguiente!=borrar)
aux=aux.siguiente;
aux.siguiente=null;
cola.siguiente=aux;
}
}
Descargar

Cola