UNIVERSIDAD NACIONAL DE CHIMBORAZO

Materia: Estructura de
datos
Tema: Colas
Por:
Estefano Iturralde
José Sinaluisa
 CONTENIDOS
Introducción Colas usando arreglos
Definición de colas Colas usando listas
Características enlazadas
generales de las colas Desbordamiento y
Operaciones básicas subdesbordamiento
Ventajas y desventajas Taller en clase
Tipos de colas
 INTRODUCCIÓN
Las colas son una de las estructuras de datos más utilizadas en
programación, ya que permiten organizar y controlar el orden en
el que se atienden datos o procesos. Su funcionamiento se basa en
una idea muy común en la vida cotidiana: la formación de filas,
donde cada elemento espera su turno para ser atendido.
Este tipo de estructura es fundamental en muchos sistemas
informáticos, como la atención al cliente, la gestión de procesos en
un sistema operativo, el uso de impresoras o el manejo de turnos
en hospitales y bancos.
 DEFINICIÓN DE
COLAS

Una cola es una estructura de datos que

organiza elementos de forma ordenada, similar
a una fila de personas. Los elementos se van
agregando al final de la cola y se van retirando
desde el frente, respetando siempre el orden
de llegada. Este funcionamiento se conoce
como FIFO (First In, First Out), lo que significa
que el primer elemento que entra a la cola es
el primero en salir. Gracias a este principio, las
colas permiten un manejo justo y ordenado de
la información.
 CARACTERÍSTICAS GENERALES

Estructura de datos lineal

Las colas organizan los elementos uno detrás de otro, formando una secuencia ordenada, donde cada elemento
ocupa una posición específica.
Orden de atención definido (FIFO)
Las colas funcionan bajo el principio FIFO (First In, First Out), lo que significa que el primer elemento que entra
es el primero en salir, garantizando un orden justo.
Inserción por el final
Los nuevos elementos solo pueden agregarse por el extremo final de la cola, no en posiciones intermedias.
Eliminación por el frente
Los elementos solo pueden retirarse desde el frente de la cola, respetando el orden establecido.
Acceso restringido
No es posible acceder directamente a un elemento intermedio; solo se puede trabajar con el primer y el último
elemento.
Control de cola vacía y cola llena
Es necesario verificar si la cola está vacía antes de eliminar elementos y si está llena antes de insertar, para
evitar errores.
Uso eficiente para procesos secuenciales
Son ideales para manejar procesos que deben ejecutarse en orden, como turnos, impresiones o tareas del sistema.
 OPERACIONES BÁSICAS

Enqueue (Insertar)
Esta operación permite agregar un nuevo elemento al final de la cola.
Siempre que se inserta un elemento, este pasa a ocupar el último lugar y debe esperar su turno para ser
atendido.
Dequeue (Eliminar)
Consiste en retirar el elemento que se encuentra al frente de la cola.
Es la operación contraria a insertar y respeta el orden FIFO, ya que siempre se elimina el elemento más
antiguo.
Front o Peek (Consultar el frente)
Permite ver el primer elemento de la cola sin eliminarlo.
Se usa cuando solo se necesita conocer quién será atendido primero.
IsEmpty (Cola vacía)
Verifica si la cola no contiene ningún elemento.
Esta operación es importante para evitar errores al intentar eliminar datos cuando la cola está vacía.
IsFull (Cola llena)
Determina si la cola ha alcanzado su capacidad máxima, especialmente cuando se implementa con arreglos.
Evita insertar elementos cuando ya no hay espacio disponible.
 VENTAJAS Y DESVENTAJAS
Mantienen el orden de llegada Acceso limitado a los elementos
Las colas procesan los elementos en el No se puede acceder directamente a un
mismo orden en que llegan, lo que permite elemento intermedio, solo al frente y al
un manejo justo y organizado de la final.
información. Poca flexibilidad
Ideales para sistemas de turnos No permiten insertar o eliminar elementos
Son muy útiles cuando se necesita atender en cualquier posición.
procesos o personas por orden, como en Posible desperdicio de memoria
bancos, hospitales o impresoras. Cuando se implementan con arreglos,
Facilitan el control de procesos pueden quedar espacios sin usar si no se
Permiten administrar tareas de manera maneja correctamente.
secuencial, evitando conflictos o desorden Necesitan control de errores
en la ejecución. Es obligatorio verificar si la cola está vacía
Sencillas de entender y usar o llena para evitar fallos en el programa.
Su funcionamiento es intuitivo, ya que se No siempre son la mejor opción
basa en situaciones cotidianas como las En situaciones donde se requiere acceso
filas. rápido a cualquier elemento, otras
Muy usadas en programación real estructuras pueden ser más adecuadas.
Se aplican en sistemas operativos, redes,
simulaciones y atención al cliente.
 TIPOS DE COLAS
COLA COLA DE
CIRCULAR PRIORIDAD
Es una mejora de la cola El orden de atención depende
simple. de la importancia.
Características: Características:
El último espacio se Cada elemento tiene una
conecta con el primero prioridad.
formando un círculo. Los elementos con mayor
Permite reutilizar COLA DOBLE prioridad se atienden
COLA espacios libres, evitando (DEQUE) primero.
SIMPLE desperdicio de memoria. Permite mayor flexibilidad. Si dos elementos tienen la
Es el tipo de cola más Ejemplo: Características: misma prioridad, se respeta
básica y común. Turnos rotativos o un reloj Se puede insertar y eliminar el orden de llegada.
Características: analógico. elementos tanto por el Ejemplo:
Los elementos se frente como por el final. Hospitales, sistemas
insertan por el final y Combina características de operativos.
se eliminan por el colas y pilas.
frente. Ejemplo:
Sigue estrictamente el Historial de navegación, listas
orden de llegada. de reproducción.
Ejemplo:
Una fila de personas en el
banco.
 COLAS CON ARREGLOS

