PDF de programación - Estructuras de datos: Pilas, Colas, Listas

Pilas
Colas
Listas

Estructuras de datos: Pilas, Colas, Listas

Algoritmos

Facultad de Informática
Universidad de A Coruña

Algoritmos

Pilas, Colas, Listas

Table of Contents

Pilas
Colas
Listas

1 Pilas

Pseudocódigo
Código JAVA

2 Colas

Pseudocódigo
Código JAVA

3 Listas

Pseudocódigo

Algoritmos

Pilas, Colas, Listas

Table of Contents

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

1 Pilas

Pseudocódigo
Código JAVA

2 Colas

Pseudocódigo
Código JAVA

3 Listas

Pseudocódigo

Algoritmos

Pilas, Colas, Listas

Pilas

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

Acceso limitado al último elemento insertado
Operaciones básicas: apilar, desapilar y cima.

desapilar o cima en una pila vacía es un error en el TDA pila.
Quedarse sin espacio al apilar es un error de implementación.

Cada operación debería tardar una cantidad constante de tiempo
en ejecutarse.

Con independencia del número de elementos apiladas.

Algoritmos

Pilas, Colas, Listas

Implementación a base de vectores (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

tipo Pila = registro
Cima_de_pila : 0..Tamaño_máximo_de_pila
Vector_de_pila : vector [1..Tamaño_máximo_de_pila]

de Tipo_de_elemento

fin registro

procedimiento Crear Pila ( P )
P.Cima_de_pila := 0
fin procedimiento

función Pila Vacía ( P ) : test

devolver P.Cima_de_pila = 0

fin función

Algoritmos

Pilas, Colas, Listas

Implementación a base de vectores (ii)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

procedimiento Apilar ( x, P )

si P.Cima_de_pila = Tamaño_máximo_de_pila entonces

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

si Pila Vacía (P) entonces error Pila vacía
sino devolver P.Vector_de_pila[P.Cima de Pila]

fin función
procedimiento Desapilar ( P )

si Pila Vacía (P) entonces error Pila vacía
sino P.Cima_de_pila := P.Cima_de_pila - 1

fin procedimiento

Algoritmos

Pilas, Colas, Listas

Código JAVA: Interfaz Pila

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

// OPERACIONES PÚBLICAS
void apilar(x) ->Inserta x
//
void desapilar() ->Elimina el último elemento insertado
//
Object cima() ->Devuelve el último elemento insertado
//
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

Código JAVA: Clase PilaVec (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

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

Código JAVA: Clase PilaVec (ii)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

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

Table of Contents

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

1 Pilas

Pseudocódigo
Código JAVA

2 Colas

Pseudocódigo
Código JAVA

3 Listas

Pseudocódigo

Algoritmos

Pilas, Colas, Listas

Colas

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

Operaciones básicas: insertar, quitarPrimero y primero.
Cada rutina debería ejecutarse en tiempo constante.

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

La implementación circular devuelve cabeza y fin al principo del
vector cuando rebasan la última posición.

final

1) Crear Cola (C)

cabeza

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

La implementación circular devuelve cabeza y fin al principo del
vector cuando rebasan la última posición.

final

1) Crear Cola (C)

2) Insertar en Cola (a,C)

cabeza

final
a
cabeza

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

La implementación circular devuelve cabeza y fin al principo del
vector cuando rebasan la última posición.

final

1) Crear Cola (C)

2) Insertar en Cola (a,C)

3) Insertar en Cola (b,C)

cabeza

final
a
cabeza

a
cabeza

final
b

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

Implementación circular a base de vectores (i)

4) Insertar en Cola (c,C)

a
cabeza

b

final
c

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

4) Insertar en Cola (c,C)

5) Insertar en Cola (d,C)

a
cabeza

a
cabeza

b

b

final
c

c

final
d

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

4) Insertar en Cola (c,C)

5) Insertar en Cola (d,C)

a
cabeza

a
cabeza

b

b

6) Quitar Primero (C)

b
cabeza

final
c

c

c

final
d

final
d

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

4) Insertar en Cola (c,C)

5) Insertar en Cola (d,C)

a
cabeza

a
cabeza

b

b

6) Quitar Primero (C)

7) Insertar en Cola (e,C)

final
e

b
cabeza

b
cabeza

Algoritmos

Pilas, Colas, Listas

final
c

c

c

c

final
d

final
d

d

