Pilas-Colas-Listas Java

Pilas Colas Listas

Estructuras de datos: Pilas, Colas, Listas
Algoritmos
´ Facultad de Informatica ˜ Universidad de A Coruna

Algoritmos

Pilas, Colas, Listas

Pilas Colas Listas

Table of Contents

1

Pilas ´ Pseudocodigo ´ Codigo J AVA Colas ´ Pseudocodigo ´ Codigo J AVA Listas ´ Pseudocodigo

2

3

Algoritmos

Pilas, Colas, Listas

Pilas Colas Listas

´Pseudocodigo ´ Codigo J AVA

Table of Contents

1

Pilas ´ Pseudocodigo ´ Codigo J AVA Colas ´ Pseudocodigo ´ Codigo J AVA Listas ´ Pseudocodigo

2

3

Algoritmos

Pilas, Colas, Listas

Pilas Colas Listas

´ Pseudocodigo ´ Codigo J AVA

Pilas

Acceso limitado al ultimo elemento insertado ´ ´ Operaciones basicas: apilar, desapilar y cima. desapilar o cima en una pila vac´a es un erroren el TDA pila. ı ´ Quedarse sin espacio al apilar es un error de implementacion. ´ Cada operacion deber´a tardar una cantidad constante de tiempo ı en ejecutarse.
Con independencia del numero de elementos apiladas. ´

Algoritmos

Pilas, Colas, Listas

Pilas Colas Listas

´ Pseudocodigo ´ Codigo J AVA

´ Implementacion a base de vectores (i)
tipo Pila = registro Cima_de_pila :0..Tama˜o_m´ximo_de_pila n a Vector_de_pila : vector [1..Tama˜o_m´ximo_de_pila] n a de Tipo_de_elemento fin registro procedimiento Crear Pila ( P ) P.Cima_de_pila := 0 fin procedimiento funci´n Pila Vac´a ( P ) : test o ı devolver P.Cima_de_pila = 0 fin funci´n o
Algoritmos Pilas, Colas, Listas

Pilas Colas Listas

´ Pseudocodigo ´ Codigo J AVA

´ Implementacion a base de vectores (ii)procedimiento Apilar ( x, P ) si P.Cima_de_pila = Tama˜o_m´ximo_de_pila entonces n a error Pila llena sino P.Cima_de_pila := P.Cima_de_pila + 1; P.Vector_de_pila[P.Cima_de_pila] := x fin procedimiento funci´n Cima ( P ) : Tipo_de_elemento o si Pila Vac´a (P) entonces error Pila vac´a ı ı sino devolver P.Vector_de_pila[P.Cima de Pila] fin funci´n o procedimiento Desapilar ( P ) si Pila Vac´a (P) entonceserror Pila vac´a ı ı sino P.Cima_de_pila := P.Cima_de_pila - 1 fin procedimiento
Algoritmos Pilas, Colas, Listas

Pilas Colas Listas

´ Pseudocodigo ´ Codigo J AVA

´ Codigo J AVA: Interfaz Pila
´ // OPERACIONES PUBLICAS // void apilar(x) ->Inserta x // void desapilar() ->Elimina el ´ltimo elemento insertado u // Object cima() ->Devuelve el ´ltimo elemento insertado u // boolean esVacia()->Devuelve true si vac´a, sino false ı // void vaciar() ->Elimina todos los elementos // ERRORES: cima o desapilar sobre la pila vac´a ı public interface IPila { void apilar(Object x); void desapilar() throws Exception; Object cima() throws Exception; boolean esVacia(); void vaciar(); }
Algoritmos Pilas, Colas, Listas

Pilas Colas Listas

´ Pseudocodigo ´ Codigo J AVA

´ Codigo J AVA:Clase PilaVec (i)
import java.util.*; public class PilaVec implements IPila { private Vector p; private int cimaDePila; static final int CAPACIDAD_POR_DEFECTO = 10; public PilaVec() { p = new Vector(CAPACIDAD_POR_DEFECTO); cimaDePila = -1; } public boolean esVacia() { return (cimaDePila == -1); } public void vaciar() { cimaDePila = -1; }
Algoritmos Pilas, Colas, Listas

Pilas Colas Listas

´Pseudocodigo ´ Codigo J AVA

´ Codigo J AVA: Clase PilaVec (ii)
public void apilar(Object x) { if (++cimaDePila == p.size()) p.add(x); else p.set(cimaDePila, x); } public void desapilar() throws Exception { if (esVacia()) throw new Exception("pila vac´a"); ı cimaDePila--; } public Object cima() throws Exception { if (esVacia()) throw new Exception("pila vac´a"); ı return p.get(cimaDePila); } }Algoritmos Pilas, Colas, Listas

Pilas Colas Listas

´ Pseudocodigo ´ Codigo J AVA

Table of Contents

1

Pilas ´ Pseudocodigo ´ Codigo J AVA Colas ´ Pseudocodigo ´ Codigo J AVA Listas ´ Pseudocodigo

2

3

Algoritmos

Pilas, Colas, Listas

Pilas Colas Listas

´ Pseudocodigo ´ Codigo J AVA

Colas

´ Operaciones basicas: insertar, quitarPrimero y primero. Cada rutina...