COLA CIRCULR

UNIDAD II
ESTRUCTURA DE DATOS 1
COLA CIRCULAR
DIRECCION ELECTRONICA:
http://personal.telefonica.terra.es/web/pegonrui/colas/colas.html#colascircC
CONTENIDO:
Colas circulares
Antes de entrar en detalles, recordemos el operador módulo, que en el lenguaje C, se representa por %. Sea m un entero mayor que cero. La expresión a % m representa el resto de la división entre a y m. Por laspropiedades de la división, si r = a % m, entonces, el entero r es tal que 0 ≤ r < m. Cuando r = 0, la división es exacta. Por ejemplo, 27 % 6 = 3, ya que al dividir 27 entre entre 6 resulta un resto de 3. Análogamente, 27% 9 = 0, pues al dividir 27 entre entre 9 resulta un resto de 0.
Operando módulo m solamente pueden aparecer los números:
0, 1, 2, ..., m-1
Si contamos de 1 a 10 módulo 7, losrestos son:
n
1
2
3
4
5
6
7
8
9
10
n % 7
1
2
3
4
5
6
0
1
2
3
La situación es idéntica a la que se presenta en el cuentakilómetros de un coche, una vez llegada al límite, el contador vuelve a 0.
Concepto de cola circular
El ambiente es el mismo que en la sección anterior, en concreto, disponemos de un vector de estructuras donde almacenar los datos. Sea m el número deestructuras. La cola no puede almacenar más de m elementos y los datos los numeramos como siempre, por índices que varían entre 0 y m-1 (ver figura siguiente):

Hacemos la estructura circular, identificando el siguiente de m-1 con 0, en otras palabras, operamos módulo m. Sea n el número de elementos de la cola (0 ≤ n ≤ m). La cola está vacía cuando n = 0 y llena cuando n = m. Otro entero, quedesignamos por fr, nos indica donde está situado el frente de la cola, es decir, el primer elemento a tratar. Para no perdernos, veamos un ejemplo. Tomemos m = 5, n = 3, fr = 0. En este caso, la cola es la siguiente:

Ahora extraemos el primer elemento, el indicado por el frente, con lo que la cola queda como:

y por consiguiente, ahora es n = 2, fr = 1. Es decir, cada vez que extraigamos unelemento, el frente avanza una unidad módulo m y n se decrementa en 1.
Veamos ahora las operaciones a realizar:
Insertar un elemento en la cola
El algoritmo es:

Extraer un elemento de la cola
El algoritmo es:

Para aclarar las ideas, seguimos con el ejemplo anterior. La situación había quedado como n = 2, fr = 1, es decir:


Insertamos un nuevo elemento. Siguiendo el algoritmo:
i = (fr+ n) % m → i = (1 + 2) % 5 = 3 % 5 = 3
es decir, copiamos el dato a la posición i = 3 e incrementamos n, con lo que n = 3, y la cola queda como:

Insertamos uno más. Otra vez:
i = (fr + n) % m → i = (1 + 3) % 5 = 4 % 5 = 4
es decir, copiamos el dato a la posición i = 4 e incrementamos n, con lo que n = 4, y la cola queda como:

Extraemos ahora. Siguiendo el algoritmo, sea x elelemento situado en la posición 1:
fr = (fr + 1) % m → fr = (1 + 1) % 5 = 2 % 5 = 2
y decrementamos n, con lo que n = 3, y la cola queda como:

Finalmente, volvemos a insertar un elemento más. Otra vez:
i = (fr + n) % m → i = (2 + 3) % 5 = 5 % 5 = 0
es decir, copiamos el dato a la posición i = 0 e incrementamos n, con lo que n = 4, y la cola queda como:

Observemos, que no es necesariocorrer los elementos, los cuales se encuentran ocupando posiciones consecutivas, naturalmente, módulo m. La programación se ha complicado un poco, pero hemos ganado en eficiencia.
Definición de una cola circular en C
Es conveniente separar los datos de los índices, así que la definición de una cola es la siguiente:

donde en algún lugar hay que definir la estructura dato. Si cambiamos estaúltima, la cola también cambia y no hay que hacer cambios en la estructura. Las variables están claras, salvo que nmax es la m de los ejemplos anteriores. Falta, para completar el estudio, el inicializar una cola, lo cual se hace con una llamada a malloc, en concreto, si definimos:
struct cola x;
y nmax es el número máximo de elementos que contendrá x, entonces:


con lo cual disponemos de...