Pilas estatica y dinamicas

Pilas estatica y dinamicas

¿Qué es una Pila?

Imagina un montón de platos "apilados" o bien fichas de dominó formando una torre e intenta eliminar una desde el centro, ¿qué ocurre?, naturalmente esta operación no está permitida si queremos mantener intactos a los platos o a la torre construida. Por esta razón, una pila se asocia a una estructura de datos LIFO (LAST IN FIRST OUT). En base a lo anterior, construye la definición de una PILA y discútela con el profesor.

En general, podemos definir para cada una de las estructuras de datos una representación estática y otra dinámica según el método de asignación de memoria utilizado.

CLASIFICACIÓN

Definición

Pila estática

¿Cómo representar estáticamente una pila?

Sin duda tendremos que utilizar arreglos o registros que como ya sabemos son la base para estructuras de datos más complejas. Considera la siguiente figura:

Vista gráfica

Suponiendo que Dato pertenece a un mismo tipo de datos y CuentaDato corresponde a un entero que se incrementa a medida que un nuevo elemento se incorpora a la pila. Intenta construir la definición de tipo para la estructura Pila.

TYPE

______________________________

______________________________

______________________________

END;

Pila Dinámica

¿Cómo representar dinámicamente una pila?

Sin duda tendremos que utilizar nodos con punteros. Considera la siguiente figura:

Suponiendo que los punteros que aparecen en la figura son capaces de apuntar a un nodo y que Dato pertenece a cualquiera de los tipos básicos o estructurados, la definición de tipo sería:

TYPE

Puntero=^NodoPila;

NodoPila=Record

Info:AlgunTipo;

sgte:Puntero;

End;

Var tope:Puntero;

Operaciones Básicas

• Inicialización

• Verificar si la pila está llena

• Verificar si la pila está vacía

• Empilamiento o PUSH

• Desempilamiento o POP

A continuación presentaremos las operaciones básicas para la representación dinámica de una pila. Haz lo mismo para la estática. Grafica las operaciones a un costado del algoritmo.

procedure InicializaPila(var s: puntero);

begin

s:= nil;

end;

function pilavacia( s: puntero):boolean;

begin

pilavacia:=(s=nil);(La función asume el valor de verdad de la condición*)

end;

function pilallena:boolean;

begin

pilallena:=(sizeof(nodo) >MAXAVAIL);

end;

Donde sizeof(nodo) devuelve el tamaño en bytes que ocupa la estructura del tipo nodo y MAXAVAIL contiene el bloque de tamaño máximo disponible para ser asignado.

procedure push (var s: puntero; nuevoelemento:tipo);

var p:_puntero;

...