Post on 15-Apr-2017
Programación 3
Pilas
Angel Vázquez-Patiñoangel.vazquezp@ucuenca.edu.ec
Departamento de Ciencias de la ComputaciónUniversidad de Cuenca
14 de marzo de 2017
14/03/17 Angel Vázquez-Patiño 2/48
Objetivos
1.Especificar el tipo abstracto de datos Pila
2.Definir e implementar la clase Pila
14/03/17 Angel Vázquez-Patiño 3/48
Contenido
Concepto de pila
Tipo de dato Pila implementado con arrays
Pila dinámica implementada con un vector
Tipo Pila implementada como una lista enlazada
14/03/17 Angel Vázquez-Patiño 4/48
Concepto de pila
14/03/17 Angel Vázquez-Patiño 5/48
Concepto de pila
Definición● Estructura de datos de entradas ordenadas que
sólo se pueden introducir y eliminar por un extremo llamado cima
● Debido a su propiedad específica último en entrar, primero en salir se conoce como estructuras de datos LIFO (last-in, first-out)
Concepto de pila
14/03/17 Angel Vázquez-Patiño 7/48
Concepto de pila
Operaciones básicas
1) Insertar (push): añade elemento en la cima
2) Quitar (pop): elimina un elemento de la pila
14/03/17 Angel Vázquez-Patiño 8/48
Concepto de pila
14/03/17 Angel Vázquez-Patiño 9/48
Concepto de pila
Implementación● Dimensión estática
– Array
● Dimensión dinámica– Vector
– Lista enlazada
14/03/17 Angel Vázquez-Patiño 10/48
Concepto de pila
Desbordamientos
1)Underflow
2)Overflow
● Para evitar estas situaciones se diseñan métodos que comprueban si la pila está llena o vacía
14/03/17 Angel Vázquez-Patiño 11/48
Concepto de pila
Especificaciones de una pila
14/03/17 Angel Vázquez-Patiño 12/48
Tipo de dato Pila implementado con arrays
14/03/17 Angel Vázquez-Patiño 13/48
Tipo de dato Pila con arrays
Se necesita● Un array● Una variable numérica cima● No puede exceder el tamaño del array
14/03/17 Angel Vázquez-Patiño 14/48
Tipo de dato Pila con arrays
Push y pop
14/03/17 Angel Vázquez-Patiño 15/48
Tipo de dato Pila con arrays
Ejemplo
14/03/17 Angel Vázquez-Patiño 16/48
Tipo de dato Pila con arrays
Clase PilaLineal
1) Representación de los datos
2) Definición de las operaciones
14/03/17 Angel Vázquez-Patiño 17/48
Tipo de dato Pila con arrays
Clase
PilaLineal
14/03/17 Angel Vázquez-Patiño 18/48
Tipo de dato Pila con arrays
14/03/17 Angel Vázquez-Patiño 19/48
Tipo de dato Pila con arrays
14/03/17 Angel Vázquez-Patiño 20/48
Tipo de dato Pila con arrays
Clase PilaLineal
14/03/17 Angel Vázquez-Patiño 21/48
Tipo de dato Pila con arrays
Implementación de operaciones sobre pilas
14/03/17 Angel Vázquez-Patiño 22/48
Tipo de dato Pila con arrays
Implementación de operaciones sobre pilas
14/03/17 Angel Vázquez-Patiño 23/48
Tipo de dato Pila con arrays
Implementación de operaciones sobre pilas
14/03/17 Angel Vázquez-Patiño 24/48
Tipo de dato Pila con arrays
Operaciones de verificación del estado de la pila
14/03/17 Angel Vázquez-Patiño 25/48
Tipo de dato Pila con arrays
Ejemplo: Palíndromo
Reconocer → r e c o n o c e R
14/03/17 Angel Vázquez-Patiño 26/48
Tipo de dato Pila con arrays
14/03/17 Angel Vázquez-Patiño 27/48
Tipo de dato Pila con arrays
14/03/17 Angel Vázquez-Patiño 28/48
Pila dinámica implementada con un Vector
14/03/17 Angel Vázquez-Patiño 29/48
Tipo de dato Pila con Vector
14/03/17 Angel Vázquez-Patiño 30/48
Tipo de dato Pila con Vector
14/03/17 Angel Vázquez-Patiño 31/48
Tipo de dato Pila con Vector
14/03/17 Angel Vázquez-Patiño 32/48
Pila dinámica implementada con una lista enlazada
14/03/17 Angel Vázquez-Patiño 33/48
Tipo de dato Pila con lista enlazada
Ventaja● Tamaño se ajusta al número de elementos
Desventaja● Para cada elemento es necesaria más
memoria ya que hay que guardar el campo de enlace entre nodos consecutivos
14/03/17 Angel Vázquez-Patiño 34/48
Tipo de dato Pila con lista enlazada
Clase NodoPila
14/03/17 Angel Vázquez-Patiño 35/48
Tipo de dato Pila con lista enlazada
Clase PilaLista
14/03/17 Angel Vázquez-Patiño 36/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
14/03/17 Angel Vázquez-Patiño 37/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
14/03/17 Angel Vázquez-Patiño 38/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
cima
E1 null
cima
E1 nullE2
cima
E2 E1 null
14/03/17 Angel Vázquez-Patiño 39/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
14/03/17 Angel Vázquez-Patiño 40/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
cima
null
cima
E1 null
cima
E2 E1 null
aux
E2
aux
E1
14/03/17 Angel Vázquez-Patiño 41/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
14/03/17 Angel Vázquez-Patiño 42/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
14/03/17 Angel Vázquez-Patiño 43/48
Resumen
14/03/17 Angel Vázquez-Patiño 44/48
Resumen● LIFO (last in first out)● Operaciones básicas
– crear, insertar, cima, quitar, pilaVacia, pilaLlena y limpiarPila
● Implementación– Arrays
– Vectores
– Listas enlazadas
14/03/17 Angel Vázquez-Patiño 45/48
Conceptos y términos importantes
14/03/17 Angel Vázquez-Patiño 46/48
Conceptos y términos importantes● FIFO● Listas enlazadas● Pila● Tipo Abstracto de Datos (TAD)● Operaciones básicas
14/03/17 Angel Vázquez-Patiño 47/48
Referencia● Joyanes Aguilar, L., Zahonero Martínez, I.,
2008. Estructuras de datos en Java. McGraw-Hill, Madrid, Spain. Capítulo 9.
14/03/17 Angel Vázquez-Patiño 48/48
Preguntas