Oscar Bedoya.

oscarbed@eisc.univalle.edu.co

http://eisc.univalle.edu.co/~oscarbed/Estructuras/

Edificio 331, 2º piso, E.I.S.C.

Estructuras de datos y Estructuras de datos y algoritmosalgoritmos

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)MeterSacarImprimir colaBuscar elemento en la colaEs una cola vacía?

Cola

A W

cola

cabecera

A W

cola

cabecera

A W

cola

cabecera

X

Cola

A W

cola

cabecera

X

A

cola

cabecera

X

Cola

•Crear cola

Al crear una lista, se crean el nodo cola y el nodo cabecera.

Ambos tienen como dato null y como siguiente null.

cola

cabecera

Cola

•Meter( La cola está vacía)•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

cabecera

cola

cabecera

W

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

•El campo siguiente del nodo cabecera pasa de ser null a ser el nodo que estamos insertado

cola

cabecera

W

cola

cabecera

W X

Cola

•Sacar

cola

cabecera

W X

cola

cabecera

X

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

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

class Nodo{

Object dato; Nodo siguiente;

Nodo(Object o) { dato=o; siguiente=null; }

Nodo(Object o, Nodo n) { dato=o; siguiente=n; }}

Cola

Al crear una lista, se crean el nodo cola y el nodo cabecera.

Ambos tienen como dato null y como siguiente null.

class Cola{

Nodo cabecera; Nodo cola;

Cola() { cabecera=new Nodo(null); cola=new Nodo(null); }

}

Cola

•Está una cola vacía?

Cuando la cola está vacía el campo siguiente de la cabecera es null. El campo siguiente de la cola también es null

public boolean estaVacia(){

if (cabecera.siguiente==null)

{

return true;

}

else

{

return false;

}

}

Cola

•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

void meter(Object o) { Nodo nuevo=new Nodo(null);

if ( estaVacia() ) { nuevo=new Nodo(o); nuevo.siguiente=null; cabecera.siguiente=nuevo; cola.siguiente=nuevo; }

Cola

•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

else { nuevo=new Nodo(o); nuevo.siguiente=cabecera.siguiente; cabecera.siguiente=nuevo; } }

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; } }

Cola