En informática , una cola es una colección de entidades que se mantienen en una secuencia y se pueden modificar mediante la adición de entidades en un extremo de la secuencia y la eliminación de entidades del otro extremo de la secuencia. Por convención, el final de la secuencia en el que se agregan elementos se denomina parte posterior, cola o parte trasera de la cola, y el extremo en el que se eliminan elementos se denomina cabeza o frente de la cola, de manera análoga a las palabras que se utilizan cuando las personas hacen fila para esperar bienes o servicios.
La operación de añadir un elemento al final de la cola se conoce como enqueue , y la operación de eliminar un elemento del frente se conoce como dequeue . También se pueden permitir otras operaciones, que a menudo incluyen una operación de peek o front que devuelve el valor del siguiente elemento que se va a sacar de la cola sin sacarlo de la cola.
Las operaciones de una cola la convierten en una estructura de datos FIFO (primero en entrar, primero en salir) . En una estructura de datos FIFO, el primer elemento añadido a la cola será el primero en eliminarse. Esto es equivalente al requisito de que una vez que se añade un nuevo elemento, todos los elementos que se añadieron antes tienen que eliminarse antes de que se pueda eliminar el nuevo elemento. Una cola es un ejemplo de una estructura de datos lineal , o de forma más abstracta, una colección secuencial. Las colas son comunes en los programas informáticos, donde se implementan como estructuras de datos acopladas a rutinas de acceso, como una estructura de datos abstracta o en lenguajes orientados a objetos como clases.
Una cola tiene dos extremos: el extremo superior, que es la única posición en la que se puede realizar la operación de inserción, y el extremo inferior, que es la única posición en la que se puede realizar la operación de extracción. Una cola se puede implementar como búferes circulares y listas enlazadas , o utilizando tanto el puntero de pila como el puntero de base.
Las colas proporcionan servicios en informática , transporte e investigación de operaciones , donde se almacenan y guardan diversas entidades, como datos, objetos, personas o eventos, para su posterior procesamiento. En estos contextos, la cola cumple la función de búfer . Otro uso de las colas es la implementación de búsquedas en amplitud .
En teoría, una característica de una cola es que no tiene una capacidad específica. Independientemente de cuántos elementos ya contenga, siempre se puede añadir un nuevo elemento. También puede estar vacía, en cuyo caso será imposible eliminar un elemento hasta que se haya añadido de nuevo un nuevo elemento.
Las matrices de longitud fija tienen una capacidad limitada, pero no es cierto que los elementos deban copiarse hacia la parte superior de la cola. El simple truco de convertir la matriz en un círculo cerrado y dejar que la cabeza y la cola se desplacen sin fin en ese círculo hace innecesario mover nunca los elementos almacenados en la matriz. Si n es el tamaño de la matriz, entonces calcular los índices módulo n convertirá la matriz en un círculo. Esta sigue siendo la forma conceptualmente más sencilla de construir una cola en un lenguaje de alto nivel , pero hay que admitir que ralentiza un poco las cosas, porque los índices de la matriz deben compararse con cero y el tamaño de la matriz, que es comparable al tiempo que se tarda en comprobar si un índice de matriz está fuera de los límites, lo que hacen algunos lenguajes, pero este será sin duda el método de elección para una implementación rápida y sucia, o para cualquier lenguaje de alto nivel que no tenga sintaxis de puntero. El tamaño de la matriz debe declararse con antelación, pero algunas implementaciones simplemente duplican el tamaño de la matriz declarada cuando se produce un desbordamiento. La mayoría de los lenguajes modernos con objetos o punteros pueden implementar o venir con bibliotecas para listas dinámicas. Es posible que estas estructuras de datos no hayan especificado un límite de capacidad fijo además de las restricciones de memoria. El desbordamiento de la cola se produce cuando se intenta agregar un elemento a una cola llena y el desbordamiento de la cola ocurre cuando se intenta eliminar un elemento de una cola vacía.
Una cola delimitada es una cola limitada a un número fijo de elementos. [1]
Existen varias implementaciones eficientes de colas FIFO. Una implementación eficiente es aquella que puede realizar las operaciones (entrada y salida de cola) en tiempo O(1) .
Las colas pueden implementarse como un tipo de datos independiente, o tal vez considerarse un caso especial de una cola de doble extremo (deque) y no implementarse por separado. Por ejemplo, Perl y Ruby permiten insertar y extraer datos de una matriz desde ambos extremos, por lo que se pueden utilizar las funciones push y shift para poner y sacar datos de una lista en cola (o, a la inversa, se pueden utilizar unshift y pop ), [2] aunque en algunos casos estas operaciones no son eficientes.
La biblioteca de plantillas estándar de C++ ofrece una queueclase con plantilla " " que está restringida únicamente a operaciones push/pop. Desde J2SE5.0, la biblioteca de Java contiene una Queueinterfaz que especifica operaciones de cola; las clases implementadoras incluyen LinkedListy (desde J2SE 1.6) ArrayDeque. PHP tiene una clase SplQueue y bibliotecas de terceros como beanstalk'd y Gearman .
Una cola simple implementada en JavaScript :
clase Cola { constructor () { this.items = [ ] ; } enqueue ( elemento ) { this.items.push ( elemento ) ; } dequeue () { devolver este .items .shift ( ) ; } } Las colas también se pueden implementar como una estructura de datos puramente funcional . [3] Hay dos implementaciones. La primera solo logra por operación en promedio . Es decir, el tiempo amortizado es , pero las operaciones individuales pueden tomar donde n es el número de elementos en la cola. La segunda implementación se llama cola en tiempo real [4] y permite que la cola sea persistente con operaciones en O(1) tiempo de peor caso. Es una implementación más compleja y requiere listas perezosas con memorización .
Los datos de esta cola se almacenan en dos listas enlazadas simples llamadas y . La lista contiene la parte delantera de la cola. La lista contiene los elementos restantes (es decir, la parte trasera de la cola) en orden inverso . Es fácil insertar en la parte delantera de la cola añadiendo un nodo en la cabecera de . Y, si no está vacío, es fácil quitarlo del final de la cola quitando el nodo en la cabecera de . Cuando está vacío, la lista se invierte y se asigna a y luego se quita la cabecera de .
La inserción ("enqueue") siempre lleva tiempo. La eliminación ("dequeue") lleva tiempo cuando la lista no está vacía. Cuando está vacía, la operación inversa lleva donde es el número de elementos en . Pero, podemos decir que es tiempo amortizado , porque cada elemento en tuvo que ser insertado y podemos asignar un costo constante para cada elemento en la operación inversa a cuando fue insertado.
La cola en tiempo real logra tiempo para todas las operaciones, sin amortización. Esta discusión será técnica, por lo que recordemos que, para una lista, denota su longitud, que NIL representa una lista vacía y representa la lista cuya cabeza es h y cuya cola es t .
La estructura de datos utilizada para implementar nuestras colas consiste en tres listas enlazadas simples donde f es el frente de la cola y r es el final de la cola en orden inverso. El invariante de la estructura es que s es el final de f sin sus primeros elementos, es decir . La cola de la cola es entonces casi y la inserción de un elemento x a es casi . Se dice casi, porque en ambos resultados, . Luego se debe llamar a una función auxiliar para que se satisfaga el invariante. Se deben considerar dos casos, dependiendo de si es la lista vacía, en cuyo caso , o no. La definición formal es y donde es f seguido de r invertido.
Llamemos a la función que devuelve f seguida de r invertida. Supongamos además que , ya que es el caso cuando se llama a esta función. Más precisamente, definimos una función perezosa que toma como entrada tres listas tales que , y devuelve la concatenación de f , de r invertida y de a . Entonces . La definición inductiva de rotate es y . Su tiempo de ejecución es , pero, dado que se utiliza la evaluación perezosa, el cálculo se retrasa hasta que los resultados son forzados por el cálculo.
La lista s en la estructura de datos tiene dos propósitos. Esta lista sirve como un contador para , de hecho, si y solo si s es la lista vacía. Este contador nos permite asegurar que la lista posterior nunca sea más larga que la lista frontal. Además, usar s , que es una cola de f , fuerza el cálculo de una parte de la lista (perezosa) f durante cada operación de cola e inserción . Por lo tanto, cuando , la lista f es totalmente forzada. Si no fuera el caso, la representación interna de f podría ser algún append de append de... de append, y el forzado ya no sería una operación de tiempo constante.
Este artículo incorpora material de dominio público de Paul E. Black. "Cola limitada". Diccionario de algoritmos y estructuras de datos . NIST .
