Cola (tipo de datos abstracto)
En informática , una cola es una colección de entidades que se mantienen en una secuencia y se puede 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 la que se agregan elementos se denomina final, final o final de la cola, y el final en el que se eliminan elementos se denomina cabeza o frente 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 quitar un elemento del frente se conoce como quitar de la cola . Otras operaciones también pueden ser permitidos, a menudo incluyendo un peek o frontal operación que devuelve el valor del siguiente elemento a ser quitadas de la cola sin desencola ella.
Las operaciones de una cola la convierten en una estructura de datos primero en entrar, primero en salir (FIFO) . En una estructura de datos FIFO, el primer elemento agregado a la cola será el primero en ser eliminado. Esto es equivalente 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 una estructura de datos lineal o, de manera más abstracta, una colección secuencial. Las colas son comunes en los programas de computadora, 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 búferes circulares y listas enlazadas .
Las colas brindan servicios en ciencias de la computación , transporte e investigación de operaciones donde varias 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 búfer . Otro uso de las colas es 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 nuevo elemento. También puede estar vacío, momento en el que eliminar un elemento será imposible hasta que se haya agregado de nuevo un nuevo elemento.
Las matrices de longitud fija tienen una capacidad limitada, pero no es cierto que los elementos deban copiarse hacia el principio de la cola. El simple truco de convertir la matriz en un círculo cerrado y dejar que la cabeza y la cola se muevan 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 el cálculo de índices módulo n convertirá la matrizen un círculo. Esta sigue siendo la forma conceptualmente más simple de construir una cola en un lenguaje de alto nivel, pero ciertamente 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 compruebe 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 anticipació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 incluir bibliotecas para listas dinámicas. Tales estructuras de datospuede que no haya especificado un límite de capacidad fijo además de las limitaciones de memoria. El desbordamiento de la cola es el resultado de 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.
