Estructuras de Datos
Colas (Queues)
El tipo de datos abstracto Cola
Implementación con arreglos
Implementación con listas enlazadas
Objetivo
Aprender a usar estructuras de colas de forma eficiente.
2
Estructuras de Datos
Colas (Queues)
El tipo de datos abstracto Cola
Implementación con arreglos
Implementación con listas enlazadas
El TDA Cola (queue)
Una cola es como una línea. Un número finito de objetos, que tienen
el mismo tipo y se ordenan por cuándo fueron añadidos. Cumple el
principio FIFO (first in, first out, primero en entrar, primero en salir).
Operaciones:
• isEmpty(): ¿está la cola vacía (sin elementos)?
• isFull(): ¿está la cola llena (implementación con arrays)?
• enqueue(newEntry): agrega el elemento newEntry al final de la
cola
4
• dequeue(): remueve el elemento al principio de la cola
• peekFront(): consulta el elemento al principio de la cola
Colas (queues) vs. pilas (stacks)
• Stack vs. Queue
• LIFO vs FIFO (first in, first out)
• Especificación del TDA e implementación de colas
• push()/pop() vs. enqueue()/dequeue()
• tiene muchas similitudes con un stack (comportamiento opuesto) 6
Estructuras de Datos
Colas (Queues)
El tipo de datos abstracto Cola
Implementación con arreglos
Implementación con listas enlazadas
Primer intento (implementación ingenua)
Usar dos variables de control y un array con capacidad MAX_QUEUE:
• front guarda el índice del primer elemento de la cola
• back guarda el índice del último elemento de la cola
(a) Implementación ingenua de una cola (b) desplazamiento a la derecha puede
dar la impresión de que la cola está llena 8
Arreglos circulares (una solución elegante)
Truco: use un arreglo circular para insertar y remover de una cola.
La idea de un arreglo circular es que similar a la de un reloj: una vez se llega
a las 12 las manecillas continúan nuevamente a la 1, en un ciclo continuo
7 0
6 1
5 2
4 3
El operador módulo
El operador mod (%) se usa para calcular residuos:
• 1%5 = 1, 2%5 = 2, 5%5 = 0, 8%5 = 3
mod puede usarse para calcular los índices front y back en un arreglo
circular, para evitar comparaciones con la capacidad de la cola
• El final de la cola es:
• back =(front + count - 1) % MAX_QUEUE;
• donde count es el número de ítems en la cola
• Después de remover un elemento el frente de la cola es:
• (front + 1) % MAX_QUEUE;
Ejemplo de cola con arrays
0 /* Codigo en C */
front =
Queue q;
count = 1
0 initialize(q);
enqueue(q, 6);
6
0 1 2 3 4 5
inserte el elemento en (front + count) % MAX_QUEUE
Ejemplo de cola con arrays
front = 0 /* Codigo en C */
Queue q;
count = 5
4
3
2
1 initialize(&q);
enqueue(&q, 6);
6 4 7 3 8 enqueue(&q, 4);
enqueue(&q, 7);
0 1 2 3 4 5
enqueue(&q, 3);
enqueue(&q, 8);
Ejemplo de cola con arrays
front = 1
2
0 /* Codigo en C */
Queue q;
count = 4
3
5 initialize(&q);
enqueue(&q, 6);
6 4 7 3 8 9 enqueue(&q, 4);
enqueue(&q, 7);
0 1 2 3 4 5
enqueue(&q, 3);
enqueue(&q, 8);
haga front = (0 + 1) % 6 = 1 dequeue(&q);//front = 1
haga front = (1 + 1) % 6 = 2 dequeue(&q);//front = 2
enqueue(&q, 9);
Ejemplo de cola con arrays
front = 2 /* Codigo en C */
Queue q;
count = 5
4 initialize(&q);
enqueue(&q, 6);
5 7 3 8 9 enqueue(&q, 4);
enqueue(&q, 7);
0 1 2 3 4 5
enqueue(&q, 3);
enqueue(&q, 8);
dequeue(&q);//front = 1
dequeue(&q);//front = 2
enqueue(&q, 9);
inserte en (front + count) % 6
enqueue(&q, 5);
= (2 + 4) % 6 = 0
Una implementación en C
array_queue.h
15
Una implementación en C
array_queue.c (parte 1/3)
16
Una implementación en C
array_queue.c (parte 2/3)
17
Una implementación en C
array_queue.c (parte 3/3)
18
Estructuras de Datos
Colas (Queues)
El tipo de datos abstracto Cola
Implementación con arreglos
Implementación con listas enlazadas
Colas implementadas con listas enlazadas
Usa una cadena de nodos enlazados, en donde cada nodo apunta al
que le sigue (el último nodo apunta a NULL).
• La cola mantiene punteros al primero y último eslabón de la cadena
Especificación (linked_queue.h)
21
Crear un nuevo nodo
Se define una función auxiliar, que devuelve un puntero al nuevo nodo:
:
Node* createNode(ItemType newEntry);
Ejemplo: crear un nodo con el valor 3: createNode(3);
item next
Node *newNodePtr = malloc(sizeof(Node));
3 node->item = newEntry; /* Toma el valor de 3 */
node->next = 0; /* Puntero nulo */
return newNodePtr; /* Devuelve el nodo */
newNodePtr
22
La operación enqueue (agregar a la cola)
Insertar un nuevo nodo, apuntado por newNodePtr, al final de la
cadena que representa la cola requiere tres cambios a punteros:
1. El puntero nextPtr (siguiente) en el nuevo nodo
2. El puntero nextPtr(siguiente) en el último nodo actual
3. El puntero backPtr en la cola
La adición de un nuevo nodo a una cola vacía es un caso especial, en el
que se debe actualizar también el puntero frontPtr
23
Agregar un ítem a una cola q no vacía
Node *newNodePtr = createNode(3);
24
Agregar un ítem a una cola q no vacía
q->backPtr->next = newNodePtr
25
Agregar un ítem a una cola q no vacía
q->backPtr = newNodePtr
26
Caso especial: agregar a una cola vacía
(a) Antes de enqueue
(b) Después de enqueue:
q->frontPtr = newNodePtr;
q->backPtr = newNodePtr;
27
Implementación: enqueue (agregar a la cola)
28
La operación dequeue (remover del frente)
• Remover del frente (principio) de la cola implica borrar el primer
nodo de la cadena.
• Si la cola contiene más de un ítem, sólo se necesita actualizar el
puntero frontPtr de la cola.
• Remover de una cola con un único elemento es un caso especial en
donde tanto frontPtr como backPtr se convierten en punteros nulos
29
Remover de una cola q con más de 1 ítem
Node *nodeToDeletePtr = q->frontPtr;
30
Remover de una cola q con más de 1 ítem
q->frontPtr = q->frontPtr->next;
31
Remover de una cola q con más de 1 ítem
nodeToDeletePtr ->next = 0;
32
Remover de una cola q con más de 1 ítem
free(nodeToDeletePtr );
33
Implementación: dequeue (quitar de la cola)
34
Implementación de otras operaciones
35
Ejemplo de cola con listas enlazadas
/* Codigo en C */
6 Queue q;
initialize(&q);
enqueue(&q, 6);
frontPtr
backPtr
36
Ejemplo de cola con listas enlazadas
/* Codigo en C */
6 Queue q;
initialize(&q);
enqueue(&q, 6);
frontPtr 4
enqueue(&q, 4);
backPtr
37
Ejemplo de cola con listas enlazadas
/* Codigo en C */
6 Queue q;
initialize(&q);
enqueue(&q, 6);
frontPtr 4
enqueue(&q, 4);
backPtr enqueue(&q, 7);
7
38
Ejemplo de cola con listas enlazadas
/* Codigo en C */
6 Queue q;
initialize(&q);
enqueue(&q, 6);
frontPtr 4
enqueue(&q, 4);
backPtr enqueue(&q, 7);
7 enqueue(&q, 3);
39
Ejemplo de cola con listas enlazadas
/* Codigo en C */
6 Queue q;
initialize(&q);
enqueue(&q, 6);
frontPtr 4
enqueue(&q, 4);
backPtr enqueue(&q, 7);
7 enqueue(&q, 3);
dequeue(&q);
40