Programación 3: pilas
-
Upload
angel-vazquez-patino -
Category
Engineering
-
view
132 -
download
0
Transcript of Programación 3: pilas
![Page 1: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/1.jpg)
Programación 3
Pilas
Angel Vázquez-Patiñ[email protected]
Departamento de Ciencias de la ComputaciónUniversidad de Cuenca
14 de marzo de 2017
![Page 2: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/2.jpg)
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
![Page 3: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/3.jpg)
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
![Page 4: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/4.jpg)
14/03/17 Angel Vázquez-Patiño 4/48
Concepto de pila
![Page 5: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/5.jpg)
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)
![Page 6: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/6.jpg)
Concepto de pila
![Page 7: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/7.jpg)
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
![Page 8: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/8.jpg)
14/03/17 Angel Vázquez-Patiño 8/48
Concepto de pila
![Page 9: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/9.jpg)
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
![Page 10: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/10.jpg)
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
![Page 11: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/11.jpg)
14/03/17 Angel Vázquez-Patiño 11/48
Concepto de pila
Especificaciones de una pila
![Page 12: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/12.jpg)
14/03/17 Angel Vázquez-Patiño 12/48
Tipo de dato Pila implementado con arrays
![Page 13: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/13.jpg)
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
![Page 14: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/14.jpg)
14/03/17 Angel Vázquez-Patiño 14/48
Tipo de dato Pila con arrays
Push y pop
![Page 15: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/15.jpg)
14/03/17 Angel Vázquez-Patiño 15/48
Tipo de dato Pila con arrays
Ejemplo
![Page 16: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/16.jpg)
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
![Page 17: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/17.jpg)
14/03/17 Angel Vázquez-Patiño 17/48
Tipo de dato Pila con arrays
Clase
PilaLineal
![Page 18: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/18.jpg)
14/03/17 Angel Vázquez-Patiño 18/48
Tipo de dato Pila con arrays
![Page 19: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/19.jpg)
14/03/17 Angel Vázquez-Patiño 19/48
Tipo de dato Pila con arrays
![Page 20: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/20.jpg)
14/03/17 Angel Vázquez-Patiño 20/48
Tipo de dato Pila con arrays
Clase PilaLineal
![Page 21: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/21.jpg)
14/03/17 Angel Vázquez-Patiño 21/48
Tipo de dato Pila con arrays
Implementación de operaciones sobre pilas
![Page 22: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/22.jpg)
14/03/17 Angel Vázquez-Patiño 22/48
Tipo de dato Pila con arrays
Implementación de operaciones sobre pilas
![Page 23: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/23.jpg)
14/03/17 Angel Vázquez-Patiño 23/48
Tipo de dato Pila con arrays
Implementación de operaciones sobre pilas
![Page 24: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/24.jpg)
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
![Page 25: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/25.jpg)
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
![Page 26: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/26.jpg)
14/03/17 Angel Vázquez-Patiño 26/48
Tipo de dato Pila con arrays
![Page 27: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/27.jpg)
14/03/17 Angel Vázquez-Patiño 27/48
Tipo de dato Pila con arrays
![Page 28: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/28.jpg)
14/03/17 Angel Vázquez-Patiño 28/48
Pila dinámica implementada con un Vector
![Page 29: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/29.jpg)
14/03/17 Angel Vázquez-Patiño 29/48
Tipo de dato Pila con Vector
![Page 30: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/30.jpg)
14/03/17 Angel Vázquez-Patiño 30/48
Tipo de dato Pila con Vector
![Page 31: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/31.jpg)
14/03/17 Angel Vázquez-Patiño 31/48
Tipo de dato Pila con Vector
![Page 32: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/32.jpg)
14/03/17 Angel Vázquez-Patiño 32/48
Pila dinámica implementada con una lista enlazada
![Page 33: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/33.jpg)
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
![Page 34: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/34.jpg)
14/03/17 Angel Vázquez-Patiño 34/48
Tipo de dato Pila con lista enlazada
Clase NodoPila
![Page 35: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/35.jpg)
14/03/17 Angel Vázquez-Patiño 35/48
Tipo de dato Pila con lista enlazada
Clase PilaLista
![Page 36: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/36.jpg)
14/03/17 Angel Vázquez-Patiño 36/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
![Page 37: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/37.jpg)
14/03/17 Angel Vázquez-Patiño 37/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
![Page 38: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/38.jpg)
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
![Page 39: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/39.jpg)
14/03/17 Angel Vázquez-Patiño 39/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
![Page 40: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/40.jpg)
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
![Page 41: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/41.jpg)
14/03/17 Angel Vázquez-Patiño 41/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
![Page 42: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/42.jpg)
14/03/17 Angel Vázquez-Patiño 42/48
Tipo de dato Pila con lista enlazada
Implementación de operaciones del TAD Pila
![Page 43: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/43.jpg)
14/03/17 Angel Vázquez-Patiño 43/48
Resumen
![Page 44: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/44.jpg)
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
![Page 45: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/45.jpg)
14/03/17 Angel Vázquez-Patiño 45/48
Conceptos y términos importantes
![Page 46: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/46.jpg)
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
![Page 47: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/47.jpg)
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.
![Page 48: Programación 3: pilas](https://reader030.fdocumento.com/reader030/viewer/2022021507/5877a66f1a28ab826e8b62d1/html5/thumbnails/48.jpg)
14/03/17 Angel Vázquez-Patiño 48/48
Preguntas