Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

TEMA 2. ESTRUCTURAS LINEALES

Objetivos
En este tema se definen varios tipos abstractos de datos que tienen una propiedad comn, disponer de una estructura lineal. Para cada uno de estos TAD se realiza su especificacin y se dan implementaciones alternativas. Para ilustrar la utilidad de los mismos se presentan ejemplos de aplicacin para su realizacin en Java.

Contenidos 1. Introduccin 2. TAD pila

2.1. Especificacin 2.2. Implementacin Mediante arrays Mediante listas enlazadas 2.3. Aplicaciones del TAD pila Tratamiento de expresiones aritmticas

3. TAD cola
3.1. Especificacin 3.2. Implementacin Mediante arrays circulares Mediante listas enlazadas 3.3. Variantes del TAD Cola 3.4. Aplicaciones del TAD cola

4. Secuencias
4.1. Secuencias por posicin: Listas Especificacin Implementacin 4.2. Iteradores

Departamento de Informtica

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

4.2.1. Listas con iteradores Especificacin Implementacin

Bibliografa
Bsica
Goodrich M. y Tamassia R., Data structures and Algorithms in JAVA 4 ed. John Wiley & Sons Inc. , 2006 Pgs.187-203, 204-210, 222-228, 231-241, 242-248 Lewis, J. y Chase J. Estructuras de datos con Java. Diseo de estructuras y algoritmos. 2 ed. Pearson. Addisson Wesley. 2006 Pgs. 152-161, 166-174, 180-182, 193-205 Weiss, Mark Allen, Estructuras de datos en Java: compatible con JAVA 2, Addisson Wesley. 2000. Pgs.139-146, 395-410, 415-427 Liskov, B. y J. Guttag, Program Development in Java: Abstraction, Specification, and Object-Oriented Design, Addison-Wesley, 2001. Pgs. 125-137

Complementaria
Goodrich M. y Tamassia R., Data structures and Algorithms in JAVA 2 ed. John Wiley & Sons Inc. , 2001. Pgs.166-173, 213-216, 249-259 Lewis, J. y Chase J. Estructuras de datos con Java. Diseo de estructuras y algoritmos. 2 ed. Pearson. Addisson Wesley. 2006 Pgs. 161-166, 182-192, 212-240, 246-261

Departamento de Informtica

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

Tema 2. Estructuras Lineales

1. Introduccin
Las estructuras lineales son importantes porque aparecen con mucha frecuencia en situaciones de la vida: Una cola de clientes de un banco, las instrucciones de un programa, los caracteres de una cadena o las pginas de un libro Caractersticas: existe un nico elemento, llamado primero, existe un nico elemento, llamado ltimo, cada elemento, excepto el primero, tiene un nico predecesor y cada elemento, excepto el ltimo, tiene un nico sucesor. Operaciones: crear la estructura vaca, insertar un elemento, borrar y obtener un elemento. Para definir claramente el comportamiento de la estructura es necesario determinar en qu posicin se inserta un elemento nuevo y qu elemento se borra o se obtiene. Principales estructuras lineales: pilas, colas y listas.

Departamento de Informtica

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

2. TAD PILA
Una pila es un contenedor de objetos que son insertados y eliminados de acuerdo con el principio de que el ltimo en entrar es el primero en salir.

Tambin se les denomina estructuras LIFO (Last In First Out).

Entrar

Salir Tope de la pila a3 a2 a1

Aplicaciones:

direcciones de los sitios ms recientemente visitados.

Navegadores en Internet almacenan en una pila las

deshacer que cancela las operaciones de edicin recientes y restablece el estado anterior del documento.

Los editores de texto proporcionan normalmente un botn

Departamento de Informtica

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

