PDF de programación - Especificación algebraica de TADs Ejemplos: Pilas, Colas, Listas - Estructuras de Datos y Algoritmos

Estructuras de Datos 

y Algoritmos

Especificación algebraica de TADs

Ejemplos: Pilas, Colas, Listas

Prof. Dr. P. Javier Herrera

Índice

Ejemplos de especificación algebraica de TADs.

– Pila
– Cola
– Lista

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

22

Pila (Stack)

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

3

Pila ‐ Aplicaciones

• Almacenamiento de datos locales 
y la información de llamadas para 
las llamadas a procedimientos 
anidados

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

4

Pila ‐ Aplicaciones

• Evaluación de la expresión y el análisis sintáctico. 

• Por ejemplo, el cálculo ((1 + 2) * 4) + 3, puede ser anotado como en 

notación postfija con la ventaja de no prevalecer las normas y los 
paréntesis necesario: 1 2 + 4 * 3 +

• Backtracking (Vuelta atrás): es una estrategia para encontrar soluciones a 

problemas que satisfacen restricciones

• Gestión de memoria en tiempo de ejecución

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

5

Pila ‐ Operaciones básicas

•

El TAD de las pilas cuenta con las siguientes operaciones:

– crear la pila vacía,
– apilar un elemento,
– desapilar el elemento en la cima,
– consultar el elemento en la cima, y
– determinar si la pila es vacía.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

6
6

Pila ‐ Especificación algebraica

especificación PILAS[ELEM]
usa BOOLEANOS
tipos pila
operaciones

pila-vacía
apilar
desapilar
cima
es-pila-vacía?

:
: elemento pila
: pila
: pila
: pila

{ constructora }
{ constructora }

→ pila
→ pila
→p pila
→p elemento
→ bool

•

Como el orden de apilación es fundamental para la posterior consulta y eliminación, las 
constructoras son libres (no son necesarias ecuaciones de equivalencia).

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

7
7

Pila ‐ Especificación algebraica

variables

e : elemento
p : pila
ecuaciones

desapilar(pila-vacía)
desapilar(apilar(e, p))

cima(pila-vacía)
cima(apilar(e, p))

= error
= p

= error
= e

es-pila-vacía?(pila-vacía)
= cierto
es-pila-vacía?(apilar(e, p)) = falso

fespecificación

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

8
8

Cola (queue)

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

9

Cola ‐ Aplicaciones

• Cola de impresión

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

10

Cola ‐ Operaciones básicas

•

El TAD de las colas cuenta con las siguientes operaciones:

– crear la cola vacía,
– añadir un elemento al final de la cola,
– eliminar el primer elemento en la cola,
– consultar el primer elemento, y
– determinar si la cola es vacía.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

11
11

Cola ‐ Especificación algebraica

especificación COLAS[ELEM]
usa BOOLEANOS
tipos cola
operaciones

cola-vacía
pedir-vez
avanzar
primero
es-cola-vacía?

:
: cola elemento
: cola
: cola
: cola

{ constructora }
{ constructora }

→ cola
→ cola
→p cola
→p elemento
→ bool

•

El orden de inserción de los elementos en la cola determina la cola, por lo que las 
constructoras son libres. No son necesarias ecuaciones de equivalencia.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

12
12

Cola ‐ Especificación algebraica

variables

e : elemento
c : cola
ecuaciones

avanzar(cola-vacía)
avanzar(pedir-vez(c, e))
avanzar(pedir-vez(c, e))

primero(cola-vacía)
primero(pedir-vez(c, e))
primero(pedir-vez(c, e))

= error

= cola-vacía ⇐ es-cola-vacía?(c)
= pedir-vez(avanzar(c), e) ⇐ ￢es-cola-vacía?(c)
= e⇐ es-cola-vacía?(c)
= primero(c) ⇐ ￢es-cola-vacía?(c)

= error

es-cola-vacía?(cola-vacía) = cierto
es-cola-vacía?(pedir-vez(c, e)) = falso

fespecificación

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

13
13

Lista (List)

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

14

Lista ‐ Aplicaciones

• Generalización de las pilas y las colas. Puede ser usada para implementar 

otras estructuras de datos.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

15

Lista ‐ Operaciones básicas

• Un posible TAD de las listas cuenta con las siguientes operaciones:

– crear la lista vacía,
– generar una lista unitaria formada por un elemento dado,
– añadir un elemento por la izquierda,
– añadir un elemento por la derecha,
– consultar el elemento más a la izquierda,
– consultar el elemento más a la derecha,
– eliminar el elemento más a la izquierda,
– eliminar el elemento más a la derecha,
– determinar si una lista es vacía,
– concatenar dos listas, y
– calcular la longitud de una lista.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

16
16

Lista ‐ Especificación algebraica

especificación LISTAS[ELEM]
usa BOOLEANOS, NATURALES
tipos lista
operaciones

[ ]
_ : _
[ _ ]
_ # _
izquierdo
elim-izq
derecho
elim-der
es-lista-vacía?
_ ++ _
longitud

:
: elemento lista
: elemento
: lista elemento
: lista
: lista
: lista
: lista
: lista
: lista lista
: lista

{ constructora }
{ constructora }

→ lista
→ lista
→ lista
→ lista
→p elemento
→p lista
→p elemento
→p lista
→ bool
→ lista
→ nat

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

17
17

Lista ‐ Especificación algebraica

variables

: elemento

e, f
x, y, z : lista

ecuaciones

= e : [ ]

[e]
x # e = x ++ [e]

izquierdo([ ])
izquierdo(e : x) = e

= error

elim-izq([ ])
elim-izq(e : x)

= error
= x

= error

derecho([ ])
derecho(e : [ ]) = e
derecho(e : f : x) = derecho(f : x)

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

18
18

Lista ‐ Especificación algebraica

= error

elim-der([ ])
elim-der(e : [ ]) = [ ]
elim-der(e : f : x) = e : elim-der(f : x)

es-lista-vacía?([ ]) = cierto
es-lista-vacía?(e : x) = falso

[ ] ++ y
(e : x) ++ y

= y
= e : (x ++ y)

longitud([ ])
longitud(e : x)

= 0
= 1 + longitud(x)

fespecificación

•

También podemos considerar como constructoras la operación que crea la lista vacía y la que 
añade un elemento por la derecha (situación simétrica a la anterior); o bien elegir la lista 
vacía, la operación de construcción de la lista unitaria y la operación de concatenación.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

19
19

Bibliografía

• Martí, N., Ortega, Y., Verdejo, J.A. Estructuras de datos y métodos algorítmicos. Ejercicios 

resueltos. Pearson/Prentice Hall, 2003. Capítulos 1, 3, 4, 5

•

Peña, R.; Diseño de programas. Formalismo y abstracción. Tercera edición. Prentice Hall, 
2005. Capítulos 5, 6

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

20