Colas
Estructuras y organización de datos
Definición
•Una cola es un conjunto de componentes
homogéneos, los cuales se insertan y se eliminan
de acuerdo con el principio FIFO (Fisrt In, First
Out): el primer componente en insertarse es el
primero en eliminarse.
Definición
•Una cola es una colección de datos que sólo puede
accederse por dos extremos, uno llamado frente
para eliminar datos y otro llamado final para
insertar datos.
Frente Final
Aplicaciones
Clasificación
•Cola estática •Cola dinámica
•Se implementa con un •Se implementa con una
arreglo lista ligada
p=frente
final
4
Clasificación
•Cola doble o bicola •Cola circular
•Inserción/eliminación •El siguiente componente
por el frente o final del final es el frente
Frente=(Frente+1)%MAX
Final=(Final+1)%MAX
Operaciones
•Encolar. Inserta un componente en el final
•Desencolar. Eliminar el componente en el frente
•Ver el frente. Consulta el componente del frente
•Ver el final. Consulta el componente del final
•Es vacía. Verifica si está vacía
desencola( ) encola(sábado)
Implementación en Java
<<interface>> Cola esVacia regresa verdadero si la cola
está es vacía, falso en otro caso
+esVacia():boolean
+verFrente():Object verFrente/Final regresa el objeto
+verFinal ():Object
almacenado en el frente/final o null si la
+encolar(info:Object):Object
+desencolar():Object cola es vacía
<<implements>>
encolar regresa el objeto insertado
ColaDinamica exitosamente en el final, regresa null en
-lacola:LinkedList otro caso
+ColaDinamica(p:ListaSimple) desencolar regresa el objeto
+ColaDinamica()
+setLaCola(p:LinkedList):void eliminado del frente o null si es vacía
+getLaCola():LinkedList
+esVacia():boolean
+verFrente():Object
+verFinal():Object
+encolar(info:Object):Object
+desencolar():Object
Implementación en Java
Implementación en Java
Implementación en Java
Implementación en Java
Aplicación: Despacha proceso por
rebanadas de tiempo=2ut
Procesador Procesador Procesador Procesador
P1 P1 P2
P1 P2 P2 P3
P2 P3 P3 P4
P3 P4 P4 P5
P4 P5 P5
P5
ColaProc ColaProc ColaProc ColaProc
Aplicación: Despacha proceso por
rebanadas de tiempo=2ut
Procesador Procesador Procesador Procesador
P2 P3 P4 P4
3 2
P3 P3
P4 3 P5 2 P5 2
P4 P5 2 P2 1 P2 1
P5 P2 1
ColaProc ColaProc ColaProc ColaProc
Aplicación: Despacha proceso por
rebanadas de tiempo=2ut
Procesador Procesador Procesador Procesador
8 9 10 11
P5 P5 P2 P4
1 1
P2 P3
P2 13 P4 1
P4 1 P4 1
2
P2 1
ColaProc ColaProc ColaProc ColaProc
Aplicación: Despachador de procesos
<<interface>> Cola
<<implements>>
usa
ColaDinamica LinkedList
usa
DespachadorP
-colaProc:ColaDinamica
-rebanadaT:int Proceso
-procEnDespacho:Proceso -id:String
-tiempo:int 1 0…* -numOp:int
tiene
+DespachadorP() +Proceso()
+set/get +Proceso(i:String,n:int)
+creaColaProcs():void +set/get
+despachaProcs():void
+main(args:String[]):void
Aplicación: creaColaProcs
1. Inicio
2. Leer (rebanadaT)
3. Leer (numProcs)
4. Para i=0,1,…,numProcs-1
4.1. Leer (idProc)
4.2. Leer (numOp)
4.3. [Link](new Proceso(id,numOp))
5. Fin
Aplicación: despachaProcs
1. Inicio
2. Tiempo = 0
3. Mientras colaProcs no vacío
3.1. procesoEnDespacho = [Link]()
3.2. id=[Link]
3.3. numOp = [Link]
3.4. contaReb = 1
3.5. Mientras numOp>0 & contaReb<rebanadaT
3.5.1. Escribir (‘Tiempo=‘,Tiempo)
3.5.2. Escribir (‘Despachando a: ‘,id)
3.5.3. Escribir (numOp,’transacciones’)
3.5.4. numOp--
3.5.5. contaReb++
3.5.6. Tiempo++
3.6. Si numOp>0
3.6.1. [Link](new Proceso(id,numOp))
4. Fin
Aplicación: main
1. Inicio
2. Declarar e instanciar midesp de la clase DespachadorP
3. Crear cola de procesos
4. Despachar los procesos
5. Fin
