En informática , una cola es una colección de entidades que se mantienen en una secuencia y pueden modificarse agregando entidades en un extremo de la secuencia y eliminando entidades del otro extremo de la secuencia. Por convención, el final de la secuencia en la que se agregan elementos se denomina final, cola o final de la cola, y el final en el que se eliminan elementos se denomina cabecera o principio de la cola, de forma análoga a las palabras utilizadas cuando la gente hace fila para esperar bienes o servicios.
La operación de agregar un elemento al final de la cola se conoce como poner en cola , y la operación de eliminar un elemento del frente se conoce como sacar de cola . También se pueden permitir otras operaciones, que a menudo incluyen una operación de vista previa o frontal que devuelve el valor del siguiente elemento que se quitará de la cola sin quitarlo de la cola.
Las operaciones de una cola la convierten en una estructura de datos de primero en entrar, primero en salir (FIFO) . En una estructura de datos FIFO, el primer elemento agregado a la cola será el primero en eliminarse. Esto equivale al requisito de que una vez que se agrega un nuevo elemento, todos los elementos que se agregaron antes deben eliminarse antes de que se pueda eliminar el nuevo elemento. Una cola es un ejemplo de estructura de datos lineal o, de manera más abstracta, una colección secuencial. Las colas son comunes en los programas informáticos, donde se implementan como estructuras de datos junto con rutinas de acceso, como una estructura de datos abstracta o en lenguajes orientados a objetos como clases. Las implementaciones comunes son buffers circulares y listas enlazadas .
Las colas brindan servicios en informática , transporte e investigación de operaciones donde diversas entidades, como datos, objetos, personas o eventos, se almacenan y mantienen para su procesamiento posterior. En estos contextos, la cola realiza la función de un buffer . Otro uso de las colas es en la implementación de la búsqueda en amplitud .
Teóricamente, una característica de una cola es que no tiene una capacidad específica. Independientemente de cuántos elementos ya estén contenidos, siempre se puede agregar un elemento nuevo. También puede estar vacío, momento en el que será imposible eliminar un elemento hasta que se haya agregado nuevamente un nuevo elemento.
Las matrices de longitud fija tienen una capacidad limitada, pero no es cierto que los elementos deban copiarse al principio de la cola. El simple truco de convertir la matriz en un círculo cerrado y dejar que la cabeza y la cola desplacen sin cesar en ese círculo hace que sea innecesario mover 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 es cierto 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 necesario para compruebe si un índice de matriz está fuera de límites, lo que hacen algunos lenguajes, pero este será sin duda el método elegido 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 anticipación, pero algunas implementaciones simplemente duplican el tamaño de la matriz declarado cuando ocurre 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 dichas estructuras de datos no hayan especificado un límite de capacidad fijo además de las limitaciones de memoria. El desbordamiento de la cola se produce al intentar 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 acotada 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 (poner y quitar la cola) en un tiempo O(1) .
Las colas pueden implementarse como un tipo de datos separado, o tal vez considerarse un caso especial de cola de doble extremo (deque) y no implementarse por separado. Por ejemplo, Perl y Ruby permiten empujar y sacar una matriz desde ambos extremos, por lo que se pueden usar funciones de empujar y desplazar para poner y sacar de la cola una lista (o, a la inversa, se pueden usar unshift y pop ), [2] aunque en algunos En algunos casos estas operaciones no son eficientes.
La biblioteca de plantillas estándar de C++ proporciona una " queue" clase con plantilla que está restringida únicamente a operaciones push/pop. Desde J2SE5.0, la biblioteca de Java contiene una Queueinterfaz que especifica operaciones en cola; Las clases de implementación 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 () { este . elementos = []; } poner en cola ( elemento ) { este . elementos . empujar ( elemento ); } quitar de la cola () { devolver esto . elementos . cambio (); } } Las colas también se pueden implementar como una estructura de datos puramente funcional . [3] Hay dos implementaciones. El primero sólo logra un promedio por operación . Es decir, el tiempo amortizado es , pero las operaciones individuales pueden tardar 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 el peor de los casos O(1). Es una implementación más compleja y requiere listas diferidas con memorización .
Los datos de esta cola se almacenan en dos listas enlazadas individualmente denominadas y . La lista ocupa la primera parte de la cola. La lista contiene los elementos restantes (también conocidos como la parte final de la cola) en orden inverso . Es fácil insertarlo al principio de la cola agregando un nodo al principio de . Y, si no está vacío, es fácil eliminarlo del final de la cola eliminando el nodo al principio de . Cuando está vacía, la lista se invierte y se asigna y luego se elimina el encabezado de .
La inserción ("poner en cola") siempre lleva tiempo. La eliminación ("quitar de la cola") se realiza cuando la lista no está vacía. Cuando está vacío, lo inverso toma donde está el número de elementos . Pero podemos decir que es tiempo amortizado , porque cada elemento tuvo que ser insertado y podemos asignar un costo constante a cada elemento a la inversa de cuando se insertó.
La cola en tiempo real logra tiempo para todas las operaciones, sin amortización. Esta discusión será técnica, así que recuerde que, para una lista, denota su longitud, que NIL representa una lista vacía y representa la lista cuyo encabezado es h y cuya cola es t .
La estructura de datos utilizada para implementar nuestras colas consta de tres listas enlazadas individualmente donde f es el principio de la cola y r es el final de la cola en orden inverso. La invariante de la estructura es que s es la parte trasera de f sin sus primeros elementos, es decir . La cola de la cola es entonces casi y al insertar un elemento x es casi . Se dice casi, porque en ambos resultados, . Luego se debe llamar a una función auxiliar para que se cumpla el invariante. Se deben considerar dos casos, dependiendo de si la lista está vacía, en cuyo caso , o no. La definición formal es y donde f seguida de r se invierte.
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 diferida 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 rotar es y . Su tiempo de ejecución es , pero, dado que se utiliza una evaluación diferida, el cálculo se retrasa hasta que el cálculo fuerza los resultados.
La lista s en la estructura de datos tiene dos propósitos. Esta lista sirve como contador para , de hecho, si y sólo si s es la lista vacía. Este contador nos permite asegurar que la trasera nunca sea más larga que la lista delantera. Además, el uso de s , que es una cola de f , fuerza el cálculo de una parte de la lista (perezosa) f durante cada operación de inserción y cola . Por tanto, cuando , la lista f es totalmente forzada. Si no fuera el caso, la representación interna de f podría ser algún agregado de agregado de... de agregado, y forzar 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 .
