PDF de programación - Tema 3. Colas - Programación II

Programación II
Tema 3. Colas

Iván Cantador y Rosa Mª Carro
Escuela Politécnica Superior
Universidad Autónoma de Madrid

Contenidos

1

• El TAD Cola
• Estructura de datos y primitivas de Cola
• Estructura de datos de Cola como array circular
• Implementación en C de Cola

• Implementación con front y rear de tipo entero



• Anexo

• Implementación con front y rear de tipo puntero

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

2

• El TAD Cola
• Estructura de datos y primitivas de Cola
• Estructura de datos de Cola como array circular
• Implementación en C de Cola

• Implementación con front y rear de tipo entero



• Anexo

• Implementación con front y rear de tipo puntero

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

El TAD Cola
• Cola (queue en inglés)

3

• Colección de elementos FIFO - First In, First Out: “el primero que

entra, el primero que sale”

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

El TAD Cola

4

• Definición de Cola

• Contenedor de elementos que son insertados y extraídos

siguiendo el principio de que el primero que fue insertado será
el primero en ser extraído (FIFO – First In, First Out)

‐ Los elementos se insertan de uno en uno: insertar
‐ Los elementos se extraen de uno en uno: extraer
‐ La posición de la cola donde se encuentra el siguiente elemento a ser

extraído se denomina front (o head, inicio)

‐ La posición de la cola donde se colocará el siguiente elemento que se

inserte se denomina rear (o tail, fin)

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

El TAD Cola
• Cola: contenedor de elementos en el que…

5

•

•

la inserción se realiza por un único punto: rear / tail / fin
la extracción se realiza por un único punto: front / head / inicio

1. Cola Vacía

rear

4. Sale Alice

rear

front

3. Entra Bob (B)

rear

front

6. Sale Bob

C

B

rear

front

B

A

C

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

front

front



2. Entra Alice (A)



rear

A



rear



5. Entra Charlie (C)

B

front

El TAD Cola
• Diferencias entre los TAD Pila y Cola

6

• Pila tiene un único punto de entrada y salida; Cola tiene dos
• Pila es LIFO (Last In, First Out); Cola es FIFO (First In, First Out)

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

El TAD Cola
• Colas en el mundo real: para pagar en comercios, comprar

7

tickets para un espectáculo, sacar dinero de un cajero, …
• Una cola gestiona un acceso concurrente a un único recurso

• En Informática existen muchos ejemplos de uso de colas

• Trabajos enviados a impresoras

‐ El primer trabajo en llegar es el primero que se imprime: First Come, First

Served (FCFS)

• Peticiones a servidores
• Uso del procesador

‐ Un sistema operativo realiza planificaciones de procesos de distintos

tipos, gestionando el orden de ejecución de los mismos

• ¡OJO! No todos los elementos tienen que tener siempre

la misma prioridad para ser procesados



 colas de prioridad (tema 6)

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

8

• El TAD Cola
• Estructura de datos y primitivas de Cola
• Estructura de datos de Cola como array circular
• Implementación en C de Cola

• Implementación con front y rear de tipo entero



• Anexo

• Implementación con front y rear de tipo puntero

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos y primitivas de Cola
• Una cola está formada por:

9

• datos: conjunto de elementos del mismo tipo, ordenados
implícitamente y accesibles desde dos puntos: front y rear

• front: indicador de la posición del próximo elemento a extraer
• rear: indicador de la posición donde colocar el próximo elemento que

se inserte

7

6

5

4

3

2

1

0

x

x

x

x

5

1

(en este dibujo se asume que la cola
tiene tamaño máximo de 8, pero no

tiene por qué ser así)

rear

front

datos

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos y primitivas de Cola

10

• Primitivas

Cola cola_crear(): crea, inicializa y devuelve una cola
cola_liberar(Cola s): libera (la memoria ocupada por) la cola

boolean cola_vacia(Cola s): devuelve true si la cola está vacía y false si no
boolean cola_llena(Cola s): devuelve true si la cola está llena y false si no

status cola_insertar(Cola s, Elemento e): inserta un dato en una cola
Elemento cola_extraer(Cola s): extrae el dato que ocupa el front de la cola

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

11

• El TAD Cola
• Estructura de datos y primitivas de Cola
• Estructura de datos de Cola como array circular
• Implementación en C de Cola

