creacion de pilas en java

Tema 8- Implementación de Pila, Cola y
Lista con Punto de Interés

Tema 8- Implementación de Pila,
Cola y Lista con Punto de Interés

Índice general:
1.
Representación Eficaz de una EDA Lineal
2.
Implementación de Pila: La Clase ArrayPila
3.
Implementación de Cola: La Clase ArrayCola
4.
I l
Implementación
ió d
de Li
Lista Con
C Punto
P
de
d Interés:
I
é La
L Clase
Cl
LEGListaConPI

Germán MoltóEscuela Técnica Superior de Ingeniería Informática
Uni ersidad Politécnica de Valencia
Universidad

1

Objetivos y Bibliografía
Desarrollar las implementaciones más eficientes de las
Estructuras de Datos lineales Pila, Cola y Lista con Punto
de Interés.







La clase ArrayPila como implementación de la interfaz Pila.
La clase ArrayCola como implementación de la interfaz Cola.
L clase
La
lLEGListaConPI
LEGLi C PI como implementación
i l
ió d
de lla iinterfaz
f
ListaConPI.

2

Representación Eficaz de una EDA
Lineal
Las implementaciones de Pila, Cola y Lista deben permitir que
sus operaciones básicas se ejecuten en tiempo constante.
constante





Así, los recorridos y búsquedas simples tendrán coste
temporal acotado por el número de elementos de la EDA:





BibliografíaPrincipal:


3

Lineal (o proporcional) con el número de elementos de la EDA.

La implementación de los métodos depende de la
representación de la colección de datos:
 Representación
p
contigua:
g Arrayy
 Representación enlazada: Lista Enlazada Genérica





Tiempo constante: Independiente del número de elementos de la EDA.

Capítulo 15 del libro de M
M.A.
A Weiss: “Estructuras
Estructuras de Datosen
Java”. Adisson-Wesley, 2000.

4

Claves para implementar una EDA
lineal
Inicialmente, representamos los datos de la EDA sobre un array de
CAPACIDAD POR DEFECTO componentes.
CAPACIDAD_POR_DEFECTO
Si la EDA requiere alguna forma de acceso especial (por ejemplo
FIFO o LIFO),
LIFO) definir nuevos atributos que los representen para
implementar el acceso eficazmente.
Analizar el coste de cada una delas operaciones de la interfaz
implementada.

Si alguna operación requiere desplazamiento de datos en la
representación
t ió interna,
i t
se descarta
d
t la
l representación
t ió como un
array.
Ensayar una implementación del interfaz con una representación
basada en Lista Enlazada.

1.
2.

3.

4
4.

5

Pila en la qque se han insertado, por
p este órden, los
elementos A, B, C y D
Visión desde elpunto de vista del modelo:



tope

D
C

Una Pila es una colección homogénea de
datos que sólo se puede gestionar
accediendo secuencialmente al dato que
ocupa el Punto de Interés,
Interés siguiendo un
criterio LIFO (Last In First Out), esto es,
accediendo al dato que ocupa el tope de
la pila, es decir, el último que se insertó.

public interface Pila {
void apilar(E x);
E desapilar();
E tope();b l
boolean
esVacia();
V i ()
}

y
implementa
p
el interfaz Pila.
• La clase ArrayPila
• Atributos principales:
• Un array para almacenar los elementos de la Pila.
• Una
U capacidad
id d iinicial
i i l para ell vector.
t
• Un marcador al tope de la pila (la posición en el vector del último
elemento insertado), inicialmente valdrá -1.

A

• Punto de vista de la implementación:
A

B

Clase ArrayPila(1/3)
package librerias.estructurasDeDatos.lineales;
import librerias.estructurasDeDatos.modelos.
librerias estructurasDeDatos modelos *;;
public class ArrayPila implements Pila {
protected E elArray[];
protected int tope;
protected static final int CAPACIDAD_POR_DEFECTO = 200;
@SuppressWarnings("unchecked")

B

C

D

tope
7



6

Esquema de Implementación de Pila


Implementación dePila: La Clase
ArrayPila

elArray
lA

public ArrayPila () {
elArray=
y (E[])
( []) new Object[CAPACIDAD
j [
_POR_DEFECTO];
]
tope = -1;
}
public void apilar(E x) {
if ( tope + 1 == elArray.length) duplicarArray();
tope++; elArray[tope] = x;
¿Qué ocurre si se trata de apilar un nuevo
elemento
l
t y elArray
lA
está
tá completo?
l t ?
}
8

Clase ArrayPila (2/3)
public E desapilar() {
E elUltimo =...

Leer documento completo

Regístrate para leer el documento completo.