universidad hispanoamericana estructura: cola profesor: ing. erick lópez ch. m.r.i
TRANSCRIPT
![Page 1: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/1.jpg)
Universidad Hispanoamericana
Estructura: COLAEstructura: COLA
Profesor:Profesor:Ing. Erick López Ch. M.R.I.Ing. Erick López Ch. M.R.I.
![Page 2: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/2.jpg)
COLAS
El concepto de cola es ampliamente utilizado en la vida real.
Fila en el cine, en el autoservicio, cajeros automáticos, etc. Esto significa que formamos una fila en la que el primero que llega es el primero en obtener el servicio y salir de la misma. Esta política de funcionamiento se denomina FIFO (First In First Out), es decir, el primer elemento en entrar es el primer elemento en salir:
Definición: Una cola es un conjunto ordenado de elementos
homogéneos, en el cual los elementos se eliminan por uno de sus extermos, denominado frente (cabeza), y se añaden por el otro extremo, denominado fondo (final). Las eliminaciones y añadidos se realizan siguiendo una política FIFO.
![Page 3: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/3.jpg)
COLAS
Al igual que las pilas, las colas se gestionan añadiendo y borrando elementos de las mismas. En este caso en particular las dos operaciones básicas de maniopulación funcionan del siguiente modo:
AÑADIR: Añade un elemento al final de la cola. ELIMINAR: Elimina un elemento del frente de la cola.
E1
E2
E3
E1 E1
E2 E2
E2
E3 E3
E3
E4 E4
E4
E5
E5
Cab Cab Cab Cab
FinFin
Fin
Fin
![Page 4: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/4.jpg)
COLAS
En el ámbito de la informática las colas son ampliamente utilizadas. Por ejemplo, los sistemas operativos suelen utilizar esta estructura de datos para gestionar los recursos que pueden ser compartidos por varios procesos (gestión de memoria, tiempo de procesador, etc). En general, las colas se aplicarán cuando los objetos manejados sigan una política FIFO.
![Page 5: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/5.jpg)
COLAS - Axiomas
1. ColaVacia(CrearCola) = Verdadero2. ColaVacia(Añadir(S,e))=falso3. Eliminar(CrearCola) = error4. Eliminar(Añadir(S,e)) = Si ColaVacia(S) entonces
CrearCola sino Añadir(Eliminar(S),e)5. Cabeza(CrearCola) = error6. Cabeza(Añadir(S,e)) = Si ColaVacia(S) entonces e
sino Cabeza(S)
![Page 6: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/6.jpg)
COLAS - Implementación
CONSTMax = … ; {número máximo de elementos}TYPE TipoCola = Record datos:array[1..Max] of TipoBase; Frente, Fondo:0..Max End;
![Page 7: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/7.jpg)
COLAS - ImplementaciónPROCEDURE CrearCola (var q:tipoCola);Begin q.frente:=0; q.fondo:=0;End;PROCEDURE ColaVacia (q:TipoCola):Boolean;Begin ColaVacia:=(q.frente=q.fondo)End;PROCEDURE Frente(q:TipoCola; var e:TipoBase);Begin If Not ColaVacia(q) then
e:=q.datos[q.frente+1] end;End;
![Page 8: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/8.jpg)
COLAS - Implementación
PROCEDURE Eliminar (var q:tipoCola);Begin If Not ColaVacia(q) Then q.frente:=q.frente+1 endEnd;
PROCEDURE Añadir (var q:TipoCola; e:TipoBase);Begin If Not ColaLlena(q) Then q.fondo:=q.fondo+1; q.datos[q.fondo]:=e EndEnd;
![Page 9: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/9.jpg)
COLAS Circulares
![Page 10: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/10.jpg)
COLAS - Implementación
FUNCTION Siguiente ( i:INTEGER ):INTEGER;FUNCTION Siguiente ( i:INTEGER ):INTEGER;BEGIN
IF (i<>MAX) THENSiguiente := i+1
ELSESiguiente := 1
END;
FUNCTION Siguiente ( i:INTEGER ):INTEGER;FUNCTION Siguiente ( i:INTEGER ):INTEGER;BEGIN
Siguiente := i MOD MAX + 1END;
![Page 11: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/11.jpg)
COLAS - Implementación
PROCEDURE CrearCola ( VAR q: TipoCola );PROCEDURE CrearCola ( VAR q: TipoCola );BEGIN
q.cabeza := MAX;q.final := MAX
END;
![Page 12: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/12.jpg)
COLAS - Implementación
FUNCTION ColaVacia ( q: TipoCola ): BOOLEAN;FUNCTION ColaVacia ( q: TipoCola ): BOOLEAN;BEGIN
ColaVacia := (q.cabeza=q.final)END;
PROCEDURE Cabeza PROCEDURE Cabeza (q: TipoCola ; VAR e:Tipobase;);(q: TipoCola ; VAR e:Tipobase;);
BEGINIF Not ColaVacia(q) THEN
BEGINe := q.datos[Siguiente(q.cabeza)]
ENDEND;
![Page 13: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/13.jpg)
COLAS - Implementación
PROCEDURE Eliminar ( VAR q: TipoCola);PROCEDURE Eliminar ( VAR q: TipoCola);BEGIN
IF Not ColaVacia(q) THENBEGIN
q.cabeza := Siguiente(q.cabeza)END
END;
![Page 14: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/14.jpg)
COLAS - Implementación
PROCEDURE Añadir PROCEDURE Añadir (VAR q: TipoCola; e:Tipobase);(VAR q: TipoCola; e:Tipobase);
BEGINIF Not ColaLlena(q) THEN
BEGINq.final := Siguiente(q.final);q.datos[q.final] := e
ENDEND;
![Page 15: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/15.jpg)
COLAS - Implementación
![Page 16: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/16.jpg)
COLAS - Implementación
![Page 17: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/17.jpg)
COLAS - Implementación
![Page 18: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/18.jpg)
COLAS - Implementación
![Page 19: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/19.jpg)
Universidad Hispanoamericana
![Page 20: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/20.jpg)
EJERCICIO COLA
Un concesionario de autos tiene un número limitado m de modelos, todos en un número limitado c de colores distintos. Cuando un cliente quiere comprar un auto, pide un auto de un modelo y color determinados. Si el auto de ese modelo y color no está disponible en el concesionario, se toman los datos del cliente (nombre y dirección), que verá atendida su petición cuando el auto esté disponible. Si hay más de una petición de un auto de las mismas características, se atienden las peticiones por orden cronológico. Se pide:
a) Definir la estructura de datos más adecuada capaz de contener las peticiones de un modelo y color de auto.
b) Definir una operación que, dado un cliente (nombre y dirección) que desea comprar un auto de un modelo y color determinado, coloque sus datos como última petición de ese modelo y color.
![Page 21: Universidad Hispanoamericana Estructura: COLA Profesor: Ing. Erick López Ch. M.R.I](https://reader035.vdocumento.com/reader035/viewer/2022062222/5665b4e51a28abb57c9492d2/html5/thumbnails/21.jpg)
EJERCICIO COLA
c) Definir una operación que, dado un modelo del que se han recibido k autos de determinado color, elimine los k primeros clientes de la lista de peticiones de ese coche y los devuelva en un vector, sabiendo que k <= 20.