Colas Algoritmos

COLAS

Una cola es una estructura de almacenamiento, donde la podemos considerar como una lista de elementos, en la que éstos van a ser insertados por un extremo y serán extraídos por otro.

Las colas son estructuras de tipo PEPS (Primeras Entradas, Primeras Salidas), ya que el primer elemento en entrar a la cola será el primero en salir de ella.

Existen muchísimos ejemplos de colas en la vida real, como por ejemplo: personas esperando en un teléfono público, niños esperando para subir a un juego mecánico, estudiantes esperando para subir a un camión escolar, etc.

Representación en Memoria

Podemos representar a las colas de dos formas :

• Como arreglos

• Como listas ordenadas

En esta unidad trataremos a las colas como arreglos de elementos, en donde debemos definir el tamaño de la cola y dos apuntadores, uno para accesar el primer elemento de la lista y otro que guarde el último. En lo sucesivo, al apuntador del primer elemento lo llamaremos F, al de el último elemento A y MAXIMO para definir el número máximo de elementos en la cola.

Cola Lineal

La cola lineal es un tipo de almacenamiento creado por el usuario que trabaja bajo la técnica FIFO (primero en entrar primero en salir). Las colas lineales se representan gráficamente de la siguiente manera:

Las operaciones que podemos realizar en una cola son las de inicialización, inserción y extracción. Los algoritmos para llevar a cabo dichas operaciones se especifican más adelante.

Las condiciones a considerar en el tratamiento de colas lineales son las siguientes:

• Overflow (cola llena), cuando se realice una inserción.

• Underflow (cola vacía), cuando se requiera de una extracción en la cola.

• Vacío

ALGORITMO DE INICIALIZACIÓN

F < -- 1

A <-- 0

ALGORITMO PARA INSERTAR

Inicio

Si A=máximo entonces

Mensaje (overflow)

En caso contrario

A<-- A+1

Cola [A] <-- valor

Fin

ALGORITMO PARA EXTRAER

Si A&ltF entonces

Mensaje (underflow)

En caso contrario

F <-- F+1

x <-- cola [F]

Cola Circular

Las colas lineales tienen un grave problema, como las extracciones sólo pueden realizarse por un extremo, puede llegar un momento en que el apuntador A sea igual al máximo número de elementos en la cola, siendo que al frente de la misma existan lugares vacíos, y al insertar un nuevo elemento nos mandará un error de overflow (cola llena).

Para solucionar el problema de desperdicio de memoria se implementaron las colas circulares, en las cuales existe un apuntador desde el último elemento al primero de la cola.

La representación gráfica de esta estructura es la siguiente:

La condición de

...