Cola (tipo de datos abstracto)

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Tipo de datos abstractos

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 en el otro. final de la secuencia. Por convención, el final de la secuencia en el que se agregan los elementos se denomina parte posterior, cola o parte posterior de la cola, y el final en el que se eliminan los elementos se denomina cabeza o parte delantera de la cola, de manera análoga a las palabras que se usan 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 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 peek o front que devuelve el valor del siguiente elemento que se eliminará de la cola sin eliminarlo.

Las operaciones de una cola la convierten en una estructura de datos de tipo 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 acopladas con rutinas de acceso, como una estructura de datos abstracta o en lenguajes orientados a objetos como clases. Las implementaciones comunes son los búferes circulares y las listas enlazadas.

Las colas brindan servicios en informática, transporte e investigación de operaciones donde varias entidades, como datos, objetos, personas o eventos, se almacenan y mantienen para su posterior procesamiento. En estos contextos, la cola realiza la función de un búfer. Otro uso de las colas es en la implementación de la búsqueda en amplitud.

Implementación de colas

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 será imposible eliminar un elemento hasta que se vuelva a agregar 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 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, calcular í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 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 verifique si un índice de matriz está fuera de los límites, lo que hacen algunos idiomas, pero este será sin duda el método elegido para una implementación rápida y sucia, o para cualquier idioma 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 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 dichas 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 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 limitada es una cola limitada a un número fijo de elementos.

Hay varias implementaciones eficientes de colas FIFO. Una implementación eficiente es aquella que puede realizar las operaciones (poner y quitar cola) en tiempo O(1).

Lista enlazada
- Una lista doblemente vinculada tiene O(1) inserción y eliminación en ambos extremos, por lo que es una opción natural para las colas.
- Una lista regular enlazada sólo tiene una inserción y eliminación eficientes en un extremo. Sin embargo, una pequeña modificación que mantiene un puntero al último nodo además del primero, le permitirá implementar una cola eficiente.
Un deque implementado usando un array dinámico modificado

Colas y lenguajes de programación

Las colas pueden implementarse como un tipo de datos separado, o pueden considerarse un caso especial de una cola doble (deque) y no implementarse por separado. Por ejemplo, Perl y Ruby permiten empujar y extraer una matriz desde ambos extremos, por lo que se pueden usar las funciones empujar y cambiar para poner y sacar una lista de la cola (o, a la inversa, uno puede usar unshift y pop), aunque en algunos casos estas operaciones no son eficientes.

La biblioteca de plantillas estándar de C++ proporciona una "cola" clase con plantilla que está restringida solo a operaciones push/pop. Desde J2SE5.0, la biblioteca de Java contiene una interfaz Queue que especifica las operaciones de la cola; las clases de implementación incluyen LinkedList y (desde J2SE 1.6) ArrayDeque. PHP tiene una clase SplQueue y bibliotecas de terceros como beanstalk'd y Gearman.

Ejemplo

Una cola simple implementada en JavaScript:

clase Queue {} constructor() {} esto.Temas = []; } enqueue()elemento) {} esto.Temas.empujar()elemento); } dequeue() {} retorno esto.Temas.cambio(); }}

Implementación puramente funcional

Las colas también pueden ser implementadas como una estructura de datos puramente funcional. Hay dos implementaciones. El primero solo logra $O(1)$ por operación promedio. Es decir, el tiempo amortizado es $O(1)$ , pero las operaciones individuales pueden tomar $O(n)$ Donde n es el número de elementos en la cola. La segunda aplicación se denomina cola en tiempo real y permite que la cola sea persistente con operaciones en O(1) peor tiempo. Es una aplicación más compleja y requiere listas perezosas con memoización.

Cola amortizada

