Cola (tipo de dato abstracto)

Las colas pueden implementarse como un tipo de dato separado, 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 elementos de un array desde ambos extremos, por lo que se pueden usar las funciones push y shift para insertar y extraer elementos de una lista (o, a la inversa, se pueden usar unshift y pop ), ^{[ 2 ]} aunque en algunos casos estas operaciones no son eficientes.

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

Una cola sencilla implementada en TypeScript :

clase Cola < T > { elementos privados : T [] = [];enqueue ( elemento : T ) : void { this . items . push ( elemento ); }dequeue ( ) : T | indefinido { return this.items.shift ( ) ; }​isEmpty ( ) : boolean { return this.items.length === 0 ; } }​​​

Los datos de esta cola se almacenan en dos listas enlazadas simples llamadas${\displaystyle f}$y${\displaystyle r}$La lista${\displaystyle f}$ocupa la parte delantera de la cola. La lista${\displaystyle r}$contiene los elementos restantes (también conocidos como el final de la cola) en orden inverso . Es fácil insertar en el frente de la cola agregando un nodo al principio de la misma.${\displaystyle f}$. Y, si${\displaystyle r}$no está vacío, es fácil eliminarlo del final de la cola eliminando el nodo que está al principio de${\displaystyle r}$. Cuando${\displaystyle r}$está vacía, la lista${\displaystyle f}$se revierte y se asigna a${\displaystyle r}$y luego el jefe de${\displaystyle r}$se elimina.

La inserción ("enqueue") siempre toma${\displaystyle O(1)}$tiempo. La eliminación ("dequeue") lleva${\displaystyle O(1)}$cuando la lista${\displaystyle r}$no está vacío. Cuando${\displaystyle r}$está vacío, el reverso toma${\displaystyle O(n)}$dónde${\displaystyle n}$es el número de elementos en${\displaystyle f}$Pero podemos decir que es${\displaystyle O(1)}$tiempo amortizado , porque cada elemento en${\displaystyle f}$Tuvo que ser insertado y podemos asignar un costo constante para cada elemento en orden inverso al momento en que fue insertado.

La cola en tiempo real logra${\displaystyle O(1)}$tiempo para todas las operaciones, sin amortización. Esta discusión será técnica, así que recuerde que, para${\displaystyle 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 consta de tres listas enlazadas simples.${\displaystyle (f,r,s)}$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 su${\displaystyle |r|}$primeros elementos, es decir${\displaystyle |s|=|f|-|r|}$. La cola${\displaystyle (\operatorname {CONS} (x,f),r,s)}$es entonces casi${\displaystyle (f,r,s)}$y insertando un elemento x a${\displaystyle (f,r,s)}$es 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}$Entonces debe llamarse para que se satisfaga el invariante. Deben considerarse dos casos, dependiendo de si${\displaystyle s}$es la lista vacía, en cuyo caso${\displaystyle |r|=|f|+1}$o no. La definición formal es${\displaystyle \operatorname {aux} (f,r,\operatorname {Cons} (\_,s))=(f,r,s)}$y${\displaystyle \operatorname {aux} (f,r,{\text{NIL}})=(f',{\text{NIL}},f')}$dónde${\displaystyle f'}$es f seguido de r invertido.

Permítanos llamar${\displaystyle \operatorname {reverse} (f,r)}$la función que devuelve f seguida de r invertida. Supongamos además que${\displaystyle |r|=|f|+1}$, puesto que es el caso cuando se llama a esta función. Más precisamente, definimos una función perezosa.${\displaystyle \operatorname {rotar} (f,r,a)}$que toma como entrada tres listas tales que${\displaystyle |r|=|f|+1}$y devuelve la concatenación de f , de r invertida y de a . Entonces${\displaystyle \operatorname {reverse} (f,r)=\operatorname {rotate} (f,r,{\text{NIL}})}$. La definición inductiva de rotar es${\displaystyle \operatorname {rotar} ({\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 ejecución es${\displaystyle O(r)}$, pero, dado que se utiliza la evaluación perezosa, el cálculo se retrasa hasta que los resultados se ven 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|}$, en efecto,${\displaystyle |f|=|r|}$si y solo si s es la lista vacía. Este contador nos permite asegurar que la parte posterior nunca sea más larga que la parte 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${\displaystyle |f|=|r|}$La lista f es totalmente forzada. Si no fuera así, la representación interna de f podría ser una especie de concatenación de concatenaciones de... de concatenaciones, y forzarla ya no sería una operación de tiempo constante.

•  Este artículo incorpora material de dominio público de Paul E. Black. "Cola acotada" . Diccionario de algoritmos y estructuras de datos . NIST .