CLASE-PILAS:
UNA PILA ES UN TIPO ESPECIAL DE
LISTA ABIERTA EN LA QUE SÓLO SE PUEDEN INSERTAR Y ELIMINAR NODOS EN UNO DE LOS
EXTREMOS DE LA LISTA. ESTAS OPERACIONES SE CONOCEN COMO "PUSH" Y
"POP", RESPECTIVAMENTE "EMPUJAR" Y "TIRAR".
ADEMÁS, LAS ESCRITURAS DE DATOS SIEMPRE SON INSERCIONES DE NODOS, Y LAS
LECTURAS SIEMPRE ELIMINAN EL NODO LEÍDO.
UNA PILA (STACK
EN INGLÉS) ES UNA LISTA ORDINAL O ESTRUCTURA DE DATOS EN LA QUE EL MODO DE
ACCESO A SUS ELEMENTOS ES DE TIPO LIFO (DEL INGLÉS LAST IN FIRST OUT, ÚLTIMO EN
ENTRAR, PRIMERO EN SALIR) QUE PERMITE ALMACENAR Y RECUPERAR DATOS. ESTA
ESTRUCTURA SE APLICA EN MULTITUD DE OCASIONES EN EL ÁREA DE INFORMÁTICA DEBIDO
A SU SIMPLICIDAD Y ORDENACIÓN IMPLÍCITA DE LA PROPIA ESTRUCTURA.
PARA EL MANEJO DE LOS DATOS SE
CUENTA CON DOS OPERACIONES BÁSICAS: APILAR (PUSH), QUE COLOCA UN OBJETO EN LA
PILA, Y SU OPERACIÓN INVERSA, RETIRAR (O DESAPILAR, POP), QUE RETIRA EL ÚLTIMO
ELEMENTO APILADO.
EN CADA MOMENTO SÓLO SE TIENE
ACCESO A LA PARTE SUPERIOR DE LA PILA, ES DECIR, AL ÚLTIMO OBJETO APILADO
(DENOMINADO TOS, TOP OF STACK EN INGLÉS). LA OPERACIÓN RETIRAR PERMITE LA
OBTENCIÓN DE ESTE ELEMENTO, QUE ES RETIRADO DE LA PILA PERMITIENDO EL ACCESO AL
SIGUIENTE (APILADO CON ANTERIORIDAD), QUE PASA A SER EL NUEVO TOS.
LA PILA ES UNA LISTA DE
ELEMENTOS CARACTERIZADA PORQUE LAS OPERACIONES DE INSERCIÓN Y ELIMINACIÓN DE
ELEMENTOS SE REALIZAN SOLAMENTE EN UN EXTREMO DE LA ESTRUCTURA. EL EXTREMO
DONDE SE REALIZAN ESTAS OPERACIONES SE DENOMINA HABITUALMENTE CIMA (TOP EN LA
NOMENCLATURA INGLESA). DADA UNA PILA P, FORMADA POR LOS ELEMENTOS A, B, C, ...,
K (P=(A,B,C,...,K)), SE DICE QUE A, QUE ES EL ELEMENTO MÁS INACCESIBLE DE LA
PILA, ESTÁ EN EL FONDO DE LA PILA (BOTTOM) Y QUE K, POR EL CONTRARIO, EL MÁS
ACCESIBLE, ESTÁ EN LA CIMA (TOP).
LAS RESTRICCIONES DEFINIDAS PARA
LA PILA IMPLICAN QUE SI UNA SERIE DE ELEMENTOS A, B, C, D, E, F SE AÑADEN, EN
ESTE ORDEN, A UNA PILA ENTONCES EL PRIMER ELEMENTO QUE SE ELIMINE (BORRE) DE LA
ESTRUCTURA DEBERÁ SER E. POR TANTO, RESULTA QUE EL ÚLTIMO ELEMENTO QUE SE
INSERTA EN UNA PILA ES EL PRIMERO QUE SE BORRA. POR ESA RAZÓN, SE DICE QUE UNA
PILA ES UNA LISTA O ESTRUCTURA LINEAL DE TIPO LIFO (LAST IN FIRST OUT, EL
ÚLTIMO QUE ENTRA ES EL PRIMERO QUE SALE).
ESTRUCTURA PILA:
A B C D E F ... ←BORRADO→INSERCIÓN
POR ANALOGÍA
CON OBJETOS COTIDIANOS, UNA OPERACIÓN APILAR EQUIVALDRÍA A COLOCAR UN PLATO
SOBRE UNA PILA DE PLATOS, Y UNA OPERACIÓN RETIRAR A RETIRARLO.
LAS
PILAS SUELEN EMPLEARSE EN LOS SIGUIENTES CONTEXTOS:
• EVALUACIÓN DE EXPRESIONES EN
NOTACIÓN POSTFIJA (NOTACIÓN POLACA INVERSA).
• RECONOCEDORES SINTÁCTICOS DE
LENGUAJES INDEPENDIENTES DEL CONTEXTO
• IMPLEMENTACIÓN DE RECURSIVIDAD.
ESTAS CARACTERÍSTICAS IMPLICAN
UN COMPORTAMIENTO DE LISTA LIFO (LAST IN FIRST OUT), EL ÚLTIMO EN ENTRAR ES EL
PRIMERO EN SALIR.
EL SÍMIL DEL QUE DERIVA EL
NOMBRE DE LA ESTRUCTURA ES UNA PILA DE PLATOS. SÓLO ES POSIBLE AÑADIR PLATOS EN
LA PARTE SUPERIOR DE LA PILA, Y SÓLO PUEDEN TOMARSE DEL MISMO EXTREMO.
EL NODO TÍPICO PARA CONSTRUIR
PILAS ES EL MISMO QUE VIMOS EN EL CAPÍTULO ANTERIOR PARA LA CONSTRUCCIÓN DE
LISTAS:
struct nodo \{
int
dato;
struct nodo *siguiente;
};
DECLARACIONES DE TIPOS PARA MANEJAR PILAS EN C:
LOS TIPOS QUE
DEFINIREMOS NORMALMENTE PARA MANEJAR PILAS SERÁN CASI LOS MISMOS QUE PARA
MANEJAR LISTAS, TAN SÓLO CAMBIAREMOS ALGUNOS NOMBRES:
typedef struct _nodo \{
int
dato;
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;
TIPONODO
ES EL TIPO PARA DECLARAR NODOS, EVIDENTEMENTE.
PNODO
ES EL TIPO PARA DECLARAR PUNTEROS A UN NODO.
PILA
ES EL TIPO PARA DECLARAR PILAS.
ES EVIDENTE, A LA VISTA DEL GRÁFICO, QUE UNA
PILA ES UNA LISTA ABIERTA. ASÍ QUE SIGUE SIENDO MUY IMPORTANTE QUE NUESTRO
PROGRAMA NUNCA PIERDA EL VALOR DEL PUNTERO AL PRIMER ELEMENTO, IGUAL QUE PASA
CON LAS LISTAS ABIERTAS.
TENIENDO EN CUENTA QUE LAS
INSERCIONES Y BORRADOS EN UNA PILA SE HACEN SIEMPRE EN UN EXTREMO, LO QUE
CONSIDERAMOS COMO EL PRIMER ELEMENTO DE LA LISTA ES EN REALIDAD EL ÚLTIMO
ELEMENTO DE LA PILA.
PILA COMO TIPO ABSTRACTO DE DATOS:
A MODO DE RESUMEN TIPO DE DATOS,
LA PILA ES UN CONTENEDOR DE NODOS Y TIENE DOS OPERACIONES BÁSICAS: PUSH (O
APILAR) Y POP (O DESAPILAR). 'PUSH' AÑADE UN NODO A LA PARTE SUPERIOR DE LA
PILA, DEJANDO POR DEBAJO EL RESTO DE LOS NODOS. 'POP' ELIMINA Y DEVUELVE EL
ACTUAL NODO SUPERIOR DE LA PILA. UNA METÁFORA QUE SE UTILIZA CON FRECUENCIA ES
LA IDEA DE UNA PILA DE PLATOS EN UNA CAFETERÍA CON MUELLE DE PILA. EN ESA
SERIE, SÓLO LA PRIMERA PLACA ES VISIBLE Y ACCESIBLE PARA EL USUARIO, TODAS LAS
DEMÁS PLACAS PERMANECEN OCULTAS. COMO SE AÑADEN LAS NUEVAS PLACAS, CADA NUEVA
PLACA SE CONVIERTE EN LA PARTE SUPERIOR DE LA PILA, ESCONDIDOS DEBAJO DE CADA
PLATO, EMPUJANDO A LA PILA DE PLACAS. A MEDIDA QUE LA PLACA SUPERIOR SE ELIMINA
DE LA PILA, LA SEGUNDA PLACA SE CONVIERTE EN LA PARTE SUPERIOR DE LA PILA. DOS
PRINCIPIOS IMPORTANTES SON ILUSTRADOS POR ESTA METÁFORA: EN PRIMER LUGAR LA
ÚLTIMA SALIDA ES UN PRINCIPIO, LA SEGUNDA ES QUE EL CONTENIDO DE LA PILA ESTÁ
OCULTO. SÓLO LA PLACA DE LA PARTE SUPERIOR ES VISIBLE, POR LO QUE PARA VER LO
QUE HAY EN LA TERCERA PLACA, EL PRIMER Y SEGUNDO PLATOS TENDRÁN QUE SER
RETIRADOS.
OPERACIONES:
UNA PILA CUENTA CON 2
OPERACIONES IMPRESCINDIBLES: APILAR Y DESAPILAR, A LAS QUE EN LAS
IMPLEMENTACIONES MODERNAS DE LAS PILAS SE SUELEN AÑADIR MÁS DE USO HABITUAL.
• CREAR: SE CREA LA PILA VACÍA.
(CONSTRUCTOR)
• TAMAÑO: REGRESA EL NUMERO DE
ELEMENTOS DE LA PILA. (SIZE)
• APILAR: SE AÑADE UN ELEMENTO A LA
PILA.(PUSH)
• DESAPILAR: SE ELIMINA EL ELEMENTO
FRONTAL DE LA PILA.(POP)
• CIMA: DEVUELVE EL ELEMENTO QUE
ESTA EN LA CIMA DE LA PILA. (TOP O PEEK)
• VACÍA: DEVUELVE CIERTO SI LA PILA
ESTÁ VACÍA O FALSO EN CASO CONTRARIO (EMPTY).
OPERACIÓN CREAR_PILA
LA CREACIÓN DE
LA PILA SE REALIZARÁ MEDIANTE EL CONSTRUCTOR POR DEFECTO. LA TAREA QUE DEBERÁ
REALIZAR SERÁ DECIR QUE NO EXISTEN ELEMENTOS EN LA PILA:
stack: Pila
stack.Cima ← 0
En C++:
٭
Pila::Pila (void)
{
cima = 0;
}
OPERACIÓN PILA_VACIA:
• ESTA
OPERACIÓN PERMITIRÁ DETERMINAR SI ES POSIBLE ELIMINAR ELEMENTOS.
• LA
PILA ESTARÁ VACIA SI LA CIMA ESTÁ APUNTANDO AL VALOR CERO.
ALGORITMO PILA_VACIA
Entrada
stack: Pila
Salida
(CIERTO, FALSO)
Inicio
Si ( stack.Cima = 0 ) entonces
Devolver ( CIERTO )
Sino
Devolver ( FALSO )
Fin_si
Fin
٭
bool Pila::PilaVacia (void)
{
return cima == 0;
}
OPERACIÓN DE INSERCIÓN DE INFORMACIÓN (APILAR):
LA OPERACIÓN DE
INSERCIÓN NORMALMENTE SE CONOCE POR SU NOMBRE INGLÉS PUSH, O APILAR. LA
OPERACIÓN APLICADA SOBRE UN PILA Y UN VALOR X, INSERTA X EN LA CIMA DE LA PILA.
ESTA OPERACIÓN ESTÁ RESTRINGIDA POR EL TIPO DE REPRESENTACIÓN ESCOGIDO. EN ESTE
CASO, LA UTILIZACIÓN DE UN ARRAY IMPLICA QUE SE TIENE UN NÚMERO MÁXIMO DE
POSIBLES ELEMENTOS EN LA PILA, POR LO TANTO, ES NECESARIO COMPROBAR,
PREVIAMENTE A LA INSERCIÓN, QUE REALMENTE HAY ESPACIO EN LA ESTRUCTURA PARA
ALMACENAR UN NUEVO ELEMENTO. CON ESTA CONSIDERACIÓN, EL ALGORITMO DE INSERCIÓN
SERÍA:
bool Pila::Apilar (Valor x)
{
bool error;
if (cima == MAX)
error = true;
else
{
error = false;
info[cima] = x;
cima++;
}
return error;
}
OPERACIÓN DE CONSULTA DE INFORMACIÓN (CIMA_PILA):
LA OPERACIÓN DE
CONSULTA DE LA INFORMACIÓN, SÓLO PUEDE ACCEDER AL ELEMENTO QUE ESTÉ SITUADO EN
LA CIMA DE LA PILA, Y PROPORCIONAR SU VALOR. EL ALGORITMO SE LIMITARÁ A
DEVOLVER EL ELEMENTO QUE ESTÁ SITUADO EN LA POSICIÓN CIMA DE LA PILA, SI EXISTE
INFORMACIÓN ALMACENADA EN LA PILA.
bool Pila::CimaPila (Valor & x)
{
bool error;
if (cima == 0)
error = true;
else
{
error = false;
x = info[cima - 1];
}
return error;
}
OPERACIÓN DE ELIMINACIÓN DE INFORMACIÓN
(DESAPILAR):
LA OPERACIÓN DE
BORRADO ELIMINA DE LA ESTRUCTURA EL ELEMENTO SITUADO EN LA CIMA.
NORMALMENTERECIBE EL NOMBRE DE POP EN LA BIBLIOGRAFÍA INGLESA. EL ALGORITMO DE
BORRADO SERÍA:
bool Pila::Desapilar (void)
{
bool error;
if (cima == 0)
error = true;
else
{
error = false;
cima--;
}
return error;
}
IMPLEMENTACIÓN:
UN REQUISITO
TÍPICO DE ALMACENAMIENTO DE UNA PILA DE N ELEMENTOS ES O(N). EL REQUISITO
TÍPICO DE TIEMPO DE O(1) LAS OPERACIONES TAMBIÉN SON FÁCILES DE SATISFACER CON
UN ARRAY O CON LISTAS ENLAZADAS SIMPLES.
LA BIBLIOTECA DE PLANTILLAS DE
C++ ESTÁNDAR PROPORCIONA UNA "PILA" CLASE TEMPLATED QUE SE LIMITA A
SÓLO APILAR/DESAPILAR OPERACIONES. JAVA CONTIENE UNA BIBLIOTECA DE LA CLASE
PILA QUE ES UNA ESPECIALIZACIÓN DE VECTOR. ESTO PODRÍA SER CONSIDERADO COMO UN
DEFECTO, PORQUE EL DISEÑO HEREDADO GET () DE VECTOR MÉTODO LIFO IGNORA LA LIMITACIÓN DE LA PILA.
IMPLEMENTACIÓN MEDIANTE CURSORES:
IMPLEMENTACIÓN
MEDIANTE ESTRUCTURAS DINÁMICAS
UNO DE LOS MAYORES PROBLEMAS EN
LA UTILIZACIÓN DE ESTRUCTURAS ESTÁTICAS, ESTRIBA EN EL HECHO DE TENER QUE
DETERMINAR, EN EL MOMENTO DE LA REALIZACIÓN DEL PROGRAMA, EL VALOR MÁXIMO DE
ELEMENTOS QUE VA A PODER CONTENER LA ESTRUCTURA.
UNA POSIBLE SOLUCIÓN A ESTE
PROBLEMA ES LA UTILIZACIÓN DE ESTRUCTURAS DINÁMICAS ENLAZADAS (UTILIZACIÓN DE
PUNTEROS) TAL Y COMO SE EXPLICÓ EN EL PRIMER CUATRIMESTRE. POR TANTO, LA CLASE
PILA CONTENDRÁ, EN ESTA IMPLEMENTACIÓN, LA SIGUIENTE PARTE PRIVADA:
class Pila
{
public: ...
private:
Puntero cima;
};
Donde Puntero será:
typedef struct Nodo * Puntero;
Y el tipo Nodo será:
struct Nodo
{
Valor info;
Puntero sig;
};
IMPLEMENTACIÓN EN PYTHON:
class Stack(object):
def
__init__(self):
self.stack_pointer = None
def
push(self, element):
self.stack_pointer = Node(element, self.stack_pointer)
def
pop(self):
e = self.stack_pointer.element
self.stack_pointer = self.stack_pointer.next
return e
def
peek(self):
return self.stack_pointer.element
def
__len__(self):
i = 0
sp = self.stack_pointer
while sp:
i += 1
sp = sp.next
return i
class Node(object):
def
__init__(self, element=None, next=None):
self.element = element
self.next = next
if __name__ == '__main__':
#
small use example
s =
Stack()
for
i in range(10):s.push(i)
for
i in range(len(s)):print(s.pop())
IMPLEMENTACIÓN EN MAUDE:
LA PILANV ES LA
PILA NO VACÍA, QUE DIFERENCIAMOS DE LA PILA NORMAL A LA HORA DE TOMAR EN CUENTA
ERRORES. EL ELEMENTO X REPRESENTA EL TIPO DE VALOR QUE PUEDE CONTENER LA PILA:
ENTERO, CARÁCTER, REGISTRO, ETC.
fmod PILA-GENÉRICA {X :: TRIV} is
sorts
Pila{X} PilaNV{X}.
subsorts PilaNV{X} < Pila{X}.
***generadores:
op
crear: -> Pila {X} [ctor].
op
apilar : X$Elt Pila{X} -> PilaNV{X} [ctor].
***constructores
op
desapilar : Pila{X} -> Pila{X}.
***selectores
op
cima : PilaNV{X} -> X$Elt.
***variables
var
P : Pila{X}.
var
E : X$Elt.
***ecuaciones
eq
desapilar (crear) = crear.
eq
desapilar(apilar(E, P)) = P.
eq
cima(apilar(E, P)) = E.
endfm
IMPLEMENTACIÓN EN VISUAL BASIC:
Public Class Stack
Private p_index As Integer
Private list As New ArrayList
Public Sub New()
p_index = -1
End
Sub
ReadOnly Property count
Get
Return list.Count
End Get
End
Property
Public Sub push(ByVal value As Object)
list.Add(value)
p_index += 1
End
Sub
Public Function pop() As Object
Dim obj As Object = list.Item(p_index)
list.RemoveAt(p_index)
p_index -= 1
Return obj
End
Function
Public Sub clear()
list.Clear()
p_index = -1
End
Sub
Public Function peek() As Object
Return list.Item(p_index)
End
Function
End Class
EN C++:
#ifndef PILA
#define PILA // define la pila
template <class T>
class Pila {
private:
struct Nodo {
T elemento;
Nodo* siguiente; // coloca el
nodo en la segunda posicion
}*
ultimo;
unsigned int elementos;
public:
Pila() {
elementos = 0;
}
~Pila() {
while (elementos != 0) pop();
}
void
push(const T& elem) {
Nodo* aux = new Nodo;
aux->elemento = elem;
aux->siguiente = ultimo;
ultimo = aux;
++elementos;
}
void
pop() {
Nodo* aux = ultimo;
ultimo = ultimo->siguiente;
delete aux;
--elementos;
}
T
cima() const {
return ultimo->elemento;
}
bool
vacia() const {
return elementos == 0;
}
unsigned int altura() const {
return elementos;
}
};
#endif
ESTRUCTURAS DE DATOS RELACIONADAS:
EL TIPO BASE DE
LA ESTRUCTURA FIFO (EL PRIMERO EN ENTRAR ES EL PRIMERO EN SALIR)ES LA COLA, Y
LA COMBINACIÓN DE LAS OPERACIONES DE LA PILA Y LA COLA ES PROPORCIONADO POR EL
DEQUE. POR EJEMPLO, EL CAMBIO DE UNA PILA EN UNA COLA EN UN ALGORITMO DE
BÚSQUEDA PUEDE CAMBIAR EL ALGORITMO DE BÚSQUEDA EN PRIMERA PROFUNDIDAD (EN
INGLÉS, DFS) POR UNA BÚSQUEDA EN AMPLITUD (EN INGLÉS, BFS). UNA PILA ACOTADA ES
UNA PILA LIMITADA A UN TAMAÑO MÁXIMO IMPUESTO EN SU ESPECIFICACIÓN.
ARQUITECTURA BÁSICA DE UNA PILA:
UNA PILA TÍPICA
ES UN ÁREA DE LA MEMORIA DE LOS COMPUTADORES CON UN ORIGEN FIJO Y UN TAMAÑO
VARIABLE. AL PRINCIPIO, EL TAMAÑO DE LA PILA ES CERO. UN PUNTERO DE PILA, POR
LO GENERAL EN FORMA DE UN REGISTRO DE HARDWARE, APUNTA A LA MÁS RECIENTE
LOCALIZACIÓN EN LA PILA; CUANDO LA PILA TIENE UN TAMAÑO DE CERO, EL PUNTERO DE
PILA DE PUNTOS EN EL ORIGEN DE LA PILA.
LAS DOS OPERACIONES APLICABLES A TODAS LAS PILAS SON:
• UNA OPERACIÓN APILAR, EN EL QUE UN
ELEMENTO DE DATOS SE COLOCA EN EL LUGAR APUNTADO POR EL PUNTERO DE PILA, Y LA
DIRECCIÓN EN EL PUNTERO DE PILA SE AJUSTA POR EL TAMAÑO DE LOS DATOS DE
PARTIDA.
• UNA OPERACIÓN DESAPILAR: UN
ELEMENTO DE DATOS EN LA UBICACIÓN ACTUAL APUNTADO POR EL PUNTERO DE PILA ES
ELIMINADO, Y EL PUNTERO DE PILA SE AJUSTA POR EL TAMAÑO DE LOS DATOS DE
PARTIDA.
HAY MUCHAS VARIACIONES EN EL PRINCIPIO BÁSICO DE
LAS OPERACIONES DE PILA. CADA PILA TIENE UN LUGAR FIJO EN LA MEMORIA EN LA QUE
COMIENZA. COMO LOS DATOS SE AÑADIRÁN A LA PILA, EL PUNTERO DE PILA ES
DESPLAZADO PARA INDICAR EL ESTADO ACTUAL DE LA PILA, QUE SE EXPANDE LEJOS DEL
ORIGEN (YA SEA HACIA ARRIBA O HACIA ABAJO, DEPENDIENDO DE LA APLICACIÓN
CONCRETA).
POR EJEMPLO, UNA PILA PUEDE
COMENZAR EN UNA POSICIÓN DE LA MEMORIA DE MIL, Y AMPLIAR POR DEBAJO DE LAS
DIRECCIONES, EN CUYO CASO, LOS NUEVOS DATOS SE ALMACENAN EN LUGARES QUE VAN POR
DEBAJO DE 1000, Y EL PUNTERO DE PILA SE DECREMENTA CADA VEZ QUE UN NUEVO
ELEMENTO SE AGREGA. CUANDO UN TEMA ES ELIMINADO DE LA PILA, EL PUNTERO DE PILA
SE INCREMENTA.
LOS PUNTEROS DE PILA PUEDEN
APUNTAR AL ORIGEN DE UNA PILA O DE UN NÚMERO LIMITADO DE DIRECCIONES, YA SEA
POR ENCIMA O POR DEBAJO DEL ORIGEN (DEPENDIENDO DE LA DIRECCIÓN EN QUE CRECE LA
PILA), SIN EMBARGO EL PUNTERO DE PILA NO PUEDE CRUZAR EL ORIGEN DE LA PILA. EN
OTRAS PALABRAS, SI EL ORIGEN DE LA PILA ESTÁ EN LA DIRECCIÓN 1000 Y LA PILA
CRECE HACIA ABAJO (HACIA LAS DIRECCIONES 999, 998, Y ASÍ SUCESIVAMENTE), EL
PUNTERO DE PILA NUNCA DEBE SER INCREMENTADO MÁS ALLÁ DE 1000 (PARA 1001, 1002,
ETC.) SI UN DESAPILAR OPERACIÓN EN LA PILA HACE QUE EL PUNTERO DE PILA SE DEJE
ATRÁS EL ORIGEN DE LA PILA, UNA PILA SE PRODUCE DESBORDAMIENTO. SI UNA OPERACIÓN DE
APILAR HACE QUE EL PUNTERO DE PILA INCREMENTE O DECREMENTE MÁS ALLÁ DEL MÁXIMO
DE LA PILA, EN UNA PILA SE PRODUCE DESBORDAMIENTO.
LA PILA ES VISUALIZADA YA SEA
CRECIENTE DE ABAJO HACIA ARRIBA (COMO PILAS DEL MUNDO REAL), O, CON EL MÁXIMO
ELEMENTO DE LA PILA EN UNA POSICIÓN FIJA, O CRECIENTE, DE IZQUIERDA A DERECHA,
POR LO QUE EL MÁXIMO ELEMENTO SE CONVIERTE EN EL MÁXIMO A "LA
DERECHA". ESTA VISUALIZACIÓN PUEDE SER INDEPENDIENTE DE LA ESTRUCTURA REAL
DE LA PILA EN LA MEMORIA. ESTO SIGNIFICA QUE ROTAR A LA DERECHA ES MOVER EL
PRIMER ELEMENTO A LA TERCERA POSICIÓN, LA SEGUNDA A LA PRIMERA Y LA TERCERA A
LA SEGUNDA. AQUÍ HAY DOS EQUIVALENTES VISUALIZACIONES DE ESTE PROCESO:
Manzana
Plátano
Plátano
==rotar a la derecha==>
Fresa
Fresa Manzana
Fresa
Manzana
Plátano
==rotar a la izquierda==>
Fresa
Manzana
Plátano
UNA PILA ES NORMALMENTE
REPRESENTADA EN LOS ORDENADORES POR UN BLOQUE DE CELDAS DE MEMORIA, CON LOS
"DE ABAJO" EN UNA UBICACIÓN FIJA, Y EL PUNTERO DE PILA DE LA
DIRECCIÓN ACTUAL DE LA "CIMA" DE CÉLULAS DE LA PILA. EN LA PARTE
SUPERIOR E INFERIOR SE UTILIZA LA TERMINOLOGÍA CON INDEPENDENCIA DE QUE LA PILA
CRECE REALMENTE A LA BAJA DE DIRECCIONES DE MEMORIA O DIRECCIONES DE MEMORIA
HACIA MAYORES.
APILANDO UN ELEMENTO EN LA
PILA,SE AJUSTA EL PUNTERO DE PILA POR EL TAMAÑO DE ELEMENTOS (YA SEA
DECREMENTAR O INCREMENTAR, EN FUNCIÓN DE LA DIRECCIÓN EN QUE CRECE LA PILA EN
LA MEMORIA), QUE APUNTA A LA PRÓXIMA CELDA, Y COPIA EL NUEVO ELEMENTO DE LA
CIMA EN ÁREA DE LA PILA. DEPENDIENDO DE NUEVO SOBRE LA APLICACIÓN EXACTA, AL
FINAL DE UNA OPERACIÓN DE APILAR, EL PUNTERO DE PILA PUEDE SEÑALAR A LA
SIGUIENTE UBICACIÓN NO UTILIZADO EN LA PILA, O TAL VEZ APUNTE AL MÁXIMO
ELEMENTO DE LA PILA. SI LA PILA APUNTA AL MÁXIMO ELEMENTO DE LA PILA, EL
PUNTERO DE PILA SE ACTUALIZARÁ ANTES DE QUE UN NUEVO ELEMENTO SE APILE, SI EL PUNTERO
QUE APUNTA A LA PRÓXIMA UBICACIÓN DISPONIBLE EN LA PILA, QUE SE ACTUALIZARÁ
DESPUÉS DE QUE EL MÁXIMO ELEMENTO SE APILE EN LA PILA.
DESAPILANDO ES SIMPLEMENTE LA
INVERSA DE APILAR. EL PRIMER ELEMENTO DE LA PILA ES ELIMINADO Y EL PUNTERO DE
PILA SE ACTUALIZA, EN EL ORDEN OPUESTO DE LA UTILIZADA EN LA OPERACIÓN DE
APILAR.
EXPRESIÓN
DE EVALUACIÓN Y ANÁLISIS SINTÁCTICO:
SE CALCULA
EMPLEANDO LA NOTACIÓN POLACA INVERSA UTILIZANDO UNA ESTRUCTURA DE PILA PARA LOS
POSIBLES VALORES. LAS EXPRESIONES PUEDEN SER REPRESENTADAS EN PREFIJO, INFIJO,
POSTFIJO. LA CONVERSIÓN DE UNA FORMA DE LA EXPRESIÓN A OTRA FORMA NECESITA DE
UNA PILA. MUCHOS COMPILADORES UTILIZAN UNA
PILA PARA ANALIZAR LA SINTAXIS DE LAS EXPRESIONES, BLOQUES DE PROGRAMA, ETC.
ANTES DE TRADUCIR EL CÓDIGO DE BAJO NIVEL. LA MAYORÍA DE LOS LENGUAJES DE
PROGRAMACIÓN SON DE CONTEXTO LIBRE DE LOS IDIOMAS QUE LES PERMITE SER
ANALIZADOS CON MÁQUINAS BASADAS EN LA PILA.
POR EJEMPLO, EL CÁLCULO: ((1 +
2) * 4) + 3, PUEDE SER ANOTADO COMO EN NOTACIÓN POSTFIJA CON LA VENTAJA DE NO
PREVALECER LAS NORMAS Y LOS PARÉNTESIS NECESARIO:
1 2
+ 4 * 3 +
LA
EXPRESIÓN ES EVALUADA DE IZQUIERDA A DERECHA UTILIZANDO UNA PILA:
• APILAR CUANDO SE ENFRENTAN A UN
OPERANDO Y
• DESAFILAR DOS OPERANDOS Y EVALUAR
EL VALOR CUANDO SE ENFRENTAN A UNA OPERACIÓN.
• APILAR EL RESULTADO.
DE
LA SIGUIENTE MANERA (LA PILA SE MUESTRA DESPUÉS DE QUE LA OPERACIÓN SE HAYA
LLEVADO A CABO):
ENTRADA
OPERACIÓN PILA
1 Apilar operando 1
2 Apilar operando 1, 2
+ Añadir 3
4 Apilar operando 3, 4
* Multiplicar 12
3 Apilar operando 12, 3
ALGORITMO PARA EVALUAR EXPRESIONES:
INICIO
LEER LA EXPRESIÓN
MIENTRAS HAYA ELEMENTOS EN LA EXPRESIÓN HACER
OBTENER EL SIGUIENTE ELEMENTO DE LA EXPRESIÓN.
SI(1) EL ELEMENTO ES UN IDENTIFICADOR DE
OPERANDO ENTONCES
APILAR (ELEMENTO)
SINO(1) {* ES UN OPERADOR *}
OP ← NÚMERO DE
OPERANDOS DEL OPERADOR
REPETIR OP VECES
DESAPILAR Y ALMACENAR
FIN_REPETIR
APLICAR EL OPERADOR SOBRE LOS OPERANDOS
DESAPILADOS
APILAR (RESULTADO DE LA OPERACIÓN)
FIN_SI(1)
FIN_MIENTRAS
SI(2) PILA_VACIA ENTONCES
"ERROR. DEMASIADOS OPERADORES"
SINO(2)
SI(3) LA PILA TIENE MÁS DE UN VALOR APILADO
ENTONCES
"ERROR. DEMASIADOS OPERANDOS"
SINO(3)
DEVOLVER ( DESAPILAR )
FIN_SI(3)
FIN_SI(2)
FIN
ESTE ALGORITMO PLASMADO EN CÓDIGO C++ SERÍA:
٭
int Evaluar (Expresion exp)
{
Pila s;
int res;
Elemento token, e1_aux, e2_aux;
while (!exp.ExpresionVacia() )
{
token = exp.SigElemento ();
if (token.EsOperando() )
s.Apilar (token);
else
{
s.CimaPila (e1_aux);
s.Desapilar ();
s.CimaPila (e2_aux);
s.Desapilar ();
res = token.Operar (e1_aux, e2_aux);
s.Apilar (res);
}
}
if (s.PilaVacia () )
{
res = 0;
cerr << “Error: Demasiados operadores”;
}
else
{
s.CimaPila (res);
s.Desapilar ();
if (!s.PilaVacia() )
cerr << “Error: Demasiados operandos”;
}
return res;
}
{
s.CimaPila (e1_aux);
s.Desapilar ();
s.CimaPila (e2_aux);
s.Desapilar ();
res = token.Operar (e1_aux, e2_aux);
s.Apilar (res);
}
