estructuras lineales java

Ampliación de Estructuras de Datos y de la Información E.S.I. Informática

Departamento de Informática 1 Reyes Pavón

TEMA 2. ESTRUCTURAS LINEALES

Objetivos En este tema se definen varios tipos abstractos de datos que tienen una propiedad común, disponer de una estructura lineal. Para cada uno de estos TAD se realiza su especificación y se dan implementaciones alternativas. Para ilustrar la utilidad de los mismos se presentan ejemplos de aplicación para su realización en Java.

Contenidos

1. Introducción

2. TAD pila 2.1. Especificación 2.2. Implementación

• Mediante arrays • Mediante listas enlazadas

2.3. Aplicaciones del TAD pila • Tratamiento de expresiones aritméticas

3. TAD cola 3.1. Especificación 3.2. Implementación

• Mediante arrays circulares • Mediante listas enlazadas

3.3. Variantes del TAD Cola 3.4. Aplicaciones del TAD cola

4. Secuencias 4.1. Secuencias por posición: Listas

• Especificación • Implementación

4.2. Iteradores



4.2.1. Listas con iteradores • Especificación • Implementación

Bibliografía

Básica Goodrich M. y Tamassia R., Data structures and Algorithms in JAVA 4ª ed. John Wiley & Sons Inc. , 2006 Págs.187-203, 204-210, 222-228, 231-241, 242-248

Lewis, J. y Chase J. Estructuras de datos con Java. Diseño de estructuras y algoritmos. 2ª ed. Pearson. Addisson Wesley. 2006 Págs. 152-161, 166-174, 180-182, 193-205

Weiss, Mark Allen, Estructuras de datos en Java: compatible con JAVA 2, Addisson Wesley. 2000. Págs.139-146, 395-410, 415-427

Liskov, B. y J. Guttag, Program Development in Java: Abstraction, Specification, and Object-Oriented Design, Addison-Wesley, 2001. Págs. 125-137

Complementaria Goodrich M. y Tamassia R., Data structures and Algorithms in JAVA 2ª ed. John Wiley & Sons Inc. , 2001. Págs.166-173, 213-216, 249-259

Lewis, J. y Chase J. Estructuras de datos con Java. Diseño de estructuras y algoritmos. 2ª ed. Pearson. Addisson Wesley. 2006 Págs. 161-166, 182-192, 212-240, 246-261



Tema 2. Estructuras Lineales

1. Introducción

♦ 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 páginas de un libro

♦ Características: 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 vacía, insertar un elemento, borrar y obtener un elemento. Para definir claramente el comportamiento de la estructura es necesario determinar en qué posición se inserta un elemento nuevo y qué elemento se borra o se obtiene.

♦ Principales estructuras lineales: pilas, colas y listas.



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.

♦ También se les denomina estructuras LIFO (Last In First Out).

♦ Aplicaciones:

♦ Navegadores en Internet almacenan en una pila las direcciones de los sitios más recientemente visitados.

♦ Los editores de texto proporcionan normalmente un botón deshacer que cancela las operaciones de edición recientes y restablece el estado anterior del documento.

Entrar Salir

a1

a2

a3

Tope de la pila



2.1. Especificación

♦ Especificación cuasi-formal:

