Como se había dicho anteriormente en el blog pasado, las colas en informática, es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción "push" se realiza por un extremo y la operación de extracción "pop" por el otro. También se le llama estructura FIFO(del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir. En está sección estaremos hablando más a profundidad de este tipo de estructuras e inclusive hacer una comparación entre las colas implementadas en arreglos y en listas enlazadas.
La cola basada en matriz es algo difícil de implementar de manera efectiva. Una simple conversión de lista basada en matriz no es eficiente, supongamos que hay "n" elementos en la cola, con la matriz basada en lista, podríamos requerir que todos los elementos de la cola se almacenen en las primeras posiciones de la matriz. Si elegimos el elemento trasero de la cola para estar en posición 0, entonces las operaciones de deshilachado requieren solo - (1) tiempo, debido a que el elemento frontal de la cola ( el que está siendo eliminado) es el último elemento de la matriz. Sin embargo, las operaciones de "enqueue(encolar)" requerirán -(n) tiempo, porque los n elementos actualmente en la cola debe ser desplazado a una posición en la matriz. Si en cambio elegimos el elemento posterior de la cola para estar en la posición n-1, entonces una operación de "enqueue" es equivalente a una operación de agregación en una lista, esto requiere sólo -(1) tiempo, pero ahora, una operación de "dequeue(desencolar)" requiere -(n) tiempo, porque todos los elementos deben ser desplazados hacia abajo por una posición para retener la propiedad de que el n-1 restante de los elementos de la cola residen en la primeras posiciones de n-1 de la matriz.
La implentación de la cola enlazada es una adaptación directa de la lista enlazada. Los métodos delanteros y traseros son punteros a los elementos de cola delantera y trasera respectivamente. Usando un encabezado de nodo enlace, lo que permite una implementación más sencilla de la operación, evitando casos especiales cuando la cola está vacía. "Enqueue" coloca el nuevo elemento en un nodo enlace al final de la lista enlazada y luego avanza hacia atrás para apuntar al nuevo enlace nodo. "Dequeue" agarra el primer elemento de la lista y lo elimina.
Teniendo en cuenta la implementación de la cola con arreglos y enlazadas, me gustaría concluir con una comparación entre cola en arreglos y cola enlazada. Para empezar, las implementaciones de cola basadas en matrices y enlazadas requieren tiempo constante. Los problemas de comparación de espacios son los mismos que para el equivalente de implentaciones en pila basadas en array, no hay manera conveniente de almacenar dos colas en la misma matriz, a menos que los elementos siempre son transferidos directamente de una cola a la otra.
Fuentes:
A Practical Introduction to Data Structures and Algorithm Analysis Third Edition (C++ Version)
Colas en informática
Comentarios
Publicar un comentario