03/10/2025
COLAS
ESD115
• Definición
• Operaciones
básicas de colas.
• Implementación
Contenido de colas.
• Áreas de
aplicación
1
03/10/2025
Objetivos
Conocer y aplicar la organización de datos
que utilizan las colas y las formas de
almacenamiento.
Definición
• Una cola es un conjunto ordenado
de elementos del que pueden
suprimirse elementos de un
• Una cola es un concepto común en la extremo (llamado la parte
vida cotidiana hacemos cola cuando: delantera de la cola) y en el que
vamos al cine, para comprar las pueden insertarse elementos del
entradas, estamos en el otro extremo (llamado la parte
supermercado, en el banco, etc. posterior de la cola).
2
03/10/2025
COLAS
• Una cola es una estructura de datos lineal que
sigue el principio FIFO (First In, First Out), es
decir, el primer elemento en entrar es el
primero en salir. Las operaciones principales
que se realizan sobre una cola son enqueue
(inserción al final) y dequeue (eliminación
desde el frente). Las colas se utilizan
comúnmente en escenarios donde se requiere
un orden secuencial en el procesamiento de
elementos, como en la gestión de procesos o
en sistemas de impresión.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
Introduction to Algorithms (3rd ed.). The MIT Press..
Funcionamiento
Política de la cola:
• El primero en llegar,
tiene la seguridad de
Todo el que sale, lo hace
que será el primero
por el frente de la cola.
en salir: (FIRST IN ,
Todo el que llega se FIRST OUT o FIFO)
ubica al final de la cola.
Se puede decir que la
cola tiene 2 extremos,
FRENTE, Y FINAL.
3
03/10/2025
1 Dinámica
2 Estructura lineal
3 Ordenada
Características 4 Política FIFO
Ejemplo
La impresión de documentos desde una o varias computadoras,
cada solicitud de impresión se coloca en una cola de impresión.
Esta cola asegura que los documentos se impriman en el orden
en que fueron enviados (FIFO: FirstIn, FirstOut)
4
03/10/2025
Operaciones
insert( q, x ) x = remove( q ) empty( q )
Suprime el Retorna false o
Inserta el
elemento true,
elemento x en
delantero de la dependiendo si
la parte
cola q y la cola contiene
posterior de la
establece su elementos o
cola q.
contenido en x. no.
Insert( q, x ) puede ejecutarse siempre,
pues no hay límite en la cantidad de
elementos que puede contener una cola.
Consideraciones
Remove (q) sólo puede aplicarse si la cola
no está vacía.
El resultado de un intento no válido de
remover un elemento de una cola vacía
se denomina subdesbordamiento.
5
03/10/2025
Implementación
Es posible En muchas ocasiones
implementar una se necesitan
estructura de datos estructuras que
cola empleando puedan cambiar de
arreglos lineales o tamaño durante la
Memoria Dinámica
Memoria Estática
circulares. ejecución del
programa. Las
estructuras dinámicas
nos permiten crear
estructuras de datos
que se adapten a las
necesidades reales a
las que suelen
enfrentarse los
programas.
Cola Memoria Estática
• La variable front indica la posición donde 5 7 2 9
inicia la cola, cada vez que se elimina un
elemento del frente. 0 front
3 rear
• La variable rear indica la posición final de la
cola, y tiene un valor de cambio de +1 al
insertarse un nuevo elemento a la estructura.
Struct queue{
int items[n];
int front;
int rear;
6
03/10/2025
Representación de una Cola con Memoria Estatica
Cola La cola lineal es un tipo de
Lineal almacenamiento creado por el usuario
que trabaja bajo la técnica FIFO. Las
colas lineales se representan
gráficamente como se muestra en la
figura:
Cola Esta estructura permite volver al
Circular: comienzo del array cuando se llegue al
final, ya sea el índice de entrada o el
índice de salida. Su representación
gráfica se muestra en la figura:
Diferencias
Cola Lineal Cola Circular
• Inicialización: Al principio se establece q.rear • Inicialización: q.front=q.rear =maxq-1;
en –1 y q.front en 0. La cola esta vacía cada Adviértase que q.front y q.rear son
vez que q.rear < q.front. inicializadas como el último índice del arreglo
• Número de elementos: La cantidad de y no como –1 ó 0, porque el último elemento
elementos en la cola en cualquier momento del arreglo precede de inmediato al primero
es igual al valor de q.rear – q.front + 1. dentro de la cola de esta representación.
• Uso de memoria ineficiente: Requiere del Debido a que q.rear es igual a q.front; al inicio
desplazamiento de datos. la cola está vacía.
• Uso de memoria: Mejora el uso de memoria,
sacrifica un elemento o casilla.
7
03/10/2025
Trasladar un elemento a una estación de servicio
especifico.
Lógica de negocio Deshabilitar el servidor.
aplicada a estructuras
de cola
Dividir una cola (En que momento
política del negocio). Contabilizar el numero de clientes atendidos.
Calcular el tiempo promedio de permanencia en cola.
Lógica de negocio Cantidad de clientes de un determinado tipo.
aplicada a estructuras de
cola
8
03/10/2025
Tipos de Colas
Colas de Prioridad
Es una estructura de datos en la que el Bicolas
ordenamiento intrínseco de los elementos determina
los resultados de sus operaciones básicas. Los nodos se pueden añadir y quitar por ambos
Ascendente: extremos; se les llama DEQUE (Double Ended
QUEue). Para representar las bicolas lo podemos
• Es una colección de elementos en las que se hacer con un array circular con Ini y Fin que apunten
pueden insertar elementos de manera arbitraria y a cada uno de los extremos. Variantes :
de las que se pueden eliminarse sólo el elemento
menor. Bicolas de entrada restringida :
Descendente: • La inserción sólo se hace por el final, aunque
podemos eliminar al principio ó al final.
• Sólo permite la eliminación del elemento mayor.
Las operaciones aplicables a una cola de este tipo, Bicolas de salida restringida :
dpq, son: pqinsert(dpq, x) y pqmaxdelete(dpq). • La eliminación sólo se hace por el final, aunque se
puede insertar al principio y al final.
Implementación Cola
Memoria Estática
Main
#define maxq 5
struct queue
{ //Declaracion de la cola
int items[maxq]; struct queue q;
int front;
int rear; /* data */
};
9
03/10/2025
void insert(struct queue *pq, int x) {
if (pq->rear == maxq - 1) {
printf("Desbordamiento: la cola está llena\n");
exit(1);
}
Colas Estáticas
pq->rear++;
No Circular pq->items[pq->rear] = x;
Insertar }
int remove(struct queue *pq) {
if (empty(pq)) {
printf("La cola está vacía\n");
exit(1);
}
Colas Estáticas
pq->front++;
No Circular
return pq->items[pq->front];
Remover }
10
03/10/2025
• Empty: Verifica si la cola esta vacía
• Full: Verifica si la cola esta llena
Ejercicio • Mostrar: Imprima los elementos de la
cola sin removerlos
Desarrollar las funciones
Ejemplo
Codificación C/C++
11
03/10/2025
void insert(struct queue *pq, int x)
{
/* hace espacio para un nuevo elemento */
if ( pq->rear==maxq-1)
pq->rear=0;
else
( pq->rear )++;
/*comprueba que no hay desbordamiento*/
Colas Estáticas if ( pq->rear==pq->front ){
printf ("desbordamiento en la cola");
exit(1);
Circular
}/* fin de if */
Insertar pq->items[pq->rear]=x;
return;
}
int remove (struct queue *pq)
{
if (empty(pq) ) {
printf ("la cola está vacía");
exit(1);
} /*fin de if*/
if (pq->front ==maxq-1)
pq->front=0;
Colas Estáticas else
(pq->front)++;
return (pq->items[pq->front]);
Circular
}
Remover
12
03/10/2025
• Empty: Verifica si la cola esta vacía
• Full: Verifica si la cola esta llena
Ejercicio • Mostrar: Imprima los elementos de la
cola sin removerlos
Desarrollar las funciones
Gracias
13
