Tipos de Colas en Java

INSTITUTO TECNOLGICO DE ESTUDIOS SUPERIORES
DE LOS CABOS
Por una patria con sabidura y espritu de progreso
Listas tipo colas

MATERIA:
Estructura de Datos
PRESENTA:
Delfino Alvarado Mendoza
CATEDRATICO:
Mauro Antonio Jernimo Montero
ndice
Introduccin................................................................................................... 3
Lista
Tipo Cola............................................................................................ 4
Conclusin...................................................................................................... 7
Bibliografa..................................................................................................... 8
Introduccin
Una cola puede almacenar lo que nosotros queramos, nmeros, personas,
documentos, cualquier cosa. Esta estructura de datos tiene muchas
aplicaciones en la informtica al igual que la pila, por ejemplo cuando mandan
a imprimir varios documentos a una impresora, existe una cola de impresin
que sigue la filosofa, se imprimen los primeros documentos y si quiero imprimir
un nuevo documento se adiciona al final de todos los documentos que estn
esperando a imprimirse.
Una vez comprendido en concepto ahora veamos como se implementa esto en
un lenguaje de programacin, por ahora lo implementaremos en Java. Java en
sus libreras ya tiene la forma de implementar Colas (queue), nosotros ahora
haremos como si no existiera, es decir crearemos nuestra versin, que es lo
que generalmente se hace cuando se aprende colas en la universidad.
Pues bien existen dos formas de implementar para que la cola sea o bien
esttica (reservamos un espacio fijo en memoria) o bien dinmica (el tamao
en memoria va creciendo segn se requiere), se implementa con arrays o con
listas enlazadas respectivamente. Nosotros implementaremos haciendo de un
array bidimensional es decir de modo esttico y al decir esttico estamos
diciendo que tendr un limite para almacenar datos en la cola.
Lista
Tipo Cola
Una lista se comporta como una cola si las inserciones las hacemos al final y
las extracciones las hacemos por el frente de la lista. Tambin se las llama
listas FIFO (First In First Out - primero en entrar primero en salir)
Confeccionaremos un programa que permita administrar una lista tipo cola.
Desarrollaremos los mtodos de insertar, extraer, vacia e imprimir.
La declaracin del nodo es igual a la clase Pila. Luego definimos dos punteros
externos:
private Nodo raiz,fondo;
raz apunta al principio de la lista y fondo al final de la lista. Utilizar dos
punteros tiene como ventaja que cada vez que tengamos que insertar un nodo
al final de la lista no tengamos que recorrerla. Por supuesto que es
perfectamente vlido implementar una cola con un nico puntero externo a la
lista.
En el constructor inicializamos a los dos punteros en null (Realmente esto es
opcional ya que los atributos de una clase en java se inicializan
automticamente con null):
Cola() {
raiz=null;
fondo=null;
}
El mtodo vaca retorna true si la lista no tiene nodos y false en caso contrario:
boolean vacia (){
if (raiz == null)
return true;
else
return false;
}
En la insercin luego de crear el nodo tenemos dos posibilidades: que la cola
est vaca, en cuyo caso los dos punteros externos a la lista deben apuntar al
nodo creado, o que haya nodos en la lista.
Nodo nuevo;
nuevo = new Nodo ();
nuevo.info = info;
nuevo.sig = null;
if (vacia ()) {
raiz = nuevo;
fondo = nuevo;
} else {
fondo.sig = nuevo;
fondo = nuevo;
}
Recordemos que definimos un puntero llamado nuevo, luego creamos el nodo

con el operador new y cargamos los dos campos, el de informacin con lo que
llega en el parmetro y el puntero con null ya que se insertar al final de la lista,
es decir no hay otro despus de este.
Si la lista est vaca:
En caso de no estar vaca:
Debemos enlazar el puntero sig del ltimo nodo con el nodo recin creado:
fondo.sig = nuevo;
Y por ltimo el puntero externo fondo debe apuntar al nodo apuntado por
nuevo:
fondo = nuevo;
Con esto ya tenemos correctamente enlazados los nodos en la lista tipo cola.
Recordar que el puntero nuevo desaparece cuando se sale del mtodo insertar,
pero el nodo creado no se pierde porque queda enlazado en la lista.
El funcionamiento del mtodo extraer es similar al de la pila:
int extraer ()
{
if (!vacia ())
{
int informacion = raiz.info;
if (raiz == fondo){
raiz = null;
fondo = null;
} else {
raiz = raiz.sig;
}
return informacion;
} else
return Integer.MAX_VALUE;
}
Si la lista no est vaca guardamos en una variable local la informacin del
primer nodo:
int informacion = raiz.info;
Para saber si hay un solo nodo verificamos si los dos punteros raiz y fondo
apuntan a la misma direccin de memoria:
if (raiz == fondo){
Luego hacemos:
raiz = null;
fondo = null;
En caso de haber 2 o ms nodos debemos avanzar el puntero raiz al siguiente

nodo:
raiz = raiz.sig;
Ya tenemos la lista correctamente enlazada (raiz apunta al primer nodo y fondo

contina apuntando al ltimo nodo)
Conclusin
Para manipular elementos en el vector de la cola son necesarias variables que
me digan en donde empiezan los elementos y otra en donde terminan, como tal
vez ests pensando porque no solo una? (una que me diga en donde termina
asumiendo que siempre se empieza desde la posicin 0 del array), pues se
puede implementar con solo una de estas variables pero presenta muchas
desventajas pues si eliminamos un elemento de nuestra cola, (el primero
justamente)
Tendramos que recorrer todos los siguientes elementos una posicin adelante
y esta manera seria muy lenta de implementar pues que pasa si son 1000
elementos, eso es mucho tiempo perdido, entonces es por eso que usamos
dos variables que me digan donde empieza y donde terminan los elementos de
la cola, dos variables enteras que llamaremos inicio y fin, estas variables
funcionan de la siguiente manera:
Bibliografa
http://www.javaya.com.ar/detalleconcepto.php?codigo=117&inicio=40

Tipos de Colas en Java

Cargado por

Copyright:

Formatos disponibles

Tipos de Colas en Java

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Tipos de Colas en Java

Cargado por

Copyright:

Formatos disponibles

INSTITUTO TECNOLGICO DE ESTUDIOS SUPERIORES

Por una patria con sabidura y espritu de progreso

Listas tipo colas

Recordemos que definimos un puntero llamado nuevo, luego creamos el nodo

En caso de no estar vaca:

En caso de haber 2 o ms nodos debemos avanzar el puntero raiz al siguiente

Ya tenemos la lista correctamente enlazada (raiz apunta al primer nodo y fondo

También podría gustarte