La estructura de datos fundamental
Mezclaré un poco los temas de algoritmos y de estructuras de datos, ya que son los dos aspectos fundamentales de la programación. Comenzamos por la mas usada en todos los ordenadores, las pilas son la base de los lenguajes, tanto nuestro querido Basic como de los modernos lenguajes orientados a objeto, todos usan las pilas para guardar datos de manera temporal.Imaginemos una pila de platos. Cuando queremos poner un plato lo debemos ubicar siempre encima, y si deseamos sacar un plato siempre lo debemos retirar de la cima. De esta forma podemos ir poniendo y sacando platos de la pila, hasta que la pila se quede vacía, o hasta que ocupe todo el espacio y no pueda crecer mas. El primer plato que pongamos en la pila no lo podemos sacar hasta que no hayamos retirado todos los que estén encima, por lo que se dice que el primero en entrar será el último en salir.
En Basic clásico, cuando se encuentra un GOSUB se introduce en la pila la dirección desde la que se ha llamado, y cuando encuentra el RETURN la saca de la pila y salta a la línea siguiente. De esta forma si encuentra varios GOSUB seguidos, introduce las direcciones en la pila, y luego siempre sabe a donde regresar con los RETURN conforme los encuentra. En los lenguajes modernos se usan mucho las pilas para pasar los parámetros de las funciones en las llamadas.
Hay una forma sencilla de crear una pila usando un arreglo y una variable que haga de puntero a la cima. Se inicia el puntero a cero, cuando se añade un elemento se incrementa el puntero y se añade en la posición del arreglo a la que apunta, si se solicita un elemento se leer de la posición apuntada y luego se resta uno. Si el apuntador es cero la pila está vacía. Esta técnica solo requiere saber de antemano el tamaño máximo de la pila, lo que no siempre es posible, pero funciona en cualquier versión del BASIC. En SuperBASIC es sencillo, al existir el elemento cero del arreglo lo usaré para guardar el puntero a la cima. Creo varias funciones para su manejo, una que inicia la pila con un tamaño por defecto, otra que la crea con un tamaño inicial, uno que nos indica si la pila está vacía, la que introduce un valor (en inglés PUSH) y hace crecer el tamaño de la pila si es necesario, la que lee un valor (en inglés POP), una para compactar la pila y reducir su tamaño al mínimo, y una ultima para cambiar el tamaño de la pila, tanto hacia arriba como hacia abajo.
6150 REMark -------------------------------------------------------------- 6160 REMark -- PILA_CREAR -> Crea la pila -- 6170 REMark -------------------------------------------------------------- 6180 DEFine PROCedure PILA_CREAR 6190 REMark Espacio minimo en la pila 6200 LET PILA_FACTOR = 10 6210 DIM ArrPila(PILA_FACTOR) 6220 END DEFine 6230 : 6240 REMark -------------------------------------------------------------- 6250 REMark -- PILA_NUEVA(tam) -> Crea la pila con un tama‰o -- 6260 REMark -------------------------------------------------------------- 6270 DEFine PROCedure PILA_NUEVA(tam) 6280 LET PILA_FACTOR = tam 6290 DIM ArrPila(tam) 6300 END DEFine 6310 : 6320 REMark -------------------------------------------------------------- 6330 REMark -- b = PILA_VACIA -> Ver si la pila esta vacia -- 6340 REMark -- RETORNA: Booleano (Si, No) -- 6350 REMark -------------------------------------------------------------- 6360 DEFine FuNction PILA_VACIA 6370 RETurn NOT ArrPila(0) 6380 END DEFine 6390 : 6400 REMark -------------------------------------------------------------- 6410 REMark -- PILA_PUSH(dato) -> Introduce un dato en la pila, si -- 6420 REMark -- esta llena crece al doble -- 6430 REMark -------------------------------------------------------------- 6440 DEFine PROCedure PILA_PUSH(dato) 6450 IF ArrPila(0) = DIMN(ArrPila) THEN 6460 PILA_CAMBIA(ArrPila(0)*2) 6470 END IF 6480 ArrPila(0)=ArrPila(0)+1 6490 ArrPila(ArrPila(0))=dato 6500 END DEFine 6510 : 6520 REMark -------------------------------------------------------------- 6530 REMark -- v = PILA_POP -> Saca un dato de la pila -- 6540 REMark -- RETORNA: Valor de la cima de la pila -- 6550 REMark -------------------------------------------------------------- 6560 DEFine FuNction PILA_POP 6570 IF PILA_VACIA THEN 6580 PRINT"Error: Pila vacia" 6590 STOP 6600 END IF 6610 ArrPila(0)=ArrPila(0)-1 6620 RETurn ArrPila(ArrPila(0)+1) 6630 END DEFine 6640 : 6650 REMark -------------------------------------------------------------- 6660 REMark -- PILA_COMPACTA -> Compacta la pila -- 6670 REMark -------------------------------------------------------------- 6680 DEFine PROCedure PILA_COMPACTA 6690 PILA_CAMBIA(ArrPila(0)+PILA_FACTOR) 6700 END DEFine 6710 : 6720 REMark -------------------------------------------------------------- 6730 REMark -- PILA_CAMBIAR -> Cambia el tamaño de la pila -- 6740 REMark -------------------------------------------------------------- 6750 DEFine PROCedure PILA_CAMBIA(tam) 6760 LOCal b(tam),i 6770 : 6780 FOR i=0 TO tam 6790 IF i > DIMN(ArrPila) THEN EXIT i 6800 b(i)=ArrPila(i) 6810 END FOR i 6820 IF tam < ArrPila(0) THEN tam=ArrPila(0)+PILA_FACTOR 6830 IF tam < PILA_FACTOR THEN tam=tam+PILA_FACTOR 6840 DIM ArrPila(tam) 6850 FOR i=0 TO tam : ArrPila(i)=b(i) 6860 END DEFine
La línea 6460 es la que permite hacer crecer la pila si se llena. Hay varias técnica posibles para fijar el tamaño en que se aumentar la pila automáticamente:
- La mas sencilla es usar in incremento fijo, de forma que cada vez que se llene se aumente su tamaño en ese valor. Funciona si la pila crece pocas veces y en poca cantidad cada vez. Se usa la fórmula Nuevo_Tamaño = Anterior_Tamaño + Cantidad. Si elegimos 10 aumenta en forma de 10, 20, 30, 40, 50, 60, 70...
- Una muy usada es incrementar en un porcentaje del tamaño, de esta forma conforme mas crece el tamaño se va adaptando. Se usa la fórmula Nuevo_Tamaño = Anterior_Tamaño + (Anterior_Tamaño * Porcentaje / 100), si elegimos porcentaje del 50% el crecimiento es 10, 15, 23, 35, 53, 80, 120,...
- El crecimiento exponencial es sencillo y efectivo, igual que el porcentual intenta crecer mas cuanto mas grande sea el tamaño inicial, se basa en multiplicar el tamaño por un factor, de forma que aumenta mas rápido que usando el porcentual, aunque hay que usarlo con cuidado ya que el tamaño crece muy rápido, pero es bueno si hay pocas ampliaciones. Se usa la fórmula Nuevo_Tamaño = Anterior_Tamaño * Factor. En mi rutina uso el factor 2 que es bueno para crecer en un factor 10, 20, 40, 80, 160, 320, 640...
Veamos un uso práctico de la pila, escribiré el algoritmo QuickSort para que en lugar de ser recursivo use la pila para ir guardando inicio y fin de las sublistas, y así cambio el proceso por uno iterativo.
ALGORITMO QuickSort_Pila (arreglo, primero, ultimo)
Pila.Push(primero, ultimo)
REPETIR
Pila.Pop(primero, ultimo)
REPETIR
izquierda ← primero
derecha ← ultimo
pivote ← ENTERO((primero + ultimo)/2))
REPETIR
MIENTRAS arreglo(izquierda) < arreglo(pivote)
izquierda ← izquierda + 1
FIN_MIENTRAS
MIENTRAS arreglo(derecha) > arreglo(pivote) do
derecha ← derecha - 1
FIN_MIENTRAS
SI izquierda <= derecha ENTONCES
SI izquierda <> derecha ENTONCES
INTERCAMBIA_ELEMENTOS(izquierda, derecha)
FIN_SI
izquierda ← izquierda + 1
derecha ← derecha - 1
FIN_SI
HASTA_QUE izquierda >= derecha
SI derecha - primero > ultimo - izquierda ENTONCES
SI primero < derecha ENTONCES
Pila.Push(primero, derecha)
FIN_SI
primero ← izquierda
SI NO
SI izquierda < ultimo ENTONCES
Pila.Push(izquierda, ultimo)
FIN_SI
ultimo ← derecha
FIN_SI
HASTA_QUE primero >= ultimo
HASTA_QUE Pila.Vacia
Esto se traduce muy sencillo a superBASIC, solo hay que tomar nuestra rutina QuickSort y añadirle primero la creación de la pila, introducimos en ella como inicio comienzo y fin, cambiamos la llamada recursiva por introducir inicio y fin de la sublista en la pila, y seguir iterando hasta que la pila quede vacía.
100 DEFine PROCedure Rapida_Pila (arreglo,sentido,primero,ultimo) 110 IF ultimo=0 THEN ultimo=DIMN(arreglo) 120 QsortP arreglo, sentido, primero, ultimo 130 END DEFine 140 : 150 DEFine PROCedure QsortP (arreglo,sentido,primero,ultimo) 160 LOCal rep_pila,pivote,izquierda,derecha,r1,r2,r3 170 : 180 PILA_CREAR 190 PILA_PUSH primero : PILA_PUSH ultimo 200 REPeat rep_pila 210 : 220 REMark Sacamos en orden inverso al introducido 230 ultimo = PILA_POP : primero = PILA_POP 240 : 250 IF (primero+1 = ultimo) THEN 260 IF COMPARA(arreglo(primero),arreglo(ultimo),sentido) = 1 THEN 270 SWAP arreglo(primero),arreglo(ultimo) 280 END IF 290 ELSE 300 izquierda = primero 310 derecha = ultimo 320 pivote = INT((primero + ultimo) / 2) 330 : 340 REPeat r1 350 IF (izquierda > pivote) OR (derecha < pivote) THEN EXIT r1 360 REPeat r2 370 IF (izquierda > pivote) THEN EXIT r2 380 IF COMPARA(arreglo(izquierda),arreglo(pivote),sentido)<>-1 390 EXIT r2 400 END IF 410 izquierda = izquierda + 1 420 END REPeat r2 430 REPeat r3 440 IF (derecha < pivote) THEN EXIT r3 450 IF COMPARA(arreglo(derecha),arreglo(pivote),sentido)<>1 460 EXIT r3 470 END IF 480 derecha = derecha - 1 490 END REPeat r3 500 SWAP arreglo(izquierda), arreglo(derecha) 510 izquierda = izquierda + 1 520 derecha = derecha - 1 530 IF (izquierda - 1) = pivote THEN 540 derecha = derecha + 1 550 pivote = derecha 560 ELSE IF (derecha + 1) = pivote THEN 570 izquierda = izquierda - 1 580 pivote = izquierda 590 END IF 600 END REPeat r1 610 IF (primero < pivote-1) THEN 620 PILA_PUSH primero : PILA_PUSH pivote-1 630 END IF 640 IF (ultimo > pivote+1) THEN 650 PILA_PUSH pivote+1 : PILA_PUSH ultimo 660 END IF 670 END IF 680 IF PILA_VACIA THEN EXIT rep_pila 690 END REPeat rep_pila 700 END DEFine
No hay comentarios:
Publicar un comentario