Los datos de esta cola se almacenan en dos listas conectadas por cantar llamadas $f$ y $r$ . La lista $f$ mantiene la parte frontal de la cola. La lista $r$ mantiene los elementos restantes (a.k.a., 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 cabeza de $f$ . Y, si $r$ no está vacío, es fácil de quitar del extremo de la cola al quitar el nodo en la cabeza de $r$ . Cuando $r$ está vacía, la lista $f$ se invierte y se asigna a $r$ y luego la cabeza de $r$ es eliminado.

El inserto ("enqueue") siempre toma $O(1)$ tiempo. La eliminación ("dequeue") toma $O(1)$ cuando la lista $r$ no está vacío. Cuando $r$ está vacío, la toma inversa $O(n)$ Donde $n$ es el número de elementos en $f$ . Pero podemos decir que es $O(1)$ tiempo amortizado, porque cada elemento en $f$ tuvo que ser insertado y podemos asignar un costo constante para cada elemento en el reverso a cuando se insertó.

Cola en tiempo real

La cola en tiempo real logra $O(1)$ tiempo para todas las operaciones, sin amortización. Esta discusión será técnica, así que recuerde que, para $l$ una lista, ${displaystyle |l|}$ denota su longitud, que NIL representa una lista vacía y ${displaystyle operatorname {CONS} (h,t)}$ 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 de canto ${displaystyle (f,r,s)}$ Donde f es el frente de la cola, r es la parte trasera de la cola en orden inverso. El invariante de la estructura es que s es la parte trasera de f sin ella $|r|$ primeros elementos, es decir ${displaystyle |s|=|f|-|r|}$ . La cola de la cola ${displaystyle (operatorname {CONS} (x,f),r,s)}$ entonces casi ${displaystyle (f,r,s)}$ y insertar un elemento x a ${displaystyle (f,r,s)}$ casi ${displaystyle (f,operatorname {CONS} (x,r),s)}$ . Se dice casi, porque en ambos resultados, ${displaystyle |s|=|f|-|r|+1}$ . Una función auxiliar ${displaystyle aux}$ debe ser llamado para que el invariante esté satisfecho. Hay que considerar dos casos, dependiendo de si $s$ es la lista vacía, en cuyo caso ${displaystyle |r|=|f|+1}$ , o no. La definición oficial es ${displaystyle operatorname {aux} (f,r,operatorname {Cons} (_,s))=(f,r,s)}$ y ${displaystyle operatorname {aux} (f,r,{text{NIL}})=(f',{text{NIL}},f')}$ Donde $f'$ es f seguido r invertido.

Vamos a llamar ${displaystyle operatorname {reverse} (f,r)}$ la función que devuelve f seguido r invertido. Asumamos además que ${displaystyle |r|=|f|+1}$ , ya que es el caso cuando se llama esta función. Más precisamente, definimos una función perezosa ${displaystyle operatorname {rotate} (f,r,a)}$ que toma como entrada tres lista tal que ${displaystyle |r|=|f|+1}$ , y devolver la concatenación de f, de r y de a. Entonces... ${displaystyle operatorname {reverse} (f,r)=operatorname {rotate} (f,r,{text{NIL}})}$ . La definición inductiva de rotación es ${displaystyle operatorname {rotate} ({text{NIL}},operatorname {Cons} (y,{text{NIL}}),a)=operatorname {Cons} (y,a)}$ y ${displaystyle operatorname {rotate} (operatorname {CONS} (x,f),operatorname {CONS} (y,r),a)=operatorname {Cons} (x,operatorname {rotate} (f,r,operatorname {CONS} (y,a)))}$ . Su tiempo de funcionamiento es ${displaystyle O(r)}$ , pero, ya que se utiliza la evaluación perezosa, el cálculo se retrasa hasta que los resultados se vean forzados por el cálculo.

La lista s en la estructura de datos tiene dos propósitos. Esta lista sirve como contador para ${displaystyle |f|-|r|}$ , de hecho, ${displaystyle |f|=|r|}$ si s es la lista vacía. Este contador nos permite asegurarnos de que la parte trasera nunca sea más larga que la lista frontal. Además, utilizando s, que es una cola de f, fuerza la computación de una parte de la lista (lazy) f durante cada uno cola y insertar operación. Por lo tanto, cuando ${displaystyle |f|=|r|}$ , la lista f es totalmente forzado. Si no fuera el caso, la representación interna de f podría ser un apéndice de... de apéndice, y forzar ya no sería una operación de tiempo constante.

Contenido relacionado

Más resultados...