• Retrointernet
Retrointernet
Estructuras de datos: diferencias entre PILAS y COLAS

Estructuras de datos: diferencias entre PILAS y COLAS

  • 21 de septiembre de 2018

Una lista es una estructura lineal de datos sobre la cual podemos realizar, entre otras, operaciones de inserción o borrado de elementos que se encontrarán en cualquier lugar.

Las pilas, sin embargo, sólo permiten la inserción o borrado de nuevos elementos por un extremo de la lista, distinguiéndose dos tipos de pilas: las LIFO (last-in, first-out) y las FIFO (first-in, first-out), o colas.


PILAS LIFO

Las pilas LIFO (el primer elemento que entra es el último que sale, o al revés, siguiendo el significado de LIFO: el último elemento en entrar es el primero en salir), guardan una analogía total con cualquier pila de objetos que podamos imaginar.

Imaginemos que a nuestra pila vacía, le vamos añadiendo elementos sólo por su parte superior. Cuando deseemos extraer uno de ellos, nos veremos obligados a hacerlo en orden inverso al que los hemos introducido: sacaremos en primer lugar el que esté situado en la parte más alta de la pila, esto es, el último que hubiéramos insertado.

Lo que, en principio, puede parecer una limitación a la potencia de las listas, presenta algunas aplicaciones interesantes. La más conocida emplea este tipo de estructura para tratar las llamadas a subrutinas.

Cuando, desde un programa principal, llamamos a una subrutina, el ordenador debe saber que, una vez terminada la ejecución de la misma, tiene que volver al punto desde el que se la llamó. Si sólo fuera posible llamar a una subrutina a la vez, la implementación podría realizarse mediante otro tipo de estructura, pero puesto que podemos encadenar cuantas llamadas a subrutinas deseemos, la pila LIFO aparece como el método de trabajo más eficiente.


PILAS FIFO o COLAS

Las colas o pilas FIFO se diferencian de las LIFO en el orden en que introducimos y extraemos los elementos de la estructura. Mientras en las anteriores sólo disponíamos de un extremo de la misma para la actualización de elementos, en ésta introducimos los datos por un extremo de la lista y los extraemos por el otro.

Con este método de trabajo, conseguimos que el primer elemento que hayamos introducido, sea también el primero que saquemos. El nombre de «cola» viene de su semejanza con la vida real. Cuando realizamos una cola para sacar una entrada de cine, la primera persona que haya llegado, será la primera que obtenga su entrada y, por tanto, la primera que abandone la cola.

Ahora bien, este no es el único modo de realizar una cola. Podemos necesitar una cola con prioridades. Imaginemos la cola ante un semáforo. En principio, la gestión de la misma puede realizarse conforme al modelo anterior, pero si llega una ambulancia (vehículo con prioridad), ésta se situará en el primer lugar de la cola, independientemente del momento de llegada de los anteriores vehículos. Si llegaran más vehículos con prioridad, éstos seguirían formando una cola, pero independiente de la anterior.

Este modo de gestión de las listas lineales, tiene, por supuesto, su aplicación en el mundo de los ordenadores, por ejemplo, en la compartición de recursos. Podemos disponer de varios ordenadores, perouna sola impresora. Cada vez que un usuario desee hacer uso de la misma, deberá situarse en una cola de espera en la que será atendido por orden de llegada.

Pero si alguno de los usuarios está dotado de una asignación de prioridad, se saltará la cola de los no-prioritarios y sólo guardará la cola de los usuarios que tengan el mismo nivel de prioridad que él.

Vídeo relacionado