Pseudocódigo (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

tipo Cola = registro

Cabeza_de_cola, Final_de_cola: 1..Tamaño_máximo_de_cola
Tamaño_de_cola : 0..Tamaño_máximo_de_cola
Vector_de_cola : vector [1..Tamaño_máximo_de_cola]

de Tipo_de_elemento

fin registro
procedimiento Crear_Cola ( C )

C.Tamaño_de_cola := 0;
C.Cabeza_de_cola := 1;
C.Final_de_cola := Tamaño_máximo_de_cola

fin procedimiento
función Cola_Vacía ( C ) : test
devolver C.Tamaño_de_cola = 0

fin función

Algoritmos

Pilas, Colas, Listas

Pseudocódigo (ii)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

procedimiento incrementar ( x ) (* privado *)
si x = Tamaño_máximo_de_cola entonces x := 1
sino x := x + 1

fin procedimiento

procedimiento Insertar_en_Cola ( x, C )

si C.Tamaño_de_Cola = Tamaño_máximo_de_cola entonces

error Cola llena

sino

C.Tamaño_de_cola := C.Tamaño_de_cola + 1;
incrementar(C.Final_de_cola);
C.Vector_de_cola[C.Final_de_cola] := x;

fin procedimiento

Algoritmos

Pilas, Colas, Listas

Pseudocódigo (iii)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

función Quitar_Primero ( C ) : Tipo_de_elemento

si Cola_Vacía ( C ) entonces

error Cola vacía

sino

C.Tamaño_de_cola := C.Tamaño_de_cola - 1;
x := C.Vector_de_cola[C.Cabeza_de_cola];
incrementar(C.Cabeza_de_cola);
devolver x

fin función
función Primero ( C ) : Tipo_de_elemento

si Cola_Vacía ( C ) entonces

error Cola vacía

sino

devolver Vector_de_cola[C.Cabeza_de_cola]

fin función

Algoritmos

Pilas, Colas, Listas

Código JAVA: Interfaz Cola

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

void insertar(x) -> Inserta x
Object primero() -> Devuelve el primer elemento
Object quitarPrimero() -> Devuelve y elimina el primer elemento
boolean esVacia() -> Devuelve true si vacía, si no false
void vaciar() -> Elimina todos los elementos

// OPERACIONES PÚBLICAS
//
//
//
//
//
// ERRORES: primer y quitarPrimero sobre una cola vacía
public interface ICola {

void insertar(Object x);
Object primero() throws Exception;
Object quitarPrimero() throws Exception;
boolean esVacia();
void vaciar();

}

Algoritmos

Pilas, Colas, Listas

Código JAVA: Clase ColasVec (i)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

public class ColaVec implements ICola {

private Object [] vector;
private int tamanoActual;
private int cabezaDeCola;
private int finalDeCola;
static final int CAPACIDAD_POR_DEFECTO = 10;
public ColaVec() {

vector = new Object[CAPACIDAD_POR_DEFECTO];
vaciar();

}
public void vaciar() {
tamanoActual = 0;
cabezaDeCola = 0;
finalDeCola = -1;

}

Algoritmos

Pilas, Colas, Listas

Código JAVA: Clase ColaVec (ii)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

public boolean esVacia() {

return (tamanoActual == 0);

}

public Object primero() throws Exception {

if (esVacia()) throw new Exception("cola vacía");
return vector[cabezaDeCola];

}

private int incrementar(int x) {

if (++x == vector.length)

x = 0;
return x;

}

Algoritmos

Pilas, Colas, Listas

Código JAVA: Clase ColaVec (iii)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

public Object quitarPrimero() throws Exception {

if (esVacia())

throw new Exception("cola vacía");

tamanoActual--;
Object valorDevuelto = vector[cabezaDeCola];
cabezaDeCola = incrementar(cabezaDeCola);
return valorDevuelto;

}
public void insertar(Object x) {

if (tamanoActual == vector.length)

duplicarCola();

finalDeCola = incrementar(finalDeCola);
vector[finalDeCola] = x;
tamanoActual++;

}

Algoritmos

Pilas, Colas, Listas

Código JAVA: Clase ColaVec (iv)

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

private void duplicarCola() {

Object [] nuevoVector =

new Object[2*vector.length];

for (int i=0; i<tamanoActual; i++,

cabezaDeCola = incrementar(cabezaDeCola))

nuevoVector[i] = vector[cabezaDeCola];

vector = nuevoVector;
cabezaDeCola = 0;
finalDeCola = tamanoActual - 1;

}

}

Algoritmos

Pilas, Colas, Listas

Amortización de la duplicación del vector

Pilas
Colas
Listas

Pseudoc ódigo
C ódigo JAVA

Cuando el vector no se duplica, toda operación