Upload
liz-coba
View
16
Download
2
Embed Size (px)
DESCRIPTION
Colas circulares
Citation preview
Here comes your footer Page 2
Introducción
La cola es una estrutura de datos en el cual los elementos se insertan por un extremo (fin o posterior) y se eliminan por el otro (anterior o frente).
También se conocen como estructuras FIFO “primero en entrar, primero en salir “.
Página
Entra
Sale
fin
frente
sale
Here comes your footer Page 3
Ejemplos o aplicaciones de Colas
Página
En computadoras:
Documentos enviados a una impresora
Personas esperando ser atendidas :
supermercados, taquillas, bancos , etc.
Here comes your footer Page 4
Colas Circulares
Página
Problema con las colas lineales hacen que surjan las colas circulares.
La idea general es insertar elementos en posiciones previamente desocupadas
fin frente0
1
Max-1
...
...
Here comes your footer Page 5
Funciones de colas
Página
Vacía(C) Frente(C) Agrega(x,c) Suprime(C) Anula(C) Imprime(C) long(C) Busca(x,C).
Here comes your footer Page 7
Anula ( C )
Página
fin = -1frente = -1
Mostrar : La cola fue anulada
-9 10 1 11
frente fin
0 1 2 3 4 5 6 - 1
frente finOperación fundamentalOperación fundamental : Asignar. : Asignar.T (n)T (n) : Constante : Constante
Here comes your footer Page 8
Vacia ( C )
Página
Si ( frente = -1 y fin = -1) mostrar :Verdadero.
Sino mostrar : Falso.
OperaciónOperación : Comparación : Comparación T (n)T (n) : Constante. : Constante.
frente y fin =-1
1 29
frente
fin
verdaderofalso
Here comes your footer Page 9
Agrega ( x , C )
Página
Si ( (fin+1 == frente ) ò ( (frente == 0 ) y ( fin == max-1) ) ) mostrar :La cola esta llena, no se puede agregar. Sino Si ( fin == max-1)
fin=0; Cola [ fin ] = x Sino fin = fin + 1 Cola [ fin ] = x
Si ( frente == -1) frente=0
T (n):T (n): constante constanteOp. FundamentalOp. Fundamental: Asignar el elemento x: Asignar el elemento x a la Colaa la Cola
8 15 2
frente fin
0 1 2 3 4 5 6
113 356 3 5 3
frente fin
0 1 2 3 4 5 6
3 4 6
frentefin
0 1 2 3 4 5 6
7
Here comes your footer Page 10
Suprime ( C )
Si ( vacía (C) == verdadero ) Mostrar : La cola esta vacía. Sino Si( frente == fin ) Anula( C )
else Si ( frente == max-1) frente=0 Sino frente = frente + 1
finfrente
15
0 1 2 3 4 5 6
finfrente
15
0 1 2 3 4 5 6
3
fin frente
15
0 1 2 3 4 5 6
153
finfrente
15
0 1 2 3 4 5 6
1 -6 12
Página
finfrente
15
0 1 2 3 4 5 6
-6 12T (n): constante.T (n): constante.Op. Fundamental: aumenta el frente en 1.Op. Fundamental: aumenta el frente en 1.
Here comes your footer Page 11
Frente ( C )
Página
Si ( vacía (c) == verdadero) mostrar : La cola esta vacía. Sino Mostrar : Cola [ frente ]
T(n): constanteT(n): constanteOp. Fundamental: mostrar el primer Op. Fundamental: mostrar el primer elemento ingresado a la Colaelemento ingresado a la Cola
0 1 2 3 4 5 6
finfrente
983015
Frente = 15
Here comes your footer Page 12
Imprimir ( C )
Página
Si ( vacía (c) == verdadero) mostrar : La cola esta vacíaSino dato_aux = frente //variable que guarda el frente de la Cola Original Repetir mientras ( Vacía (C) != verdadero )
Mostrar = “ Posición “ frente "------" Frente (C) Agrega ( Frente (C) ,D) Elimina (C )
Traspaso ( dato_aux , C ,D) Anula (D)
0 1 2 3 4 5 6
finfrente
983332
frente
0 1 2 3 4 5 6
fin
983332
Cola C Cola D
frentefrente frente finfin fin finfrente
983332
0 1 2 3 4 5 6
Cola C
finfrente
0 1 2 3 4 5 6
Cola D
frente fin
T(n): nT(n): nOp. Mostrar elemento a elementoOp. Mostrar elemento a elemento
Here comes your footer Page 13
Traspaso ( dato_aux , C, D)
frente = dato_aux
fin = dato_aux -1
Repetir mientras (Vacia(D) !=veradero)
Agrega(Frente(D),C)
Elimina(D)
Página
0 1 2 3 4 5 6
finfrente
983332
0 1 2 3 4 5 6
finfrente
9832 33
Cola D Cola C
finfrente
frente =1 y fin =1-1=0
frentefrentefrente fin fin fin
T(n): nT(n): nOp. Cambiar los elementos de una cola a otraOp. Cambiar los elementos de una cola a otra
Here comes your footer Page 14
Long ( C )
Página
Si ( Vacia (C) == verdadero ) mostrar : La cola esta vacia .
Sino Si ( fin >= frente ) Mostrar : ( ( fin – frente ) + 1 ).
Sino Mostrar : ( ( ( max - frente ) + fin ) + 1 ).
T(n): constanteT(n): constanteOp. Fundamental: realiza el cálculo Op. Fundamental: realiza el cálculo correspondiente y lo devuelve.correspondiente y lo devuelve.
0 1 2 3 4 5 6
finfrente
983015 ( 4 - 1 ) + 1 = 4
0 1 2 3 4 5 6
fin frente
983015 ( ( 7 – 5) + 1 ) +1 = 4
Here comes your footer Page 15
Busca ( x , C )
Página
Si ( vacía (c) == verdadero) mostrar : La cola esta vacía sino kont =0 // para saber si existe o no el dato en la Cola
dato_aux = frente Anula (D) Repetir mientras (Vacía (C) != verdadero) Si (x == Frente (C)) Mostrar : El elemento se encuentra en la Cola, y esta en la posición -- frente kont =1 Agrega (Frente (C),D) Elimina (C) Sino Agrega (Frente (C),D) Elimina (C) Si (kont==0) mostrar : Este elemento NO se encuentra en la Cola Traspaso ( dato_aux, C, D)
Here comes your footer Page 16Página
Busca ( x , C )
0 1 2 3 4 5 6
finfrente
98337
0 1 2 3 4 5 6
finfrente
Cola C Cola D
X = 3
Si x = Frente ( C )
Muestra : existe este elemento y esta en la posición frente
7 33 98
frente finfrentefrente frente fin finfin
T(n): nT(n): nOp. Fundamental: recorre toda la cola para Op. Fundamental: recorre toda la cola para encontrar los posibles x .encontrar los posibles x .