empresa

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
Programación en Pascal
Capítulo 23. Pila. (Stack). Tipos de datos abstractos.

23. PILA. (Stack). Tipos de Datos Abstractos.
23.1 Conceptos.
Uno de los conceptos más útiles en ciencias de la computación es la pila.
Una pila es una colección ordenada de elementos de igual tipo, en la cual pueden insertarse
nuevoselementos o eliminarse elementos sólo en un extremo; el que se denomina tope.
Una visión simple de la estructura es observar una pila de papeles. Sólo puede tomarse el
que está encima; y si se agregan componentes a la pila, también se lo hará en el tope de la
pila. Un stack es un caso particular, de un concepto más amplio denominado lista; también
suele denominarse lifo (last in, first out); esdecir, el último en llegar es el primero en salir.
La pila es una estructura dinámica, en el sentido que los elementos pueden ser insertados o
eliminados.
Las operaciones básicas con una pila son:
a) Meta un nuevo elemento (push). Insertar.
b) Sacar el elemento que está en el tope (pop). Borrar.
c) Iniciar la pila; dejarla vacía.
d) Detectar si está vacía o llena.
También pueden definirseoperaciones simples, que en ciertas aplicaciones resultan útiles:
a) Intercambiar los dos elementos superiores.
b) Leer valor del tope, sin eliminar.
c) Duplicar el tope.
Una visión esquemática de la estructura es:

tope

En la que se asume un crecimiento hacia
arriba y limitado.

Prof. Leopoldo Silva Bijit.

07-07-2003

287

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DEELECTRONICA
Programación en Pascal
Capítulo 23. Pila. (Stack). Tipos de datos abstractos.

En Pascal no se dispone de la pila como un tipo de datos. Pero puede ser implementada
con los tipos existentes. Por esta razón la pila es un ejemplo de tipo abstracto de datos.
Abstracto en el sentido que no existe como un tipo primitivo. Un modelo matemático con una
colección de operaciones definidassobre ese modelo, es un tipo de dato abstracto. El cual
puede implementarse en un lenguaje de programación mediante una definición de tipo y un
conjunto de procedimientos para realizar cada una de las operaciones del tipo.
23.2. Implementación mediante arreglo.
Una posibilidad es tratar como un arreglo:
var pila: array [1..lmax] of tipobase;
tope:integer; {0..lmax}
A continuación seimplementan las operaciones básicas, en términos de procedimientos:
procedure iniciopila;
begin tope:=0 end;
function vacia:boolean; {función sin parámetros}
begin
vacia:=tope=0
end;
A las funciones booleanas conviene ponerle nombres de adjetivos.
procedure push(nuevotope:tipo_base);
{introduce una nueva componente; y ocupa un espacio}
begin
if tope=lmax
then writeln('rebalse pila')
elsebegin
tope:=tope+1;
pila[tope]:=nuevotope
end
end;
procedure pop(var valortope:tipo_base);

Prof. Leopoldo Silva Bijit.

07-07-2003

288

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
Programación en Pascal
Capítulo 23. Pila. (Stack). Tipos de datos abstractos.

{copia en una variable el tope; y libera un espacio}
begin
if vacia
then writeln('pila vacia')else
begin
valortope:=pila[tope];
tope:=tope-1
end
end;
La variable tope debe ser accesible en todos los procedimientos.
Un ejemplo de aplicación podría ser el análisis de paréntesis en expresiones algebraicas. Se
permiten paréntesis ( [{}]). Debe verificarse que éstos estén hermanados correctamente.

Algoritmo:
Se inicia una pila vacía.
Se van leyendo caracteres, cuando se encuentraun paréntesis abierto, se lo introduce a
la pila. Cuando se encuentra un paréntesis cerrado, se lo compara con el tope; si son de
igual tipo, se saca el tope, en caso contrario se detecta falla sintáctica. El resto de
caracteres se descarta; al final la pila debe quedar vacía.

23.3. Implementación mediante re gistro.
Otra posibilidad de diseño es agrupar el tope y las componentes, en un...