Colas cierculares Lenguaje de programacion II

TAD Cola

Definición, implementación y
aplicaciones

Algoritmos y Estructuras de Datos

´
Departamento de Electricidad y Electr onica
(UPV/EHU)

TAD Cola – p.1/33

TAD COLA
Indice
1. Definición e interfaces básicos
2. Implementación mediante arrays estáticos (v1)
3. Implementación mediante arrays estáticos (v2: colas circulares)
4. Implementación mediante listas ligadas
5.Colas de prioridad
5.1. Definición e interfaces
5.2. Implementación basada en arrays estáticos
5.3. Implementación basada en listas ligadas
6. Ejercicios

Algoritmos y Estructuras de Datos

´
Departamento de Electricidad y Electr onica
(UPV/EHU)

TAD Cola – p.2/33

Definición
1

2

3

4

8

56

2

−15

primer
elemento

5

6

MAX−1 MAX

..........

ultimoelemento

por este extremo
se accede y se eliminan
elementos

por este extremo
se añaden nuevos
elementos

Cola: conjunto dinámico de tipo FIFO (First Input First Output): el
primer elemento que entra al conjunto es el primero que sale.
No es posible acceder a elementos intermedios. Sólo es
accesible (y eliminable) el primer elemento de la cola, y sólo se
pueden añadir nuevos elementostras el último elemento de la
cola.
Ejemplos: cola de un supermercado, cola para imprimir, colas de
despegue y aterrizaje de un aeropuerto, etc.
Algoritmos y Estructuras de Datos

´
Departamento de Electricidad y Electr onica
(UPV/EHU)

TAD Cola – p.3/33

Interfaces básicos
procedimiento inicializar (ref q: COLA)
inicializa la variable q de tipo COLA
realiza las reservas dinámicasde memoria necesarias
como resultado, se tendrá una cola q vacía
inicializar (q): primera acción a realizar sobre q

Algoritmos y Estructuras de Datos

´
Departamento de Electricidad y Electr onica
(UPV/EHU)

TAD Cola – p.4/33

Interfaces básicos
procedimiento inicializar (ref q: COLA)
función añadir (ref q: COLA, x: ELEMENTO): booleano
añade el elemento x a la cola q
devuelve:Algoritmos y Estructuras de Datos

TRUE

si la operación se realiza con éxito

FALSE

si la cola q está llena

´
Departamento de Electricidad y Electr onica
(UPV/EHU)

TAD Cola – p.4/33

Interfaces básicos
procedimiento inicializar (ref q: COLA)
función añadir (ref q: COLA, x: ELEMENTO): booleano

q

1

2

3

4

8

56

2

−15

5

6

MAX−1 MAX..........

añadir(q,7)

q

Algoritmos y Estructuras de Datos

1

2

3

4

5

8

56

2

−15

7

6

MAX−1 MAX

..........

´
Departamento de Electricidad y Electr onica
(UPV/EHU)

TAD Cola – p.4/33

Interfaces básicos
procedimiento inicializar (ref q: COLA)
función añadir (ref q: COLA, x: ELEMENTO): booleano
función primero(q: COLA): ELEMENTO
devuelve el valordel elemento que ocupa la primera
posición en la cola q
precondición: q no vacía

Algoritmos y Estructuras de Datos

´
Departamento de Electricidad y Electr onica
(UPV/EHU)

TAD Cola – p.4/33

Interfaces básicos
procedimiento inicializar (ref q: COLA)
función añadir (ref q: COLA, x: ELEMENTO): booleano
función primero(q: COLA): ELEMENTO

q

1

2

3

4

5

8

56

2−15

7

6

MAX−1 MAX

..........

primero(q) −→ 8

Algoritmos y Estructuras de Datos

´
Departamento de Electricidad y Electr onica
(UPV/EHU)

TAD Cola – p.4/33

Interfaces básicos
procedimiento inicializar (ref q: COLA)
función añadir (ref q: COLA, x: ELEMENTO): booleano
función primero(q: COLA): ELEMENTO
función avanzar (ref q: COLA): ELEMENTO
extrae de la cola q elelemento que ocupa la primera
posición, lo cual significa que el elemento que antes
ocupaba la segunda posición ahora ocupa el primer
lugar.
devuelve el valor del elemento extraído.
precondición: q no vacía
Algoritmos y Estructuras de Datos

´
Departamento de Electricidad y Electr onica
(UPV/EHU)

TAD Cola – p.4/33

Interfaces básicos
procedimiento inicializar (ref q: COLA)...