Pilas

📖 Teoría

📖

Una Pila es un TAD lineal de tipo LIFO, lo que quiere decir es que es una lista cuyas operaciones han sido restringidas a solo unas pocas que permitan añadir (apilar) y sacar (desapilar) elementos desde el mismo extremo de la lista

En una pila, la inserción (apilar) y extracción (desapilar) de elementos de la estructura se realiza desde el mismo lado de la lista de manera eficiente: $O(1)$

Es una estructura de tipo LIFO (Last In First Out), por lo que el ultimo elemento en ser insertado (apilado) en la estructura será en primero en ser extraido (desapilado). Osea, los elementos se extraen en orden inverso al que se introducen

Especificación Algebraica de una Pila

Parámetros Genéricos
TElemento

Tipos
TPila

Operaciones
Constructoras generadoras
crearPilaVacia → TPila
apilar: TPila X TElemento → TPila
Observadoras selectoras
(PARCIAL) cima: TPila → TElemento
(PARCIAL) desapilar: TPila → TPila
Observadoras no selectoras
esPilaVacia: TPila → boolean
Constructoras Generadoras
copiar: TPila → TPila
destruir: TPila → TPila

Variables
p , p<N> , pila → TPila
e , e<N> → TElemento

Ecuaciones de definitud
DEF ( cima( apilar(p, e) ) )
DEF ( desapilar( apilar(p, e) ) )

Ecuaciones
Observadoras selectoras
cima( apilar(p, e) ) = e
desapilar( apilar(p, e) ) = p
Observadoras no selectoras
esPilaVacia
esPilaVacia( crearPilaVacia ) = True
esPilaVacia( apilar(p, e) ) = False
Constructoras no generadoras
copiar
copiar( crearPilaVacia ) = crearPilaVacia
copiar( apilar(p, e) ) = apilar(copiar(l), e)
destruir
destruir( crearPilaVacia ) = crearPilaVacia
destruir( apilar(p, e) ) = destruir(p)

⚙️ Implementación

💡

Implementaciones de listas válidas

Desde el pincipio
Todas las implementaciones de listas son válidas para pilas

Desde el final
Circular estática

Interface

unit uPila;
    
interface
    
    uses uElemento;

    type
        TNodo = RECORD
            info:TElemento;
            sig:^TNodo;
        END;
        TPila = ^TNodo;  

	
	procedure crearPilaVacia(var p:TPila);   
	function esVacia(p:TPila):boolean; 
	procedure apilar(var p:TPila; e:TElemento);
	procedure despilar(var p:TPila; var e:TElemento); 
	procedure mostrarPila(p:TPila);
	
implementation
	
	// ...

end.

Implemetation

Apilar

Añade un elemento nuevo a la pila

procedure apilar(var p:TPila; e:TElemento); 
var aux:^TNodo;
begin
    new(aux);
    copiarElemento(aux^.info, e);
    aux^.sig := p;
    p := aux;
end;

Cima
Consulta el primero elemento de la pila, sin sacarlo
procedure cima(var e:TElemento; p:TPila); begin
   if not Esvacia(p) then copiarElemento(e, p^.info);
end;

Desapilar

Saca un nodo de la pila y lo devuelve como parámetro

procedure despilar(var p:TPila; var e:TElemento); 
var aux:^TNodo;
begin
   if not Esvacia(p) then begin
		copiarElemento(e, p^.info);
    aux := p;
    p:= p^.sig;
    dispose(aux);
	end;
end;

EsPilaVacia
Comprueba si una pila está vacía
function esPilaVacia(p:TPila):boolean; begin 
    esVacia := (p = nil);         
end;

CrearPilaVacia
Pone la referencia de la lista recivida apuintando a NIL
procedure crearPilaVacia(var p:TPila); begin
		p := NIL;
end;

CopiarPila

Crear una copiar de los nodos de un pila en otra pila

procedure copiarPila(var pdest:TPila; psrc:TPila); 
var auxe:TElemento;
begin
		if esPilaVacia(p) then pdest := NIL
		else begin
			copiarPila(pdest, psrc);
			cima(auxe, psrc);
			apilar(pdest, auxe);
		end;
end;