Tema5 Pilas

Pilas (Stacks)
•
•
•
•
•

Tipos de Datos Abstractos (TDAs)
Pilas (Stacks)
Aplicación al análisis de una serie de tiempo
Implementación Java de una pila
Interfaces y excepciones

 

 

1

Tipos de Datos Abstractos 
(TDAs)
• Un Tipo de Dato Abstracto es una abstracción de una estructura de 
dato. (No hay código relacionado)
• El TDA especifica:
– qué se puede almacenar en el TDA
–qué operaciones se pueden realizar sobre/por el TDA

• Por ejemplo, si se modela una bolsa de caramelos como un TDA, 
se puede especificar que:
– este TDA almacena caramelos
– este TDA permite poner un caramelo y extraer un caramelo.

 

 

2

Tipos de Datos Abstractos 
(TDAs)

• Hay una gran cantidad de TDAs formalizados y estándar.
• En lo sucesivo se mostrarán varios TDAs estándar diferentes (pilas, colas, árboles...)

 

 

3

Pilas (Stacks)
• Una pila es un contenedor de objetos que se insertan y extraen de 
acuerdo al principio de último en entrar, primero en salir (last­in­
first­out, LIFO). 
• Los objetos se pueden insertar en cualquier momento, pero sólo el 
último (el insertado más reciente) objecto puede ser extraído.
• La inserción de un elemento se conoce como “pushing” en la pila. “Popping” de la pila es sinónimo de extraer un elemento.

 

 

4

El Tipo de Dato Abstracto Pila
• Una pila es un tipo de dato abstracto (TDA) que soporta dos 
métodos principales:
– push(o): Inserta un objeto sobre el último o cima de la pila.
– pop(): 
Extrae el objeto de la cima de la pila y lo devuelve; si la pila está 
vacía, ocurre un error.

• Los siguientes métodos para la gestión de la pila deben ser definidos:
– size():
Devuelve el número de objetos en la pila.
– isEmpty():
Devuelve un boolean indicando si la pila está vacía.
– top():
Devuelve el objeto de la cima de la pila sin extraerlo; si la pila está 
vacía, ocurre un error.

 

 

5

Aplicación: Series de Tiempo
• El lapso si del precio de una acción en una día i determinado es el máximo número de días consecutivos (hasta el día en curso) que el 
precio de la acción ha sido menor o igual a su precio en el día i

 

 

6

Un Algoritmo Ineficiente
• Hay una forma directa de calcular el lapso de una acción de n días:
Algoritmo calculaLapso1(P):
Input: un array de números P de n­elementos tal que 
P[i] es el precio de la acción en el día i
Output: un array de números S de n­elementos tal que 
S[i] es el lapso de la acción en el día ifor i 0 to n ­ 1 do k  0
done  false
repeat
if P[i ­ k]  P[i] then k  k + 1
else done  true
until (k = i) or done
S[i]  k
return S

El tiempo de ejecución de este algoritmo es O(n2). 
 
 

7

Una pila puede ayudar

• Vemos que si en el día i puede calcularse fácilmente si se conoce 
el día previo más próximo a i, tal que el precio es mayor que el precio del día i. Si existe tal día, lo llamanos h(i), en otro caso, 
por convención se define h(i) = ­1
• El lapso se calcula como si = i ­ h(i)

 

Usamos una pila para 
mantener h(i)
 

8

Un Algoritmo Eficiente
• El código para el nuevo algoritmo es:
Algoritmo calculaLapso2(P):
Input: un array de números P de n­elementos que representan los 
precios de la acción 
Output: un array de números S de n­elementos tal que 
S[i] es el lapso de la acción en el día i Sea D una pila vacía
for i 0 to n ­ 1 do k  0
done  false
while not(D.isEmpty() or done) do
if P[i] ?? P[D.top()] then
D.pop()
else done  true
if D.isEmpty() then h  ­1
else h  D.top()
       S[i]  i ­ h
       D.push(i)
 
return S  

9

Implementación Java
• Dado el TDA pila, necesitamos codificar el TDA para usarlo en los 
programas. Es necesario primero entender dos constructores de programas: interfaces y exceptions.
• Una interface es  una forma de declarar lo que hace una clase. No 
menciona cómo lo hace.
– Para una interface, se escriben los nombres de los métodos y los parámetros. 
Cuando se especifican parámetros, lo que realmente importa son sus tipos.
– Después, cuando se escribe una class para esa interface, se codifica el ...