Tad Pila
Cargado por
BmanTad Pila
Cargado por
BmanESTRUCTURAS DE DATOS
y ALGORITMOS
Licenciatura en Ciencias de la Computacin
Tipo Abstracto de Datos Pila
T.A.D. PILA
Estructuras de Datos y
Algoritmos
PILAS
Las Pilas son secuencias de
elementos que pueden crecer y
contraerse siguiendo la poltica :
Ultimo en Entrar, Primero en Salir
Entre los elementos existe un orden
temporal
Se las suele llamar tambin Listas
LIFO- Last In First Out- , o Listas
ltimo en entrar primero en salir, o
Stack.
Estructuras de Datos y
Algoritmos
T.A.D. PILA Especificacin (1)
Pila: Secuencia de cero o mas elementos de un tipo
determinado que obedece a la poltica LIFO.
P = (a1, a2, ....., an) , n>=0
El orden temporal de inserciones en este conjunto
determina completamente el orden en el cual los
elementos sern recuperados.
a1: primer elemento ingresado.
an: ltimo elemento ingresado, primer elemento a ser
retirado. an es el elemento que se encuentra en el tope
o cima de la pila.
Estructuras de Datos y
Algoritmos
T.A.D. PILA Especificacin (2)
Operaciones Abstractas Sean P: Pila y X:
elemento
NOMBRE ENCABEZADO FUNCION ENTRADA SALIDA
Ingresa el elemento X P=(a1,a2,...,an,X)
Insertar Insertar (P,X) PyX
en la pila P
Si P no est vaca, P=(a1,a2,...an-1) y X= an si
elimina el elemento
Suprimir Suprimir(P,X) P n>0; Error en caso
que fue insertado
mas recientemente contrario
Procesa todos los
Est sujeta al proceso
elementos de P
Recorrer Recorrer(P) P que se realiza sobre
siguiendo la
los elementos de P
poltica LIFO
Crear * Crear(P) Inicializa P P P=( )
Verdadero si P No tiene
Evala si P tiene
Vaca * Vaca(P) P elementos, Falso en
elementos
caso contrario.
Estructuras de Datos y
Algoritmos
T.A.D. PILA Aplicacin (1)
Se desea controlar la correspondencia de
[ / ] , { / } y ( / ) en una expresin
aritmtica, en la que los identificadores de
los operandos estn formados por un solo
carcter
Expresin de Entrada Mensaje de Salida
{[(A-B)*C]^D} CORRESPONDENCIA
{([A-B)*C]^D} ERROR DE CORRESPONDENCI
{([A-B)*C]^D ERROR DE CORRESPONDENCIA
{[A-B)*C]^D} ERROR DE CORRESPONDENCIA
Estructuras de Datos y
Algoritmos
T.A.D. PILA Aplicacin (2)
Recuperar ( Expresin, X )
MIENTRAS (No fin de Expresin) y (No Error)
SI ( X = " [ " X = " { " X = "(" )
ENTONCES
Insertar ( P , X)
FIN SI
SI ( X = "]" X = " }" X = ")" )
ENTONCES
Suprimir (P, aux)
SI (No Error)
ENTONCES
SI (X = " ] " y aux "[" )
(X = " } " y aux "{ " )
(X = " ) " y aux " (" )
ENTONCES
Error
FIN SI
FIN SI
FIN SI
Recuperar ( Expresin, X )
FIN MIENTRAS
SI ( No (Vaca (P)) (Error)
ENTONCES
" ERROR DE CORRESPONDENCIA"
SINO
" CORRESPONDENCIA"
FIN SI
Estructuras de Datos y
Algoritmos
T.A.D. PILA Representacin
Representacin
secuencial
tope
an n-1
n-1
P = (a1, a2, ....., ...
an)
a1 0
items
Estructuras de Datos y
Algoritmos
T.A.D. PILA Representacin (2)
Representacin
encadenada:
P = (a1, a2, .....,
an)
Cant tope
an a1
Estructuras de Datos y
T.A.D. PILA
Algoritmos
Construccin de operaciones abstractas
(1)
class pila int suprimir(void)
{ int *items; { int x;
int tope; if (vacia())
int cant; { printf("%s","Pila vacia");
R
E public: return(0);
P S pila(int xcant=0): }
R E cant(xcant) else
E C
{ tope=-1; { x=items[tope--];
S U
E items=new int[cant]; return(x);
E
N N } }
T C int vacia(void) }
A I { return (tope==-1); void mostrar(void)
C A
} { int i;
I L
int insertar(int x) if (!vacia())
N { { for (i=tope; i>=0; i--)
if (tope<cant-1) { cout<<items[i]<<endl;
{ items[++tope]=x; }
return (x); }
} }
else return (0); };
}
Estructuras de Datos y
T.A.D. PILA Algoritmos
Construccin de operaciones abstractas
(2)
class celda
{
int item;
celda *sig;
public:
R int obteneritem(void)
E
E {
P
R N return(item);
E C }
S A void cargaritem(int xitem)
E D
{
N E
N item=xitem;
T
A }
A
C D void cargarsig(celda* xtope)
I A {
sig=xtope;
N }
celda* obtenersig(void)
{
return(sig);
}
};
Estructuras de Datos y
T.A.D. PILA Algoritmos
Construccin de operaciones abstractas
(3)
class pila
{ int suprimir(void)
int cant; { celda *aux;
celda *tope; int x;
R
E public: if (vacia())
P E pila(celda* xtope=NULL,int xcant=0): { printf("%s","Pila vacia");
R N tope(xtope),cant(xcant) return(0);
E C
{} }
S A
D int vacia(void) else
E
N E { { aux=tope;
T N return (cant==0); x=tope->obteneritem();
A A } tope=tope->obtenersig();
C D
int insertar(int x) cant--;
I A
{ free(aux);
N celda *ps1; return(x);
ps1=new(celda); }
ps1->cargaritem(x); }
ps1->cargarsig(tope);
tope=ps1;
cant++;
return(ps1->obteneritem());
}