public class Pila <E> { // características:

// 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 vacía //métodos public int tamaño() // Produce: devuelve el número de elementos de la pila public boolean esVacio() // Produce: cierto si la pila está vacía. Falso en otro caso public E top() throws PilaVaciaExcepcion

// Produce: si la pila está vacía lanza la excepción // PilaVaciaExcepcion, sino devuelve el objeto más // recientemente introducido

public E pop() throws PilaVaciaExcepcion // Modifica: this // Produce: si la pila está vacía lanza la excepción // PilaVaciaExcepcion, sino devuelve el objeto más // recientemente introducido y lo suprime de la pila public void push (E elemento) // Modifica: this // Produce: añade 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()); } }



elementos

Tope de la pila

2.2. Implementación

♦ Dos pasos:

♦ Definición de una interfaz que describa los nombres de los métodos que soporta el TAD y cómo tienen que ser declarados y usados.

public interface Pila<E>{ public int tamaño(); 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 métodos de la interfaz asociada con el TAD.

♦ Mediante arrays

♦ Problema: pila llena

♦ Solución:

− método privado duplicarPila() que lleve a cabo una expansión dinámica del vector

− un nuevo tipo de excepción, PilaLlenaExcepcion public class ArrayPila<E> implements Pila<E>{ public static final int CAPACIDAD_POR_DEFECTO=10; private E[]elementos; private int tope;

a1 a2 a3 a4 ... at

0 1 2 3 tope N-1



public ArrayPila(int capacidad){ elementos=(E[])new Object [capacidad]; tope=-1; } public ArrayPila (){ this(CAPACIDAD_POR_DEFECTO); } public int tamaño(){ 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 vacía"); 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; } }

♦ Implementación alternativa usando la clase Vector<E>

♦ Ventajas: implementación simple y eficiente

♦ Desventaja: límite superior en el tamaño del array



♦ Mediante listas enlazadas genéricas

♦ Se define una clase genérica 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 parámetro elemento=e; sig=n; } //métodos 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; }

Tope de la pila



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

♦ Se define una clase genérica 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 tamaño(){ 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; } }



2.3. Aplicaciones del TAD Pila

♦ Las pilas son una estructura de datos muy usada como estructura auxiliar en diversos algoritmos y esquemas de programación. Los casos más representativos son:

♦ Solitario, Laberinto, etc. (back tracking).

♦ Evaluación de expresiones aritméticas, conversión de notaciones (postfija, prefija, infija)...

♦ Llamadas a subprogramas

♦ Recursión.

2.3.1. Tratamiento de expresiones aritméticas ¿Cuál 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. ¿Cómo puede solucionarse?

♦ Paréntesis: (4*5) + (6 * 7)

♦ Usando otra notación para los símbolos.

Tipos de notación :

♦ Infija: A op B 4 * 5 + 6 * 7

♦ Postfija: A B op 4 5 * 6 7 * +

♦ Prefija: op A B + * 4 5 * 6 7

Una ventaja de la notación postfija es que no necesita paréntesis.



Conversión de notación infija a postfija Ejemplo: a + b * c + (d * e + f) * g a b c * + d e * 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 serían: ( +,- *, / d.2) push (P, op)

2. Cuando se llega al final de la entrada, se vacía 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 más a la derecha

Entrada Operación Pila Salida

‘a’ a la salida a

‘+’ Push ‘+’ a

‘b’ a la salida ‘+’ a b

‘*’ ‘+’ < ‘*’ push ‘*’ ‘+’ ‘*’ a b



‘c’ a la salida ‘+’ ‘*’ a b c

‘+’ mientras precedencia tope ‘+’ a b c * +

>= precedencia operador

hacer pop;

push ‘+’

‘(‘ push ‘(‘ ‘+’ ‘(’ a b c * +

‘d’ a la salida ‘+’ ‘(’ a b c * + d

‘*’ Push ‘+’ ‘(’ ‘*’ a b c * + d

‘e’ a la salida ‘+’ ‘(’ ‘*’ a b c * + d e

‘+’ mientras precedencia tope ‘+’ ‘(’ ‘+’ a b c * + d e *

>= precedencia operador

hacer pop;

push ‘+’

‘f’ a la salida ‘+’ ‘(’ ‘+’ a b c * + d e * f

‘)’ repetir pop hasta encontrar ‘(‘ ‘+’ a b c * + d e * f +

‘*’ push ‘+’ ‘*’ a b c * + d e * f +

‘g’ a la salida ‘+’ ‘*’ a b c * + d e * f + g

vaciar pila a b c * + d e * f + g * +



Evaluación de la notación postfija mediante una pila. ¿Cómo 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 operación 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 operación

Ejemplo: 4 5 * 6 7 * + Entrada Acción Pila 4 Push() 4 5 Push() 4 5 * Evaluar + push() 20 6 Push() 20 6 7 Push() 20 6 7 * Evaluar + push() 20 42 + Evaluar + push() 62

estructuras lineales java

Documents