2.1. Especificacin
Especificacin cuasi-formal:
public class Pila <E> { // caractersticas: // Es una secuencia de elementos donde el ltimo en entrar es el primero // en ser eliminado // Los objetos son modificables. // constructores public Pila <E> ( ) // Produce: una pila vaca //mtodos public int tamao() // Produce: devuelve el nmero de elementos de la pila public boolean esVacio() // Produce: cierto si la pila est vaca. Falso en otro caso public E top() throws PilaVaciaExcepcion // Produce: si la pila est vaca lanza la excepcin // PilaVaciaExcepcion, sino devuelve el objeto ms // recientemente introducido public E pop() throws PilaVaciaExcepcion // Modifica: this // Produce: si la pila est vaca lanza la excepcin // PilaVaciaExcepcion, sino devuelve el objeto ms // recientemente introducido y lo suprime de la pila public void push (E elemento) // Modifica: this // Produce: aade un objeto a la pila, pasando a ser el nuevo tope }

Ejemplo de uso del TAD Pila:

public class PruebaPila{ public static void main (String []args){ Pila<Integer> p = new Pila<Integer>(); for (int i=1; i<10;i++) p.push(i); System.out.println("Los elementos de la pila son:"); while(!p.esVacio()) System.out.println(p.pop()); } }

Departamento de Informtica

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

2.2. Implementacin
Dos pasos:

Definicin de una interfaz que describa los nombres de los mtodos que soporta el TAD y cmo tienen que ser declarados y usados.
public interface Pila<E>{ public int tamao(); public boolean esVacio(); public E top() throws PilaVaciaExcepcion; public void push (E elemento); public E pop() throws PilaVaciaExcepcion; } public class PilaVaciaExcepcion extends RuntimeException{ ... }

Proporcionar una clase concreta que implemente los mtodos de la interfaz asociada con el TAD.
Tope de la pila

Mediante arrays

elementos

a1
0

a2
1

a3
2

a4
3

...

at
tope N-1

Problema: pila llena Solucin: mtodo privado duplicarPila() que lleve a cabo una expansin dinmica del vector un nuevo tipo de excepcin, PilaLlenaExcepcion

public class ArrayPila<E> implements Pila<E>{ public static final int CAPACIDAD_POR_DEFECTO=10; private E[]elementos; private int tope;

Departamento de Informtica

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

public ArrayPila(int capacidad){ elementos=(E[])new Object [capacidad]; tope=-1; } public ArrayPila (){ this(CAPACIDAD_POR_DEFECTO); } public int tamao(){ return (tope+1); } public boolean esVacio(){ return tope==-1; } public E top()throws PilaVaciaExcepcion{ if (esVacio()) throw new PilaVaciaExcepcion("top: Pila vacia"); return elementos[tope]; } public void push (E elemento){ if (tope==elementos.length-1) duplicarPila(); elementos[++tope]=elemento; } public E pop()throws PilaVaciaExcepcion{ E elemento; if (esVacio()) throw new PilaVaciaExcepcion("pop: Pila vaca"); elemento=elementos[tope]; elementos[tope--]=null; return elemento; } private void duplicarPila(){ E[] nuevaPila; nuevaPila=(E[])new Object[elementos.length*2]; for (int i=0;i<elementos.length;i++) nuevaPila[i]=elementos[i]; elementos=nuevaPila; } }

Implementacin alternativa usando la clase Vector<E> Ventajas: implementacin simple y eficiente Desventaja: lmite superior en el tamao del array

Departamento de Informtica

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

Mediante listas enlazadas genricas

Tope de la pila

Se define una clase genrica Nodo, la cual especifica el formato de los objetos asociados a los nodos de la pila
public class Nodo<E> { private E elemento; //referencia al elemento del nodo private Nodo<E> sig; //referencia al siguiente nodo de la lista //constructor public Nodo(){ //Produce: crea un nodo con valor null en sus referencias al // elemento y al siguiente nodo this(null,null); } public Nodo(E e, Nodo<E> n){ // Produce: un objeto Nodo con el elemento y siguiente nodo // que se le pasa como parmetro elemento=e; sig=n; } //mtodos public void setElemento(E e){ // Modifica: this // Produce: modifica el atributo elemento de this elemento = e; } public void setSig(Nodo<E> n){ // Modifica: this // Produce: modifica el atributo sig de this sig = n; } public E getElemento(){ // Produce: devuelve el atributo elemento de this return elemento; }

Departamento de Informtica

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

public Nodo<E> getSig(){ // Produce: devuelve el atributo sig de this return sig; } }

Se define una clase genrica EnlazadaPila que mantiene una referencia al primer nodo de la lista.

public class EnlazadaPila<E> implements Pila<E> { private Nodo<E> tope; private int contador; public EnlazadaPila(){ tope=null; contador=0; } public int tamao(){ return contador; } public boolean esVacio(){ return tope==null; } public E top() throws PilaVaciaExcepcion{ if (esVacio()) throw new PilaVaciaExcepcion("top: Pila Vacia"); return tope.getElemento(); } public void push (E e){ Nodo<E> n=new Nodo<E>(e,tope); tope=n; contador++; } public E pop() throws PilaVaciaExcepcion{ if (esVacio()) throw new PilaVaciaExcepcion("pop: Pila Vacia"); E e=tope.getElemento(); tope=tope.getSig(); contador--; return e; } }

Departamento de Informtica

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

2.3. Aplicaciones del TAD Pila

Las pilas son una estructura de datos muy usada como estructura auxiliar en diversos algoritmos y esquemas de programacin. Los casos ms representativos son:

Solitario, Laberinto, etc. (back tracking).

notaciones (postfija, prefija, infija)...

Evaluacin de expresiones aritmticas, conversin de

Llamadas a subprogramas

Recursin.

2.3.1. Tratamiento de expresiones aritmticas Cul es el resultado de 4*5 + 6*7? 20 + 42 = 62, correcto 20 + 6 = 26 * 7 = 182, error A qu se debe el error? Se han utilizado mal las precedencias. Cmo puede solucionarse?

Parntesis: (4*5) + (6 * 7) Usando otra notacin para los smbolos.

Tipos de notacin :

Infija: Postfija: Prefija:

A op B A B op op A B

4*5+6*7 45*67*+ +*45*67

Una ventaja de la notacin postfija es que no necesita parntesis.

Departamento de Informtica

10

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

Conversin de notacin infija a postfija Ejemplo: a + b * c + (d * e + f) * g abc*+de*f+g*+

Usando una pila este proceso puede realizarse de la siguiente forma: 1. Leyendo uno por uno los elementos de la entrada y si a) es un operando, se manda a la salida; b) es un ( push (P, ( ) c) es un ) hacer pop (P) hasta que se encuentre ( d) es un operador op, entonces d.1) sacar de la pila, pop (P), los operadores con prioridad mayor o igual a op. Las prioridades de menor a mayor seran: ( +,*, / d.2) push (P, op) 2. Cuando se llega al final de la entrada, se vaca la pila P sobre la salida. Ejemplo: Entrada = a + b * c + (d * e + f) * g En el siguiente ejemplo el tope de la pila es el elemento ms a la derecha
Entrada a + b * Operacin a la salida Push a la salida + < * push * + + + * Pila Salida a a ab ab

