Tecnico

Tema 14: El TAD de las pilas
Informática (2010–11)

José A. Alonso Jiménez
Grupo de Lógica Computacional Departamento de Ciencias de la Computación e I.A. Universidad de Sevilla

IM Tema 14: El TAD de las pilas

Tema 14: El TAD de las pilas
1. Tipos abstractos de datos Abstracción y tipos abstractos de datos 2. Especificación del TAD de las pilas Signatura del TAD pilas Propiedades delTAD de las pilas 3. Implementaciones del TAD de las pilas Las pilas como tipos de datos algebraicos Las pilas como listas 4. Comprobación de las implementaciones con QuickCheck Librerías auxiliares Generador de pilas Especificación de las propiedades de las pilas Comprobación de las propiedades

2 / 31

IM Tema 14: El TAD de las pilas Tipos abstractos de datos Abstracción y tipos abstractos dedatos

Tema 14: El TAD de las pilas
1. Tipos abstractos de datos Abstracción y tipos abstractos de datos 2. Especificación del TAD de las pilas 3. Implementaciones del TAD de las pilas 4. Comprobación de las implementaciones con QuickCheck

3 / 31

IM Tema 14: El TAD de las pilas Tipos abstractos de datos Abstracción y tipos abstractos de datos

Abstracción y tipos abstractos de datos
Laabstracción es un mecanismo para comprender problemas que involucran una gran cantidad de detalles. Aspectos de la abstracción:
Destacar los detalles relevantes. Ocultar los detalles irrelevantes.

Un tipo abstracto de datos (TAD) es una colección de valores y operaciones que se definen mediante una especificación que es independiente de cualquier representación. Un TAD es una abstracción:
Sedestacan los detalles (normalmente pocos) de la especificación (el qué). Se ocultan los detalles (normalmente numerosos) de la implementación (el cómo).

Analogía con las estructuras algebraicas.

4 / 31

IM Tema 14: El TAD de las pilas Especificación del TAD de las pilas Signatura del TAD pilas

Tema 14: El TAD de las pilas
1. Tipos abstractos de datos 2. Especificación del TAD de las pilasSignatura del TAD pilas Propiedades del TAD de las pilas 3. Implementaciones del TAD de las pilas 4. Comprobación de las implementaciones con QuickCheck

5 / 31

IM Tema 14: El TAD de las pilas Especificación del TAD de las pilas Signatura del TAD pilas

Descripción informal de las pilas
Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que lasoperaciones de inserción de extracción se realizan por el mismo extremo. La pilas también se llaman estructuras LIFO (del inglés Last In First Out), debido a que el último elemento en entrar será el primero en salir. Analogía con las pilas de platos.

6 / 31

IM Tema 14: El TAD de las pilas Especificación del TAD de las pilas Signatura del TAD pilas

Signatura del TAD de las pilas
Signatura:vacia :: apila :: cima :: desapila :: esVacia :: Descripción:

Pila a -> Pila Pila Pila

a Pila a -> a -> a ->

a -> Pila a a Pila a Bool

vacia es la pila vacía. (apila x p) es la pila obtenida añadiendo x al principio de p. (cima p) es la cima de la pila p. (desapila p) es la pila obtenida suprimiendo la cima de p. (esVacia p) se verifica si p es la pila vacía.

7 / 31

IM Tema 14: ElTAD de las pilas Especificación del TAD de las pilas Propiedades del TAD de las pilas

Tema 14: El TAD de las pilas
1. Tipos abstractos de datos 2. Especificación del TAD de las pilas Signatura del TAD pilas Propiedades del TAD de las pilas 3. Implementaciones del TAD de las pilas 4. Comprobación de las implementaciones con QuickCheck

8 / 31

IM Tema 14: El TAD de las pilas Especificacióndel TAD de las pilas Propiedades del TAD de las pilas

Propiedades de las pilas
1. cima (apila x p) == x 2. desapila (apila x p) == p 3. esVacia vacia 4. not (esVacia (apila x p))

9 / 31

IM Tema 14: El TAD de las pilas Implementaciones del TAD de las pilas Las pilas como tipos de datos algebraicos

Tema 14: El TAD de las pilas
1. Tipos abstractos de datos 2. Especificación del TAD de...