La cola tiene una estructura similar a la pila, pero con una difirencia concectual importante: el paradigma por tras de la cola es el FIFO - First In, First Out, o "el primero en entrar es el primero en salir", en traducción libre.
Piense en una cola para comprar boletos, por ejemplo. La persona que llegó primero será atendida (y comprará su boleto) antes de aquellas que llegaron más tarde y se quedaron atrás en la fila. La cola como estructura de datos sigue el mismo principio.
Por lo tanto, también hay solo dos formas de manipular una cola:
- Insertar un elemento al final de la cola
- Remover un elemento del inicio de la cola
Deque
La estructura de datos deque (abreviación de double-ended queue o "cola de dos puntos") es una variación de la cola que acepta la inserción y eliminación de elementos tanto del principio como del final de la cola.
Podemos comparar, nuevamente, con una cola de personas en un mostrador de servicio: primero se atiende a una persona mayor que llega (o sea, no puede ser colocada en el final de la cola), al mismo tiempo que una persona que entro en el final de la cola puede desistir de esperar y irse (en este caso, no puedes esperar la persona llegar al frente de la cola para luego quitarla).
Otra forma de entender la estructura deque es como una unión de estructuras de pila y cola.
Cola circular
Otra variación de cola es la cola circular (circular queue) , donde el ultimo elemento es conectado con el primer elemento - como en el circulo:
La cola circular busca resolver una limitación de cola lineal, que es lidear con espacios vazios que pueden hacer cola despues de quitar elementos del inicio de la cola.
Usos
Un uso fácil de recordar para la cola es simplemente la cola de impresión de los sistemas operativos: el último trabajo de impresión que se agregará a la cola será el último en imprimirse.
Además, las solicitudes que se hacen a un servidor también se organizan en una cola para ser respondidas, y cuando cambiamos de programa usando el atajo alt+tab, el sistema operativo gestiona el pedido utilizando el principio de lista circular.