Departamento de Informtica

11

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

c +

a la salida mientras precedencia tope >= precedencia operador hacer pop; push +

+ * +

abc abc*+

( d * e +

push ( a la salida Push a la salida mientras precedencia tope >= precedencia operador hacer pop; push +

+ ( + ( + ( * + ( * + ( +

abc*+ abc*+d abc*+d abc*+de abc*+de*

f ) * g

a la salida repetir pop hasta encontrar ( push a la salida vaciar pila

+ ( + + + * + *

abc*+de*f abc*+de*f+ abc*+de*f+ abc*+de*f+g abc*+de*f+g*+

Departamento de Informtica

12

Reyes Pavn

Ampliacin de Estructuras de Datos y de la Informacin

E.S.I. Informtica

Evaluacin de la notacin postfija mediante una pila. Cmo usar una pila? 1. Se lee la entrada, elemento a elemento, x:

Si es un operando se mete en la pila: push(P, x) Si es un operador se sacan los operandos, se realiza la operacin y se guarda el resultado en la pila:

pop (P); pop(P); evaluar (operador, op1, op2, res); push(P, res) 2. Al terminar de leer la entrada, en el tope de la pila P debe quedar el resultado de la operacin Ejemplo: 4 5 * 6 7 * + Entrada 4 Accin Pila 4 45

Push() Push() Evaluar + push() Push() Push() Evaluar + push() Evaluar + push()

5
* 6 7 * +

20 20 6
20 6 7 20 42 62

Departamento de Informtica

13

Reyes Pavn