Informa

Ricardo Ferrís Castell

Algoritmos y Estructuras de Datos I

12. COLAS
12.0 INTRODUCCIÓN .....................................................................................................................................................41
12.1 FUNDAMENTOS.....................................................................................................................................................41
12.2. REPRESENTACIÓN DE LAS COLAS EN C++............................................................................................................42
Implementación mediante estructuras estáticas: Colas lineales .............................................................................45
Implementación mediante estructuras estáticas: Colas circulares.........................................................................49
Implementación mediante estructuras dinámicas: Colas enlazadas .......................................................................51

12.0 Introducción
En este tema veremos las estructuras de datos lineales colas, su significado y las operaciones más
habituales sobre ellas, así como algunas posibles implementaciones con estructurasestáticas y
dinámicas en C++.

12.1 Fundamentos
Las colas son secuencias de elementos caracterizadas porque las operaciones de inserción y borrado
se realizan sobre extremos opuestos de la secuencia. La inserción se produce en el "final" de la
secuencia, mientras que el borrado se realiza en el otro extremo, el "inicio" de la secuencia.
Las restricciones definidas para una cola hacen que elprimer elemento que se inserta en ella sea,
igualmente, el primero en ser extraido de la estructura. Si una serie de elementos A, B, C, D, E se
insertan en una cola en ese mismo orden, entonces los elementos irán saliendo de la cola en el
ordenen que entraron. Por esa razón, en ocasiones, las colas se conocen con el nombre de listas o
secuencias FIFO (First In First Out, el primero que entra es elprimero que sale).
Estructura Cola
A
→
Borrado

B

C

D

E

F

...
→
Inserción

Las colas, al igual que las pilas, resultan de aplicación habitual en muchos problemas informáticos.
Quizás la aplicación más común de las colas es la organización de tareas de un ordenador. En
general, los trabajos enviados a un ordenador son "encolados" por éste, para ir procesandosecuencialmente todos los trabajos en el mismo orden en que se reciben. Cuando el ordenador
recibe el encargo de realizar una tarea, ésta es almacenada al final de la cola de trabajos. En el
momento que la tarea que estaba realizando el procesador acaba, éste selecciona la tarea situada al
principio de la cola para ser ejecutada a continuación. Todo esto suponiendo la ausencia de
prioridades en lostrabajos. En caso contrario, existirá una cola para cada prioridad. Del mismo
modo, es necesaria una cola, por ejemplo, a la hora de gestionar eficientemente los trabajos que
deben ser enviados a una impresora (o a casi cualquier dispositvo conectado a un ordenador). De
esta manera, el ordenador controla el envio de trabajos al dispositivo, no enviando un trabajo hasta
que la impresora no terminecon el anterior.
Análogamente a las pilas, es necesario definir el conjunto de operaciones básicas para especificar
adecuadamente una estructura cola. Estas operaciones serían:
Tema 12. Colas

41

Algoritmos y Estructuras de Datos I

Ricardo Ferrís Castell

- Crear una cola vacía.
- Determinar si la cola está vacía, en cuyo caso no es posible eliminar elementos.
- Acceder al elementoinicial de la cola.
- Insertar elementos al final de la cola.
- Eliminar elementos del inicio de la cola.
Al igual que realizamos con las pilas, haremos una declaración un poco más formal de estas
operaciones y los axiomas que las caracterizan:
Estructura
Cola ( Valor )

{* Valor será el tipo de datos que podremos guardar en la cola *}

Operaciones
CREAR_COLA ( ) → Cola
ENCOLAR (...