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...
La rutina
PILA_CAMBIA es la que permite cambiar el tamaño del arreglo. Como SuperBASIC
no permite ampliar el arreglo de manera estándar, es necesario crear un arreglo temporal, copiar la pila en el, cambiar el tamaño de la pila, y volver a copiar el temporal a la pila. Esto cuesta un tiempo, por eso hay que buscar un tamaño de incremento adecuado.
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
