Otra estructura de datos muy usada
Las colas son la otra estructura de datos simple mas usada. Se comporta como cualquier cola, cuando llegas te pones al final, y conforme se va procesando lo que está en la cabecera vas avanzando. Aquí la máxima es que el primero en entrar es el primero en salir.Todos usáis una impresora en vuestro ordenador, cuando enviar cosas a imprimir se colocan en una cola de trabajos, y se van procesando de uno en uno. De esta forma podemos tener todos los trabajos de impresión que necesitemos, nuestros o de otros usuarios, y no se lía la impresora ya que los procesa por estricto orden de llegada.
Las colas son sencillas de implementar usando un arreglo y dos variables que hacen de punteros, uno a la cabeza y otro a la cola, conforme llegan los elementos se aumenta el apuntador a la cola y se ubican en el lugar que indique, cuando se desea sacar algo se usa el elemento ubicado en la posición apuntada por la cabeza y se aumenta el apuntador. La cola esta vacía cuando la cabeza supera a la cola. Para evitar que crezcan indefinidamente, cuando se saca un elemento de la cola y esta queda vacía, se reinician los punteros de cabeza y cola. Otro proceso importante es que muchas veces se introducen un conjunto de elementos a una velocidad y se retiran a otra, con lo que puede que el puntero de cola alcance el tamaño máximo disponible, pero como la cabeza ha avanzado queda espacio disponible al comienzo de la cola, por lo que para recuperar ese espacio hay que compactar la cola, desplazando todos los elementos hacia el comienzo.
Esta implementación de la cola que realizo en SuperBASIC usando un arreglo es muy sencilla, utilizo el elemento 0 del arreglo como apuntador a la cabecera, y el elemento 1 como apuntador a la cola, de esta forma mantengo toda la información de manejo en el arreglo. Dispongo de una serie de procedimientos y funciones para el manejo:
- COLA_CREAR crea una cola con un tamaño mínimo
- COLA_NUEVA crea una cola del tamaño que se le indique y un margen mínimo
- COLA_VACIA retorna un booleano que indica si la cola está vacía
- COLA_ADD añade un dato al final de la cola, si está llena intenta compactarla, si sigue llena la amplia al doble de su tamaño
- COLA_EXTRACT retorna el dato ubicado en la cabecera de cola
- COLA_REDUCE reduce la cola al tamaño real que ocupa mas el margen mínimo
- COLA_CAMBIA cambia su tamaño al que se le indique, puede ser mayor o menor que el tamaño actual de la cola, pero nunca la reduce a menos del numero de elementos que contiene mas el margen mínimo
- COLA_INIT de uso interno por los otros procesos, sirve para inicializar los punteros de la cola, no debe ser usada mas que por los otros procesos de manejo de la cola
- COLA_COMPACTA de uso interno por los otros procesos, pasa todos los elementos ocupados por la cola al principio de la misma, dejando todo el espacio libre al final.
1000 REMark -------------------------------------------------------------- 1010 REMark -- ESTRUCTURAS DE DATOS -- 1020 REMark -- Modulo....: Cola -- 1030 REMark -- Objetivo..: Cola usando un arreglo simple -- 1040 REMark -- Autor.....: javu61, 11/2016 -- 1050 REMark -- Procesos..: -- 1060 REMark -- COLA_CREAR -- Crear la cola -- 1070 REMark -- COLA_NUEVA(tam) -- Crea la cola con un tamaño -- 1080 REMark -- COLA_INIT -- Inicializa una cola -- 1090 REMark -- b=COLA_VACIA -- Ver si la cola esta vacia -- 1100 REMark -- COLA_ADD(dato) -- Introduce un dato en la cola -- 1110 REMark -- v=COLA_EXTRACT -- Saca un dato de la cola -- 1120 REMark -- COLA_REDUCE -- Compacta y reduce su tamaño -- 1130 REMark -- COLA_CAMBIA(tam)-- Cambia el tama‰o de la cola -- 1140 REMark -- COLA_COMPACTA -- Compacta la cola -- 1150 REMark -- Puntero...: Se usa el elemento cero del arreglo como -- 1160 REMark -- puntero a la cabeza, y el elemento 1 como -- 1170 REMark -- puntero a la cola -- 1180 REMark -------------------------------------------------------------- 1190 : 1200 REMark -------------------------------------------------------------- 1210 REMark -- COLA_CREAR -- Crea la cola -- 1220 REMark -------------------------------------------------------------- 1230 DEFine PROCedure COLA_CREAR 1240 COLA_NUEVA 10,5 : REMark Espacio para 10 elementos, crece minimo 5 1250 END DEFine 1260 : 1270 REMark -------------------------------------------------------------- 1280 REMark -- COLA_NUEVA(tam,fac) -- Crea la cola con un tama‰o y -- 1290 REMark -- con un factor de crecimiento -- 1300 REMark -------------------------------------------------------------- 1310 DEFine PROCedure COLA_NUEVA(tam,fac) 1320 LET COLA_FACTOR = fac 1330 LET COLA_CABEZA = 0 1340 LET COLA_COLA = 1 1350 DIM ArrCola(tam+1) : REMark Elementos 0 y 1 se usan como punteros 1360 COLA_INIT 1370 END DEFine 1380 : 1390 REMark -------------------------------------------------------------- 1400 REMark -- COLA_INIT -- Inicializa una cola -- 1410 REMark -------------------------------------------------------------- 1420 DEFine PROCedure COLA_INIT 1430 ArrCola(COLA_CABEZA) = 2 : REMark Puntero a cabeza 1440 ArrCola(COLA_COLA) = 1 : REMark Puntero a cola 1450 END DEFine 1460 : 1470 REMark -------------------------------------------------------------- 1480 REMark -- b = COLA_VACIA -- Ver si la cola esta vacia -- 1490 REMark -- RETORNA: Booleano (Si, No) -- 1500 REMark -------------------------------------------------------------- 1510 DEFine FuNction COLA_VACIA 1520 RETurn (ArrCola(COLA_CABEZA) > ArrCola(COLA_COLA)) 1530 END DEFine 1540 : 1550 REMark -------------------------------------------------------------- 1560 REMark -- COLA_ADD(dato) -- Introduce un dato en la cola, si -- 1570 REMark -- esta llena crece al doble -- 1580 REMark -------------------------------------------------------------- 1590 DEFine PROCedure COLA_ADD(dato) 1600 IF ArrCola(COLA_COLA) = DIMN(ArrCola) THEN 1610 COLA_COMPACTA 1620 END IF 1630 IF ArrCola(COLA_COLA) = DIMN(ArrCola) THEN 1640 COLA_CAMBIA(DIMN(ArrCola)*2) 1650 END IF 1660 ArrCola(COLA_COLA)=ArrCola(COLA_COLA)+1 1670 ArrCola(ArrCola(COLA_COLA))=dato 1680 END DEFine 1690 : 1700 REMark -------------------------------------------------------------- 1710 REMark -- v = COLA_EXTRACT -- Saca un dato de la cola -- 1720 REMark -- RETORNA: Valor de la cabeza de la cola -- 1730 REMark -------------------------------------------------------------- 1740 DEFine FuNction COLA_EXTRACT 1750 LOCal valor 1760 : 1770 IF COLA_VACIA THEN 1780 PRINT"Error: Cola vacia" 1790 STOP 1800 END IF 1810 : 1820 valor=ArrCola(ArrCola(COLA_CABEZA)) 1830 :: ArrCola(ArrCola(COLA_CABEZA))=0 1840 ArrCola(COLA_CABEZA)=ArrCola(COLA_CABEZA)+1 1850 IF COLA_VACIA THEN COLA_INIT 1860 RETurn valor 1870 END DEFine 1880 : 1890 REMark -------------------------------------------------------------- 1900 REMark -- COLA_REDUCE -- Compacta y reduce su tama‰o -- 1910 REMark -------------------------------------------------------------- 1920 DEFine PROCedure COLA_REDUCE 1930 COLA_COMPACTA 1940 COLA_CAMBIA(ArrCola(COLA_CABEZA)+COLA_FACTOR) 1950 END DEFine 1960 : 1970 REMark -------------------------------------------------------------- 1980 REMark -- COLA_CAMBIA -- Cambia el tama‰o de la cola -- 1990 REMark -------------------------------------------------------------- 2000 DEFine PROCedure COLA_CAMBIA(tam) 2010 LOCal b(DIMN(ArrCola)),minimo,i 2020 : 2030 COLA_COMPACTA 2040 FOR i=0 TO ArrCola(COLA_COLA) 2050 IF i > DIMN(ArrCola) THEN EXIT i 2060 b(i)=ArrCola(i) 2070 END FOR i 2080 minimo = ArrCola(COLA_COLA)-ArrCola(COLA_CABEZA)+1 + COLA_FACTOR 2090 IF tam < minimo THEN tam = minimo 2100 IF tam < COLA_FACTOR THEN tam=tam+COLA_FACTOR 2110 COLA_NUEVA tam,COLA_FACTOR 2120 FOR i=0 TO b(COLA_COLA) 2130 ArrCola(i)=b(i) 2140 END FOR i 2150 END DEFine 2160 : 2170 REMark -------------------------------------------------------------- 2180 REMark -- COLA_COMPACTA -- Compacta la cola -- 2190 REMark -------------------------------------------------------------- 2200 DEFine PROCedure COLA_COMPACTA(tam) 2210 LOCal i,ini,fin 2220 : 2230 IF (NOT COLA_VACIA) AND (ArrCola(COLA_CABEZA) > 2) THEN 2240 ini=ArrCola(COLA_CABEZA) 2250 fin=ArrCola(COLA_COLA) 2260 COLA_INIT 2270 FOR i=ini TO fin 2280 COLA_ADD ArrCola(i) 2290 END FOR i 2300 :: FOR i=fin+1 TO DIMN(ArrCola) : ArrCola(i)=0 2310 END IF 2320 END DEFineAdemás de esta implementación mas simple, existe la posibilidad de aprovechar mejor el espacio evitando ampliaciones, cuando la cola alcanza el final del espacio, mira si hay sitio libre al comienzo, lo que será habitual si se han extraído elementos, y continua la cola por allí hasta alcanzar la cabeza. Ahora hay que poner el indicador de cola vacia al sacar un elemento, no podemos fiarnos de que los punteros se crucen ya. Las funciones que se manejan externamente son iguales a las anteriores, solo cambian las funciones de uso interno. He definido los procedimientos siguientes:
- COLA_CREAR crea una cola con un tamaño mínimo
- COLA_NUEVA crea una cola del tamaño que se le indique y un margen mínimo
- COLA_VACIA retorna un booleano que indica si la cola está vacía
- COLA_ADD añade un dato al final de la cola, si está llena intenta compactarla, si sigue llena la amplia al doble de su tamaño
- COLA_EXTRACT retorna el dato ubicado en la cabecera de cola
- COLA_REDUCE reduce la cola al tamaño real que ocupa mas el margen mínimo
- COLA_CAMBIA cambia su tamaño al que se le indique, puede ser mayor o menor que el tamaño actual de la cola, pero nunca la reduce a menos del numero de elementos que contiene mas el margen mínimo
- COLA_INIT de uso interno por los otros procesos, sirve para inicializar los punteros de la cola, no debe ser usada mas que por los otros procesos de manejo de la cola
- COLA_REORDENA de uso interno por los otros procesos, pasa todos los elementos ocupados por la cola al principio de la misma, dejando todo el espacio libre al final. Es la única función que tiene otro nombre entre las dos versiones, ya que realmente hacen lo mismo pero de forma un poco diferente.
1000 REMark -------------------------------------------------------------- 1010 REMark -- ESTRUCTURAS DE DATOS -- 1020 REMark -- Modulo....: Cola -- 1030 REMark -- Objetivo..: Cola usando un arreglo, cola circular -- 1040 REMark -- Autor.....: javu61, 11/2016 -- 1050 REMark -- Procesos..: -- 1060 REMark -- COLA_CREAR -- Crear la cola -- 1070 REMark -- COLA_NUEVA(tam) -- Crea la cola con un tamaño -- 1080 REMark -- COLA_INIT -- Inicializa una cola -- 1090 REMark -- b=COLA_VACIA -- Ver si la cola esta vacia -- 1100 REMark -- COLA_ADD(dato) -- Introduce un dato en la cola -- 1110 REMark -- v=COLA_EXTRACT -- Saca un dato de la cola -- 1120 REMark -- COLA_REDUCE -- Reordena y reduce su tamaño -- 1130 REMark -- COLA_CAMBIA(tam)-- Cambia el tama‰o de la cola -- 1140 REMark -- COLA_REORDENA -- Reordena la cola -- 1150 REMark -- Puntero...: Se usa el elemento cero del arreglo como -- 1160 REMark -- puntero a la cabeza, y el elemento 1 como -- 1170 REMark -- puntero a la cola -- 1180 REMark -------------------------------------------------------------- 1190 : 1200 REMark -------------------------------------------------------------- 1210 REMark -- COLA_CREAR -- Crea la cola -- 1220 REMark -------------------------------------------------------------- 1230 DEFine PROCedure COLA_CREAR 1240 COLA_NUEVA 10,5 : REMark Espacio minimo 10 elementos 1250 END DEFine 1260 : 1270 REMark -------------------------------------------------------------- 1280 REMark -- COLA_NUEVA(tam,fac) -- Crea la cola con un tama‰o y -- 1290 REMark -- con un factor de crecimiento -- 1300 REMark -------------------------------------------------------------- 1310 DEFine PROCedure COLA_NUEVA(tam,factor) 1320 LET COLA_FACTOR = factor 1330 LET COLA_CABEZA = 0 1340 LET COLA_COLA = 1 1350 DIM ArrCola(tam+1) : REMark Elementos 0 y 1 se usan como punteros 1360 COLA_INIT 1370 END DEFine 1380 : 1390 REMark -------------------------------------------------------------- 1400 REMark -- COLA_INIT -- Inicializa una cola -- 1410 REMark -------------------------------------------------------------- 1420 DEFine PROCedure COLA_INIT 1430 ArrCola(COLA_CABEZA) = 0 : REMark Puntero a cabeza 1440 ArrCola(COLA_COLA) = 0 : REMark Puntero a cola 1450 END DEFine 1460 : 1470 REMark -------------------------------------------------------------- 1480 REMark -- b = COLA_VACIA -- Ver si la cola esta vacia -- 1490 REMark -- RETORNA: Booleano (Si, No) -- 1500 REMark -------------------------------------------------------------- 1510 DEFine FuNction COLA_VACIA 1520 RETurn (ArrCola(COLA_CABEZA) = 0) 1530 END DEFine 1540 : 1550 REMark -------------------------------------------------------------- 1560 REMark -- COLA_ADD(dato) -- Introduce un dato en la cola, si -- 1570 REMark -- esta llena crece al doble -- 1580 REMark -------------------------------------------------------------- 1590 DEFine PROCedure COLA_ADD(dato) 1600 REMark Si la cola estŒ vacia, posiciono al comienzo 1610 IF ArrCola(COLA_COLA)=0 THEN 1620 ArrCola(COLA_CABEZA)=2 1630 ArrCola(COLA_COLA) =1 1640 ELSE 1650 : 1660 REMark Si la cola alcanza la cabeza, estŒ lleno 1670 IF ArrCola(COLA_COLA)+1 = ArrCola(COLA_CABEZA) THEN 1680 COLA_CAMBIA(DIMN(ArrCola)*2) 1690 END IF 1700 : 1710 REMark Si la cola alcanza el final del arreglo 1720 IF ArrCola(COLA_COLA) = DIMN(ArrCola) THEN 1730 IF ArrCola(COLA_CABEZA) >2 THEN 1740 ArrCola(COLA_COLA)=1 1750 ELSE 1760 COLA_CAMBIA(DIMN(ArrCola)*2) 1770 END IF 1780 END IF 1790 END IF 1800 : 1810 ArrCola(COLA_COLA)=ArrCola(COLA_COLA)+1 1820 ArrCola(ArrCola(COLA_COLA))=dato 1830 END DEFine 1840 : 1850 REMark -------------------------------------------------------------- 1860 REMark -- v = COLA_EXTRACT -- Saca un dato de la cola -- 1870 REMark -- RETORNA: Valor de la cabeza de la cola -- 1880 REMark -------------------------------------------------------------- 1890 DEFine FuNction COLA_EXTRACT 1900 LOCal valor 1910 : 1920 IF COLA_VACIA THEN 1930 PRINT"Error: Cola vacia" 1940 STOP 1950 END IF 1960 : 1970 valor=ArrCola(ArrCola(COLA_CABEZA)) 1980 :: ArrCola(ArrCola(COLA_CABEZA))=0 1990 ArrCola(COLA_CABEZA)=ArrCola(COLA_CABEZA)+1 2000 IF ArrCola(COLA_CABEZA) > DIMN(ArrCola) THEN 2010 ArrCola(COLA_CABEZA)=2 2020 END IF 2030 : 2040 REMark Ver si cola vacia 2050 IF ArrCola(COLA_CABEZA) = ArrCola(COLA_COLA)+1 THEN COLA_INIT 2060 RETurn valor 2070 END DEFine 2080 : 2090 REMark -------------------------------------------------------------- 2100 REMark -- COLA_REDUCE -- Reordena y reduce su tama‰o -- 2110 REMark -------------------------------------------------------------- 2120 DEFine PROCedure COLA_REDUCE 2130 COLA_REORDENA 2140 COLA_CAMBIA(0) 2150 END DEFine 2160 : 2170 REMark -------------------------------------------------------------- 2180 REMark -- COLA_CAMBIAR -- Cambia el tama‰o de la cola -- 2190 REMark -------------------------------------------------------------- 2200 DEFine PROCedure COLA_CAMBIA(tam) 2210 LOCal b(DIMN(ArrCola)),mintam,i 2220 : 2230 COLA_REORDENA 2240 FOR i=0 TO ArrCola(COLA_COLA) : b(i)=ArrCola(i) 2250 : 2260 mintam = ArrCola(COLA_COLA)-ArrCola(COLA_CABEZA)+1 + COLA_FACTOR 2270 IF tam < mintam THEN tam=mintam 2280 IF tam < COLA_FACTOR THEN tam=tam+COLA_FACTOR 2290 COLA_NUEVA tam, COLA_FACTOR 2300 : 2310 FOR i=0 TO b(COLA_COLA) 2320 ArrCola(i)=b(i) 2330 END FOR i 2340 END DEFine 2350 : 2360 REMark -------------------------------------------------------------- 2370 REMark -- COLA_REORDENA -- Reordena la cola -- 2380 REMark -------------------------------------------------------------- 2390 DEFine PROCedure COLA_REORDENA 2400 LOCal b(DIMN(ArrCola)),i,j,ini,fin 2410 : 2420 ini=ArrCola(COLA_CABEZA) 2430 fin=ArrCola(COLA_COLA) 2440 j=1 2450 : 2460 REMark Copio de la cabeza al final o a la cola 2470 FOR i=ini TO DIMN(ArrCola) 2480 IF (fin > ini) AND (i > fin) THEN EXIT i 2490 j=j+1: : b(j)=ArrCola(i) 2500 END FOR i 2510 : 2520 REMark Copio del inicio a la cola 2530 IF (fin < ini) THEN 2540 FOR i=2 TO fin 2550 j=j+1: : b(j)=ArrCola(i) 2560 END FOR i 2570 END IF 2580 : 2590 ArrCola(COLA_CABEZA) = 2 2600 ArrCola(COLA_COLA) = j 2610 FOR i= 2 TO j : ArrCola(i)=b(i) 2620 :: FOR i=j+1 TO DIMN(ArrCola) : ArrCola(i)=0 2630 END DEFine
Para realizar las pruebas de las colas he creado un pequeño programita que me las automatiza, siempre hay que definir una serie de pruebas de funcionamiento diversas y pensadas para probar los puntos vulnerables de las rutinas, y luego pasarlas para las dos rutinas, lo que al usar las funciones con el mismo nombre me aseguro de funciona y ambas pasan las mismas pruebas.
100 MODE 4: PAPER 0 : CLS 110 INPUT "Cual prefiere (1)=Simple (2)=Circular",t$ 120 IF t$<>"1" AND t$<>"2" THEN GO TO 110 130 n$="mdv1_ed_cola_arreglo" & t$ 140 PRINT "Cargando ";n$ 150 MERGE n$ 160 : 170 MODE 4: PAPER 0 : CLS : LET No=0 : LET Si=1 180 t1=DATE 190 : 200 COLA_CREAR 210 : 220 PRINT "PRUEBA 1: Introduce 3 elementos y los extrae" 230 FOR i=1 TO 3 : mete(i) 240 FOR i=1 TO 3 : saca(i) 250 PRINT 260 : 270 PRINT "PRUEBA 2: Introduce 9, extrae 5, introduce 3, extrae 9" 280 FOR i=1 TO 9 : mete(i) 290 FOR i=1 TO 5 : saca(i) 300 FOR i=10 TO 13 : mete(i) 310 FOR i=6 TO 13 : saca(i) 320 PRINT 330 : 340 PRINT "PRUEBA 3: Inroduce 9, Extrae 2, introduce 10 y reduce" 350 FOR i=1 TO 9 : mete(i) 360 FOR i=1 TO 2 : saca(i) 370 FOR i=10 TO 19 : mete(i) 380 PRINT "CM "; : COLA_REDUCE : ver 390 PRINT 400 : 410 PRINT "PRUEBA 4: Extrae elementos hasta error por vacia" 420 FOR i=3 TO 19 : saca(i) 430 t2=DATE 440 PRINT "Tard֠";t2-t1;" segundos" 450 saca(0) 460 STOP 470 : 480 DEFine PROCedure mete(a) 490 PRINT "EN ";a;" - "; 500 COLA_ADD(a) 510 ver 520 END DEFine 530 : 540 DEFine PROCedure saca(a) 550 PRINT "SA "; 560 s=COLA_EXTRACT 570 IF a<>s THEN PRINT "ERROR" : STOP 580 PRINT s;" - "; : ver 590 END DEFine 600 : 610 DEFine PROCedure ver 620 LOCal xx 630 : 640 IF COLA_VACIA THEN 650 PRINT "v "; 660 ELSE 670 PRINT " "; 680 END IF 690 PRINT ArrCola(0);!ArrCola(1);": "; 700 FOR xx=2 TO DIMN(ArrCola) : PRINT !ArrCola(xx); 710 PRINT 720 END DEFine
En ambos casos ha tardado 24 segundos en ejecutarse, ya que la diferencia es mínima entre ambas, con mas datos seguro que la primera es mas rápida que la segunda si no hay aumentos de tamaño por ser mas simple, pero la segunda ganará cuando tenga muchos movimientos de entrada y salida continua, por no necesitar reordenar ni ampliar la cola.
Todo lo que he desarrollado hasta ahora de algoritmos de ordenación y de estructuras de datos está aquí para que lo podáis descargar.
No hay comentarios:
Publicar un comentario