• Implementación con front y rear de tipo entero



• Anexo

• Implementación con front y rear de tipo puntero

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos de Cola como array circular

12



• Ejemplo de ejecución de operaciones en una cola

1) cola_inicializar(q)
2) cola_insertar(q, 5)
3) cola_insertar(q, 3)
4) cola_extraer(q)
5) cola_extraer(q)
6) cola_insertar(q, 7)


• Problemas

f=r

1)

f

r

2)

5

f

r

3)

5 3

f

r

4)

3

f=r

5)

6)

f r?

7

• Limitación del número máximo de elementos
• Desperdicio de espacio



Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos de Cola como array circular

13

• Soluciones al desperdicio de espacio

1) Cada vez que se extrae un elemento, se desplazan todos los

datos una posición en el array
•

Ineficiente

2) Cuando rear llega al final del array, se desplazan todos los

elementos una posición en el array
•

(menos) Ineficiente

3) Implementación de la cola como un array circular

• Más eficiente

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos de Cola como array circular

14

• Cola circular

0 1

2

3

…

N-1



N-1

0

…

1

2

3

…

• ¿Cómo implementarla?

• Incrementando front y rear módulo COLA_MAX

front = (front+1) % COLA_MAX

rear = (rear+1) % COLA_MAX


• Problema vigente

• Limitación del número máximo de elementos

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos de Cola como array circular
• Ejemplo de ejecución de operaciones

15

1) cola_inicializar(q)
2) cola_insertar(q, 5)
3) cola_insertar(q, 3)
4) cola_extraer(q, e)
5) cola_extraer(q, e)
6) cola_insertar(q, 7)
7) cola_insertar(q, 2)
8) cola_insertar(q, 1)


f=r

f=r

1)

vacía

5)

vacía

f

r

2)

5

r

6)

f

7

f

r

r

f

3)

5 3

7)

2

7

llena

f

r

f=r

4)

3

8)

2 1 7

¿vacía?
¿llena?

• Conflicto cola llena/vacía

front == rear  ¿Cola vacía o llena?

•
• Solución: sacrificar un hueco libre en el array

‐ Prohibir la inserción cuando sólo queda un hueco
‐ 7) es cola llena
‐ Una cola tiene espacio para (COLA_MAX -1) elementos

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

16

• El TAD Cola
• Estructura de datos y primitivas de Cola
• Estructura de datos de Cola como array circular
• Implementación en C de Cola

• Implementación con front y rear de tipo entero



• Anexo

• Implementación con front y rear de tipo puntero

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos y primitivas de Cola
• EdD en C

17

• datos: en este tema será un array de punteros: Elemento *datos[];
• front, rear: en este tema se declarará de 2 maneras (versiones) distintas

• Como enteros: int front, rear;
• Como punteros a elemento del array: Elemento **front, **rear;

7

6

5

4

3

2

1

0

5

1

x

x

x

x

7

6

5

4

3

2

1

0

x

x

x

x

rear

front

datos

Versión 1



rear


front

datos

Versión 2

Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C de Cola

18

• Implementación con front y rear de tipo entero

• Se asume la existencia del TAD Elemento
• EdD de Cola mediante un array


// En cola.h
typedef struct _Cola Cola;


// En cola.c

#define COLA_MAX 8

struct _Cola {

Elemento *datos[COLA_MAX];

int front; // Primer elemento

int rear; // Primer hueco tras
// el último elemento

5

rear

1

7

6

5

4

3

2

1

0

x

x

x

x

};

front

datos



Programación II – Tema 3: Colas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C de Cola
• Implementación con front y rear de tipo entero

• Asumimos la existencia del TAD Elemento que, entre otras,

tiene asociadas las primitivas liberar y copiar:
void elemento_liberar(Elemento *pe);

Elemento *elemento_copiar(const Elemento *pe);

• Primitivas (prototipos en cola.h)

Cola *cola_crear();

void cola_liberar(Cola *pq);

boolean cola_vacia(const Cola *pq);

boolean cola_llena(const Cola *pq);

status cola_insertar(Cola *pq, const Elemento *pe);

Elemento *cola_extraer(Cola *pq);
• Estructura de datos (en cola.c)

struct _Cola {

Elemento *datos[COLA_MAX];

int front;

int rear

};

Programación II – Tema 3: Colas

Escuela Politécnica Superior