7/26/2019 algoritmos y extructura de datos

1/15

Mg.Ing. Yuri A. Pomachagua Basualdo

2015

Ing Yuri A. Pomachagua Basualdo rt

7/26/2019 algoritmos y extructura de datos

2/15

Contenido

Definicin de Colas

Operaciones con colas Insercin

Eliminacin

Aplicaciones

rt

Ing Yuri A. Pomachagua Basualdo

7/26/2019 algoritmos y extructura de datos

3/15

Logro

l finalizar esta sesin el alumno ser

capaz de Crear insertar y eliminar colas

utilizando arreglos o listas enlazadas

rt

Ing Yuri A. Pomachagua Basualdo

7/26/2019 algoritmos y extructura de datos

4/15

PILAS Y COLAS

Ing Yuri A. Pomachagua Basualdo rt

7/26/2019 algoritmos y extructura de datos

5/15

Estticas

Arrays

(Vectores y Matrices)

Registros (Record)

Ficheros (File)

Lineales

Listas

Pilas

ColasDinmicas

No lineales

rboles

Grafos

Ing Yuri A. Pomachagua Basualdo rt

7/26/2019 algoritmos y extructura de datos

6/15

La cola (Queue) Es una lista lineal de

elementos en la que los nuevos elementos

se introducen por un extremo y los ya

existentes se eliminan por el otro.

Los elementos de una cola se eliminan en el

orden que ingresaron. Es decir el primer

elemento que ingresa a la estructura es el

primer elemento en salir. A esto se le conoce

con el nombre de estructuras FIFO.

Para su representacin requieren el uso

de otras estructuras de datos como el

ARREGLO o la LISTA

Ing Yuri A. Pomachagua Basualdo rt

7/26/2019 algoritmos y extructura de datos

7/15

Ejemplos:

Cola de personas esperando

ser atendidas

Cola para el autobs

Cola para llamar por telfono

Cola para ingresar al cine.

Cola para el teatro.

Ing Yuri A. Pomachagua Basualdo rt

7/26/2019 algoritmos y extructura de datos

8/15

Ing Yuri A. Pomachagua Basualdo rt

1 100

2 200

3 300

.

.

10 1000

100 200 300 400 . . . . . 1000

1 100

2 200

3 300

4 400

10

1

2

3

10

7/26/2019 algoritmos y extructura de datos

9/15

OPERACIONESCON COLAS

Ing Yuri A. Pomachagua Basualdo rt

7/26/2019 algoritmos y extructura de datos

10/15

Ing Yuri A. Pomachagua Basualdo

Las operaciones bsicas que se pueden llevar son: Insertar un elemento en la Coila Eliminar un elemento en la Cola

Operaciones Auxiliar: Cola_vaca Cola_llena

Las inserciones se llevarn a cabo por el FINAL de lacola, mientras que las eliminaciones se harn por elFRENTE

Considerando que una cola puede almacenar unmximo nmero de elementos y que adems FRENTEindica la posicin del primer elemento y FINAL laposicin del ltimo.

rt

http://www.google.com.pe/url?sa=i&rct=j&q=&esrc=s&frm=1&source=images&cd=&cad=rja&uact=8&docid=GOrWf-9ndOxUHM&tbnid=0QzIOcujsaFiNM:&ved=0CAUQjRw&url=http://www.dreamstime.com/stock-photos-telephone-queue-some-men-making-phone-call-image35732183&ei=ffeXU8D1OOHhsAShkoL4Cw&bvm=bv.68693194,d.cWc&psig=AFQjCNHqIpmC8oh5XjJE2I8tfscT7JyUEA&ust=1402554582312694

7/26/2019 algoritmos y extructura de datos

11/15

Ing Yuri A. Pomachagua Basualdo

Cola_vacia (COLA, FRENTE, SW)

Si (FRENTE ==0)

SW = 1 (La cola est vaca)

Sino

Hacer SW = 0 (La cola no est vaca)

Fin_SI

rt

7/26/2019 algoritmos y extructura de datos

12/15

Ing Yuri A. Pomachagua Basualdo

Cola_llena (COLA, FRENTE, MAX, SW)

Si (FInal == MAX)SW = 1 (La cola est llena)

Sino

SW = 0 (La cola no est llena)

Fin_Si

rt

7/26/2019 algoritmos y extructura de datos

13/15

Ing Yuri A. Pomachagua Basualdo

Insertar_Cola(COLA, MAX, FRENTE, FINAL, Dato)

Si (FINAL < MAX)

FINAL = FINAL + 1;COLA[FINAL] = Dato;

Si (FINAL == 1)

FRENTE = 1;

Fin_Si

SinoEscribir (Desbordamiento cola llena );

Fin_Si

rt

7/26/2019 algoritmos y extructura de datos

14/15

Ing Yuri A. Pomachagua Basualdo

Quitar_Cola(COLA, FRENTE, FINAL, Dato)

Si (FRENTE == 0)

DATO = COLA [FRENTE]Si (FRENTE = FINAL)

FRENTE = 0

FINAL = 0;{Indica COLA vaca}

Sino

FRENTE = FRENTE + 1Fin_Si

Sino

Escribir ("Subdesbordamiento - Cola vaca);

Fin_Si

rt

7/26/2019 algoritmos y extructura de datos

15/15

IMPLEMENTAR EN EL

LABORATORIO LOS ALGORITMOSEXPLICADOS EN CLASE

rt

Ing Yuri A. Pomachagua Basualdo