Colas con arreglos

Una cola con arreglos es una forma de implementar una
cola utilizando un arreglo (array) de tamaño fijo para
almacenar los elementos. Para controlar la cola se
utilizan dos índices: frente y final.
¿Cómo funciona?
El frente indica la posición del primer elemento de
la cola.
El final indica la posición donde se insertará el
siguiente elemento.
Al insertar un elemento, el índice final avanza.
Al eliminar un elemento, el índice frente avanza.
De esta manera, los elementos se mantienen ordenados
dentro del arreglo.
 COLAS CON LISTAS
ENLAZADAS

Una cola con listas enlazadas es una forma de

implementar una cola utilizando nodos enlazados
dinámicamente, en lugar de un arreglo de tamaño fijo.
Cada nodo almacena un dato y un enlace al siguiente
nodo de la cola.
¿Cómo funciona?
Cada nodo contiene:
Un dato
Un puntero al siguiente nodo
La cola mantiene dos referencias:
frente: apunta al primer nodo
final: apunta al último nodo
Los elementos se insertan al final y se eliminan
desde el frente.
 DESBORDAMIENTO Y
SUBDESBORDAMIENTO

Desbordamiento (Overflow) Subdesbordamiento (Underflow)

El desbordamiento ocurre cuando se intenta insertar un El subdesbordamiento ocurre cuando se intenta
elemento en una cola que ya está llena. eliminar un elemento de una cola que está vacía.
¿Por qué ocurre? ¿Por qué ocurre?
Cuando la cola tiene un tamaño máximo (por ejemplo,
implementada con arreglos). Cuando no hay elementos en la cola.
Cuando no se verifica si hay espacio disponible antes Cuando no se verifica si la cola está vacía
de insertar. antes de eliminar.
Ejemplo: Ejemplo sencillo:
“Si una cola tiene capacidad para 5 elementos y ya “Si una cola está vacía y se intenta eliminar un
contiene 5, al intentar insertar uno más se produce un elemento, ocurre un subdesbordamiento.”
desbordamiento.” Cómo se evita:
Cómo se evita: Verificando si la cola está vacía (IsEmpty)
Verificando si la cola está llena (IsFull) antes de antes de eliminar.
insertar.
Usando colas dinámicas, como las implementadas con Controlando correctamente el frente y el final
listas enlazadas. de la cola.
 EJERCICIOS DE COLAS SIMPLES

Ingresar n números en una cola y luego mostrar el primero y el ultimo, sin

perder la cola original.
Insertar n números en una cola.
Luego:
Contar cuántos números son pares y cuántos son impares.
Crear dos nuevas colas: una que almacene los números pares y otra que
almacene los números impares
Finalmente, mostrar la cola original y las colas resultantes.
Usando el método size(), determinar el numero mayor de la cola
 EJERCICIOS DE COLAS DOBLES

Elabore un programa en C++ que permita ingresar n números a una cola doble
(deque), eligiendo si cada número se inserta por el inicio o por el final, y
luego muestre todos los elementos de la cola.
Ingresar n números en una cola doble.
Separar positivos y negativos usando cola doble
Los números positivos deben insertarse por el final.
Los números negativos deben insertarse por el frente.
Finalmente, mostrar la cola doble resultante.
 EJERCICIOS DE COLAS DOBLES

Ingresar n números enteros en una cola doble siguiendo estas reglas:

- Si el numero es positivo y par, se inserta por el frente.
- Si el numero es positivo e impar, se inserta por el final.
- Si el numero es negativo o cero, no se inserta, pero se debe contar cuantos
negativos 0 ceros se ingresaron.
Al finalizar:
Mostrar la cola doble resultante.
Mostrar cuantos números negativos se descartaron.
Mostrar cuantos números quedaron en la cola.
 TALLER EN CLASE
En un sistema de atención se
Ingresar n números enteros en una ingresan n números que
cola simple. representan turnos.
A partir de la cola original: Cada turno sigue estas reglas al
[Link] si el tamaño de la ingresar a una cola doble:
cola es par o impar. [Link] el número es múltiplo de 5,
[Link] la mitad de los se inserta por el frente.
elementos de la cola y [Link] el número no es múltiplo de
guardarlos en una cola auxiliar. 5, se inserta por el final.
[Link] los elementos que quedan [Link] el número es negativo, no se
en la cola original: inserta, pero se debe contar
Contar cuántos son pares y cuántos fueron rechazados.
cuántos son impares. Al finalizar:
Determinar el número Mostrar la cola doble
mayor. resultante
[Link] todas las colas Mostrar cuántos turnos fueron
resultantes. rechazados
Mostrar cuántos turnos
quedaron en la cola
 TALLER EN CLASE
Si la cantidad de elementos de la cola es un
número primo, muestre el elemento de mayor
valor utilizando la operación básica top().
Caso contrario, indique un mensaje informando que
la cantidad de elementos no es un número primo.
Pregunta
¿Qué entiende por desbordamiento y
subdesbordamiento en una cola?
 MUCHAS
GRACIAS
Por participar y acompañarnos en esta exposición.