Universidad Autónoma de Madrid
Escuela Politécnica Superior
Tipos Abstractos de Datos
TAD Cola
Departamento de Ingeniería Informática
Escuela Politécnica Superior
Universidad Autónoma de Madrid 1
TAD Cola. Definición
• Conjunto Homogéneo de datos ordenados implícitamente con la
particularidad de que a los datos se accede por dos puntos
• Para la inserción, un único punto: rear ≡ fin ≡ tail
• Indica la posición en la que se debe insertar el siguiente elemento que llegue a la
cola (se inserta al final)
• Para la extracción, por un único punto: front ≡ inicio ≡ head
• Indica la posición ocupada por el primer elemento de la cola, el que se debe
extraer cuando se extraiga de la misma (se extrae del inicio)
• Acceso FIFO (First In First Out): El primero en entrar es el primero en
salir. Similar a una cola de personas
2
TAD Cola. Visualización
rear
1) Cola Vacía front 4) Manuel sale
rear front
Caja Caja
2) Llega Manuel (M) 5) Llega Pedro (P)
rear front rear front
Caja Caja
P S
M
3) Llega Sandra (S) 6) Sandra sale(S)
rear front rear front
Caja Caja
S M P
3
TAD Cola. Ejemplos
• Colas en el mundo real: pan, cine, cajero, impresora, etc.
• La cola gestiona un acceso concurrente a un único recurso
• Cola de impresión
- Primer trabajo en llegar es el primero que se imprime: First Come, First
Served (FCFS)
• Acceso a la CPU
- En procesadores y Sistemas Operativos (SO) antiguos se hacía un
procesamiento secuencial de los programas
- Cada programa a ejecutar se pone en la cola de ejecución y se
procesaba en orden
- Actualmente las CPUs y los SO son multitarea y multiusuario
- OJO, no todos los procesos son igual de importantes. Existen las colas
de prioridad
4
TAD Cola. Métodos de implementación
• q = queue(): Inicializa una cola q
• emptyQ(q): Comprueba si una cola q está vacía
• frontQ(q): Devuelve el elemento en el front de q
• enqueue(q, data): Inserta el dato data en la posición rear de la cola q
• dequeue(q): Extrae el elemento que ocupa la posición front de la cola q
5
TAD Cola. Definición como array estático
Ejemplo de definición en C
#define MAX_SIZE 256
typedef <tipo_dato> generic;
typedef struct {
generic datos[MAX_SIZE];
rear int front; // primer elemento
int rear; // último elemento
front } Cola;
datos
6
TAD Cola. Definición como array estático
• Ejemplo de ejecución de operaciones en una cola
1)colaIni(q) f=r f r
2)colaInsertar(5) 1) 4) 3
3)colaInsertar(3) r f=r
f
4)colaExtraer()
2) 5 5)
5)colaExtraer()
6)colaInsertar(7) f r f r?
3) 5 3 6) 7
• Problemas:
• Limitación del número máximo de elementos
• Desperdicio de espacio
7
TAD Cola. Definición como array estático
• 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
8
TAD Cola. Definición como array circular
N-1 0
• Cola circular … 1
2
0 1 2 3 … N-1
3
…
• ¿Cómo implementarla?
• Incrementando front y rear con una operación modular MAX_SIZE
front = (front+1) % MAX_SIZE
rear = (rear+1) % MAX_SIZE
• Problema vigente
• Limitación del número máximo de elementos
9
TAD Cola. Definición como array circular
• Ejemplo de ejecución de operaciones f=r f=r
1) colaIni()
2) colaInsertar(5) 1) vacía 5) vacía
3) colaInsertar(3) f r r f
4) colaExtraer()
5) colaExtraer() 2) 5 6) 7
6) colaInsertar(7)
7) colaInsertar(2) f r r f
8) colaInsertar(1) 3) 5 3 7) 2 7 llena
f r f=r
• Conflicto cola llena/vacía ¿vacía?
• front == rear ¿Cola vacía o llena? 4) 3 8) 2 1 7 ¿llena?
• Solución: sacrificar un hueco libre en el array
• Prohibir la inserción cuando sólo queda un hueco
• El evento (7) ya es cola llena
• Una cola circular tiene espacio para (MAX_SIZE -1) elementos
Y en Python …
10
TAD Cola. Implementación I
• Podemos implementar una Cola en Python mediante dos vías
A. Definiendo la clase con sus funciones primitivas (manejan directamente los objetos)
• La memoria es dinámica. No hay limitación estática de espacio
# A constructor
class queue():
def __init__(self):
[Link] = None
[Link] = None
[Link] = 0
11
TAD Cola. Implementación II
B. Definiendo la clase como subclase de la clase Lista Enlazada Simple
12