Colas

7.
C
O
L
A
S

## Introducción.

Las estructuras de datos son una colección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos. Debido a que por lo general tenemos que tratar con conjuntos de datos y no con datos simples (enteros, reales, booleanos, etc.) que por sí solos no nos dicen nada, ni nos sirven de mucho, es necesario tratar con estructuras de datos adecuadas a cada necesidad.
Dentro de las estructuras de datos existen las colas que son una forma de ordenamiento en sistema FIFO que significa que el primer dato que entre es el primer dato que sale, este sistema se ve muy típico en una sociedad ya que es similar al sistema de fila (cola) de las tortillas, del banco, del cine y por lo tanto es bastante familiar para nosotros, una característica de este sistema es que al entrar y salir no se saturan los datos porque así como entra puede ya salir o esperar al siguiente dato.

## RESUMEN

### ¿Qué es una Cola?

Es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción PUSH se realiza por un extremo, y la operación de extracción POP por el otro lado. También es una estructura FIFO, es decir, el primero en llegar siempre será el primero en salir.

### Características:

- Se realizan las inserciones al final de las listas, no al principio.
- Se usan para almacenar datos que necesitan ser procesados según el orden de llegada.

### Uso:

Los datos se almacenan y guardan mediante colas para su posterior procesamiento.
Se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

### Ejemplos:

- Personas esperando en la fila de un supermercado.
- Gente esperando entrar al cine.
- La fila en los bancos para pagar o hacer un movimiento bancario.

### Aplicaciones:

Se utiliza de muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora.

### Tipos de colas:

- Cola simple: Estructura lineal dónde los elementos salen en el mismo orden en que llegan
- Cola circular: Estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor.
- Cola de prioridades: Tipo de dato abstracto similar a una cola en la que los elementos tienen adicionalmente, una prioridad asignada.
- Bi cola: Tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola.
- Bi colas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio o al final.
- Bi colas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

### Cola de prioridades (Operaciones)

- Una cola de prioridad soporta al menos 2 de estas operaciones:
- Añadir con prioridad: Se añade un elemento a la cola, con su correspondiente prioridad.
- Eliminar elemento de mayor prioridad: Se devuelve y elimina el elemento con mayor prioridad más antiguo que no haya sido desencolado de la cola.

### Operaciones de cola:

- Acceder al primer elemento de la Cola
- Añadir un elemento al final de la Cola
- Eliminar el primer elemento de la Cola
- Vaciar una Cola
- Verificar el estado de la Cola: vacía, Llena.

### Sintaxis:

- Función (Indica si la cola está vacía, si va a añadir un elemento, etc.)
- Entrada (Cola a comprobar, cola a inicializar, nuevo elemento a cola)
- Precondiciones (Hay espacio, no está vacía, Ninguna)
- Salida (Cola inicializada, cola llena, cola vacía, cola nueva)
- Post condiciones (Cola está vacía, cola está llena, cola original con nuevo elemento)

## Operadores: - Cola vacía.
- Consultar el frente.
- Consultar el final.
- Meter.
- Sacar.
- Vaciar Cola.
- Eliminación de elementos.
Una operación muy útil es ver si la cola está vacía. Cola Vacía (Cola) devuelve True si la Cola está vacía y False en los demás casos. Ponemos SupCola cuando la cola no está vacía. Teóricamente ponemos siempre InsCola, porque en principio, una cola no tiene un tamaño limitado.
Las colas pueden necesitar cantidad de memoria sobre todo si se diseña con un gran número de elementos. Para evitar este desperdicio de memoria, existe un procedimiento para diseñar las colas mediante una lista circular.
Q (1), Q (2), …, Q(n). De tal forma que el elemento Q (1), quede a continuación de Q (n)

## Estructura de Datos: Colas

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. Es un grupo ordenado de elementos homogéneos en el que los nuevos elementos se añaden por un extremo (el final) y se quitan por el otro extremo (el frente). En las colas el elemento que entró primero sale también primero, por ello se las llama como listas FIFO (first in, first out) "primero en entrar, primero en salir".
La diferencia con las pilas es en el modo de entrada / salida de datos; en las colas se realizan las inserciones al final de la lista, no al principio. Por eso, se usan para almacenar datos que necesitan ser procesados según el orden de llegada.
C= C (1), C (2), ......., C (N)
Las eliminaciones se realizan al principio de la lista frente (front), y las inserciones se realizan en el otro extremo final (rear).

## Aplicaciones de las Colas

Las Colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).
Si se está trabajando en un sistema multiusuario, cuando se le dice a la computadora que ejecute un programa concreto, el sistema operativo añade la petición a la "cola de trabajo". Cuando la petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada/salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.

### Las operaciones que se pueden realizar con una cola son:

- Acceder al primer elemento de la Cola
- Añadir un elemento al final de la Cola
- Eliminar el primer elemento de la Cola
- Vaciar una Cola
- Verificar el estado de la Cola: vacía, Llena.
La característica de las colas es que tienen una capacidad específica. Por muchos elementos que contengan siempre se puede añadir un elemento más y en caso de estar vacía borrar un elemento sería imposible hasta que no se añade un nuevo elemento. A la hora de añadir un elemento podríamos darles una mayor importancia a unos elementos que a otros (un cargo VIP) y para ello se crea un tipo de cola especial que es la cola de prioridad.

## Operaciones Básicas

1. Crear: se crea la cola vacía.
2. Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
3. Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
4. Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

## Colas en JAVA

public void inserta(Elemento x) {
Nodo Nuevo;
Nuevo = new Nodo(x, null);
if (NodoCabeza == null) {
NodoCabeza = Nuevo;
} else {
NodoFinal.Siguiente = Nuevo;
}
NodoFinal = Nuevo;
}
public Elemento cabeza() throws IllegalArgumentException {
if (NodoCabeza == null) {
throw new IllegalArgumentException();
} else {
return NodoCabeza.Info;
}
} public Cola() {
// Devuelve una Cola vacía
NodoCabeza = null;
NodoFinal = null;}

## CONCLUSIÓN

El uso de las estructuras de datos, como por ejemplo las colas en este caso, son muy importantes, ya que podemos llevar un orden de archivos o programas en un computador, lo cual le facilita las tareas a las PC’s y ayuda a crear una eficiencia en la memoria, y para el usuario o programador es más fácil el manejo de los sistemas o programas. Las colas o el uso de las mismas lo podemos ver en la vida cotidiana, en ejemplos tan simples como: en la fila para comprar pan o tortillas, el primero que llega a la panadería o la tortillería, es el primero en recibir sus artículos, y obviamente, el primero en salir o irse de ese lugar, de esta forma o de igual manera funcionan las colas en los sistemas operativos en programación, el primer archivo o programa en ejecutarse, es el primero en abrir y en terminar su función o tarea a realizar. Por lo tanto, es muy útil saber utilizar cada una de las estructuras de datos indicadas para cada caso.

## Bibliografía:

• https://www.ecured.cu/Cola_(Estructura_de_datos)
• http://estructura-de-datos-garo.blogspot.mx/2011/10/colas-informatica.html
• https://upload.wikimedia.org/wikipedia/commons/5/51/APUNTES.pdf
• https://es.slideshare.net/arrietaevelio/pilas-y-colas-26803229
• Nota: Las imágenes fueron obtenidas de las mismas páginas que la información.

## Complementos

Estructuras de datos – 5. Colas