Tema6
-
Upload
pedro-sanchez -
Category
Technology
-
view
133 -
download
5
Transcript of Tema6
EstucturasEstucturas de Datosde Datos PPáágina gina 11
Unidad III
Tema 6: Pilas, Colas y Listas
Profesor: Jorge Escalona / Tobías Bolívar
Email: [email protected] / [email protected]
Página Web: http://estructuradatos.tripod.com
EstucturasEstucturas de Datosde Datos PPáágina gina 22
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
• Pilas
• Colas
• DiColas
• Listas Enlazadas
– Listas Simplemente Enlazadas
– Listas Doblemente Enlazadas
Contenido: 12
3
4
n
frente final
Roma Caracas Paris
cabecera
EstucturasEstucturas de Datosde Datos PPáágina gina 33
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Pilas
• Una Pila es un contenedor de objetos que son insertados y removidos de
acuerdo al principio Last-In First-Out (LIFO).
• Operaciones básicas:
Inserta el objeto elem en la cima de la pila.
Entrada:Object; Salida: Ninguna
Remueve y retorna el objeto de la cima de la pila. Un error ocurre si
la pila está vacía.
Entrada: Object; Salida: Object.
Retorna el número de objetos en la pila.
Entrada: Ninguna; Salida: Entero;
Retorna un valor booleano inicando si la pila está vacía.
Entrada: Ninguna: Salida: Boolean
Retorna el objeto de la cima de la pila, sin removerlo;
Entrada: Ninguna; Salida: Object
Agregar(elem):
Remover(elem):
Longitud():
PilaVacia():
Cima()
EstucturasEstucturas de Datosde Datos PPáágina gina 44
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Pilas - Implementación con un Arreglo
Algoritmo Longitud():
return cima + 1.
Algoritmo PilaVacia():
return (cima<0).
Algoritmo Cima():
if PilaVacia() then
Generar ErrorPilaVacia
return Elementos[cima].
Algoritmo Agregar(elem):
if Longitud() = Max then
generar ErrorPilaLlena
cima ← cima + 1
Elementos[cima] ← elem.
Algoritmo Remover():
if PilaVacia() then
generar ErrorPilaVacia
elem -> elementos[cima]
elementos[cima] ← null
cima ← cima - 1
return elem.
EstucturasEstucturas de Datosde Datos PPáágina gina 55
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Colas
• Una Cola es un contenedor de objetos que son insertados y removidos de
acuerdo al principio FIFO (First-in First-Out).• Operaciones básicas:
Inserta el objeto elem al final de la cola.
Entrada:Object; Salida: Ninguna
Remueve y retorna el objeto del frente de la cola. Un error ocurre si
la cola está vacía.
Entrada: Object; Salida: Object.
Retorna el número de objetos en la cola.
Entrada: Ninguna; Salida: Entero;
Retorna un valor booleano inicando si la cola está vacía.
Entrada: Ninguna: Salida: Boolean
Retorna el objeto del frente de la cola, sin removerlo;
Entrada: Ninguna; Salida: Object
Agregar(elem):
Remover(elem):
Longitud():
ColaVacia():
Frente()
EstucturasEstucturas de Datosde Datos PPáágina gina 66
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Colas - Implementaciones con Arreglos Lineales
•Se utilizan dos índices para manipular la cola: frente (elemento al inicio) y final (elemento en
el final).
•Para agregar un elemento, se incrementa el índice final, considerando que la cola no esté
llena (final = max).
1 2 3 4 .... n
D S A
frente final
1 2 3 4 .... n
D S A P
frente final
A) Cola Original. B) Cola resultante después de insertar el
elemento ‘P’.
EstucturasEstucturas de Datosde Datos PPáágina gina 77
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Colas - Implementaciones con Arreglos Lineales
•Para remover un elemento, se tienen dos opciones:
•Se incrementa el índice frente para apuntar al siguiente elemento. La desventaja
de esta opción es que se puede subutilizar el espacio del arreglo.
•Se mantiene el índice frente siempre en la primera posición del arreglo y se
mueven los elementos en la cola una posición. La desventaja de esta opción es el
costo de desplazar los elementos para una cola medianamente grande.
1 2 3 4 .... n
D S A P
frente final
A) Cola Original. B) Cola resultante después de eliminar un elemento.
1 2 3 4 .... n
D S A P
frente final
A) Cola Original.
1 2 3 4 .... n
S A P
frente final
B) Cola resultante después de eliminar un elemento.
1 2 3 4 .... n
S A P
frente final
EstucturasEstucturas de Datosde Datos PPáágina gina 88
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Colas - Implementaciones con Arreglos Circulares
• Se puede seguir agregando elementos a la cola aún si el índice frente apunta al último
elemento del arreglo, insertándolo en la primera posición si no está ocupada.
• Para agregar un elemento se mueve el índice final hacia delante una posición según la siguiente fórmula: final ← (final + 1) mod N
• Para eliminar un elemento se mueve el índice frente hacia delante una posición según la siguiente fórmula: frente ← (frente + 1) mod N
12
3
4
n
frente final
12
3
4
n
frente
final1
23
4
n
frente
final
EstucturasEstucturas de Datosde Datos PPáágina gina 99
Colas - Implementaciones con Arreglos Circulares
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
• Inicialmente, tanto el índice frente como final, apuntan al primer elemento del arreglo. De
aquí, se establece la condición de cola vacía si frente = final. (figura a)
• El índice final, siempre apunta a una posición vacía del arreglo, la siguiente al último
elemento de la cola. (figura b)
• Para evitar que después de insertar n elementos sin desencolar ninguno, final vuelva a
apuntar a frente, lo cual haría coincidir las condiciones de pila vacia con la de pila llena, se
sacrifica una posición del arreglo, de tal forma que la condición de pila llena se presenta
cuando siguiente(final) = frente. (figura c)
12
3
4
n
frente final
12
3
4
n
frente
finalDG
X
n-1 n-11
23
4
n
DGX
n-1
frente
L
K
.
..
. . ....
(Figura a) (Figura b) (Figura c)
final
EstucturasEstucturas de Datosde Datos PPáágina gina 1010
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Colas - Implementación con Arreglos Circulares
Algoritmo Longitud():
return
(Max-frente+final) mod Max.
Algoritmo ColaVacia():
return (frente = final).
Algoritmo Frente():
if ColaVacia() then
Generar ErrorColaVacia
return Elementos[frente].
Algoritmo Encolar(elem):
if Longitud() = Max - 1 then
generar ErrorColaLlena
Elementos[final] ← elem
final ← (final + 1) mod Max.
Algoritmo Desencolar():
if ColaVacia() then
generar ErrorColaVacia
elem -> elementos[frente]
elementos[frente] ← null
frente ← (frente + 1) mod Max
return elem.
Nota: Las fórmulas para el cálculo de
frente y final son válidas si la numeración
del arreglo comienza en cero. Para
arreglos cuya numeración comience en 1,
hay que sumarles 1 al resultado de la
fórmula.
EstucturasEstucturas de Datosde Datos PPáágina gina 1111
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
DiColas
• Una DiCola es un contenedor de objetos que pueden ser insertados y
removidos tanto como por el inicio como por el final.
• Operaciones básicas:
Inserta el objeto elem al inicio de la cola.Entrada:Object; Salida: Ninguna
Inserta el objeto elem al final de la cola.Entrada:Object; Salida: Ninguna
Remueve y retorna el objeto del frente de la cola. Entrada: Object; Salida: Object.
Remueve y retorna el objeto del final de la cola. Entrada: Object; Salida: Object.
Retorna el número de objetos en la cola.Entrada: Ninguna; Salida: Entero;
Retorna un valor booleano inicando si la cola está vacía.Entrada: Ninguna: Salida: Boolean
Retorna el objeto del frente de la cola, sin removerlo;Entrada: Ninguna; Salida: Object
Retorna el objeto del final de la cola, sin removerlo;Entrada: Ninguna; Salida: Object
AgregarInicio(elem):
AgregarFinal(elem):
RemoverInicio(elem):
RemoverFinal(elem):
Longitud( ):
DiColaVacia( ):
Frente( ):
Final( ):
EstucturasEstucturas de Datosde Datos PPáágina gina 1212
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Implementando Pilas y Colas con DiColas
Métodos de Pila
Longitud()
PilaVacia()
Cima()
Agregar(elem)
Remover()
Métodos de DiCola
Longitud()
DiColaVacia()
Final()
AgregarFinal(elem)
RemoverFinal()
Métodos de Cola
Longitud()
ColaVacia()
Frente()
Agregar(elem)
Remover()
Métodos de DiCola
Longitud()
DiColaVacia()
Frente()
AgregarFinal(elem)
RemoverFrente()
• Implementando
una Pila con una
DiCola
• Implementando
una Cola con una
DiCola
EstucturasEstucturas de Datosde Datos PPáágina gina 1313
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Implementando Pilas y Colas con DiColas
• Usando una DiCola para implementar una Pila o una Cola, es un ejemplo de
un adaptador de plantilla. Un adaptador de plantilla, implementa una clase
utilizando métodos de alguna otra clase.
• En general, un adaptador de una clase especializa una clase más general.
• Se puede aplicar de dos formas:
• Especializar una clase más general modificando algunos métodos.
Ejemplo: Implementar una Pila con una DiCola.
• Especializar los tipos de objetos usados por una clase más general.
Ejemplo: Definir una clase PilaEnteros que la clase Pilas para sólo
almacenar números enteros.
EstucturasEstucturas de Datosde Datos PPáágina gina 1414
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Listas Enlazadas
• Una lista enlazada es un tipo general de una estructura de dato utilizada
para almacenar una colección de elementos sin un tamaño predefinido.
• Alternativa para representar estructuras de datos lineales donde no se conoce
de antemano la cantidad de elementos a almacenar.
• La forma más simple de una lista enlazada es una lista simplemente enlazada, la cual consiste de una colección de nodos que juntos forman una
colección lineal.
Nueva York Roma Caracas
cabecera
sig sig sig sig
elemento elemento elemento elemento
Paris
EstucturasEstucturas de Datosde Datos PPáágina gina 1515
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Listas Simplemente Enlazadas
• En una lista simplemente enlazada, cada nodo es un objeto compuesto que
guarda una referencia a un elemento y una referencia, llamada siguiente(next), a otro nodo.
• El primer y último nodo de una lista enlazada usualmente son llamados el
nodo cabecera (head) y el nodo cola (tail), respectivamente.
• Se identifica la cola como el nodo que tiene en siguiente una referencia null,
lo cual indica el fin de la lista.
• El enlace al siguiente elemento nos permite alcanzar cualquier nodo de la
lista comenzando desde el nodo cabecera. A esta operación se le llama
recorrer la lista.
Nueva York Roma Caracas
cabecera
sig sig sig sig
elemento elemento elemento elemento
Paris
EstucturasEstucturas de Datosde Datos PPáágina gina 1616
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Implementación de Listas Simplemente Enlazadas
• Para implementar una lista simplemente enlazada se definen dos clases:
• La clase Nodo, la cual especifica el formato de los objetos asociados con
los nodos de la lista;
• La clase ListaEnlazada, la cual mantiene una referencia al nodo
cabecera de la lista y, adicionalmente, cualquier otra información que
pueda facilitar la manipulación de la lista. Como por ejemplo, una
referencia al nodo cola, o el número de elementos que existen en la lista.
EstucturasEstucturas de Datosde Datos PPáágina gina 1717
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Inserción y Eliminación en la cabecera de la lista.
Nueva York Roma Caracas Paris
Nueva York Roma Caracas Paris
cabecera
cabecera
Roma Caracas Paris
cabecera
EstucturasEstucturas de Datosde Datos PPáágina gina 1818
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Implementando una Pila con una Lista Simplemente Enlazada
• La implementación del TAD Pila utilizando una Lista Simplemente Enlazada
es bastante sencilla.
• Se utiliza la cabecera como la cima de la pila ya que la operación de
eliminación es más facil por este extremo de la lista que por la cola.
• Para facilidad y rapidez en ejecución de los métodos del TAD Pila, se
mantiene un contador del número de elementos actuales de la lista.
• La implementación de una pila sobre una lista simplemente enlazada tiene
una importante ventaja sobre la implementación basada en un arreglo, ya que
no requiere que se defina explícitamente un límite superior al tamaño de la
pila, por lo cual es libre de crecer o decrecer arbitrariamente.
Roma Caracas Paris
cabecera (cima)
EstucturasEstucturas de Datosde Datos PPáágina gina 1919
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Implementando una Cola con una Lista Simplemente Enlazada
• Al igual que para el TAD Pila, la implementación del TAD Cola utilizando una
Lista Simplemente Enlazada es bastante sencilla.
• Se utiliza la cabecera como el frente de la cola y el último nodo (nodo cola)
como el final de la cola. Por qué no lo contrario?
• Para facilidad y rapidez en ejecución de los métodos del TAD Cola, se
mantiene un contador del número de elementos actuales de la lista.
• A pesar de que la implementación de una cola sobre una lista simplemente
enlazada presenta las mismas ventajas que una pila sobre un arreglo, la
implementación de los métodos es un poco más complicada.
Roma Caracas Paris
cabecera (frente) final
EstucturasEstucturas de Datosde Datos PPáágina gina 2020
Unidad III: Estructuras de Datos LinealesUnidad III: Estructuras de Datos Lineales
Implementando una DiCola con una Lista Doblemente Enlazada• Remover un elemento en el final de una lista simplemente enlazada no puede ser
realizado en tiempo lineal.
• Para evitar este problema, la implementación de una DiCola se basa en una lista doblemente enlazada.
• Cada uno de los nodos de la lista doblemente enlazada tiene un enlace siguiente (elemento siguiente) y un enlace previo (elemento anterior).
• Se utilizan nodos especiales de cabecera (header) y remolque (trailer).
• El nodo cabecera va antes del primer elemento de la lista. Tiene un enlace
siguiente válido, pero un enlace previo nulo.
• El nodo remolque va después del último elemento de la lista. Tiene un enlace
previo válido, pero un enlace siguiente nulo.
• Los nodos cabecera y remolque son sólo nodos sentinelas; ellos no guardan ningún
elemento.
Roma Caracas Paris
cabecera remolque
EstucturasEstucturas de Datosde Datos PPáágina gina 2121
Unidad III: El Java Unidad III: El Java CollectionsCollections Framework (JFC)Framework (JFC)
• El Java Collections Framework (JFC) es una arquitectura unificada para
representar y manipular colecciones. Contiene los siguientes
elementos:
– Interfaces: Tipos abstractos de datos que representan las colecciones.
Permiten manipularlas con independencia de los detalles de su
implementación.
– Implementaciones: clases que implementan las interfaces anteriores.
– Algoritmos: Métodos que realizan de forma eficiente tareas habituales,
como búsquedas y ordenaciones, sobre objetos que implementan las
interfaces de la estructura de colecciones.
EstucturasEstucturas de Datosde Datos PPáágina gina 2222
Unidad III: El Java Unidad III: El Java CollectionsCollections Framework (JFC)Framework (JFC)
• Las interfaces del JFC encapsulan diferentes tipos de colecciones las cuales permiten que sean manipuladas independientemente de su implementación.
• Todas las interfaces son definidas de forma genérica. Por ejemplo, la declaración de la interfaz Collection está definida de la siguiente manera:
public interface Collection<E>...
Interfaces:
EstucturasEstucturas de Datosde Datos PPáágina gina 2323
Unidad III: El Java Unidad III: El Java CollectionsCollections Framework (JFC)Framework (JFC)
• Collection: Es la raíz de la jerarquía de las colecciones. Representa un grupo de objetos conocidos como sus elementos.
• Set: Una colección que no permite elementos duplicados. Esta interfaz modela la definición de conjuntos matemáticos.
• List: Una colección o secuencia ordenada. Permite elementos duplicados.
• Queue: Una colección usada para almacenar múltiples elementos con prioridad para su procesamiento.
• Map: Un objeto que mapea claves con valores. Un objeto Map no puede contener claves duplicadas.
• SortedSet: Un conjunto que mantiene sus elementos en orden ascendente.
• SortedMap: Un objeto Map que mantiene sus valores mapeados en orden ascendente según la clave de cada mapeo.
Interfaces:
EstucturasEstucturas de Datosde Datos PPáágina gina 2424
Unidad III: El Java Unidad III: El Java CollectionsCollections Framework (JFC)Framework (JFC)
• Son las clases que implementan las interfaces del JFC.
Manejan los datos contenidos en las colecciones.
Implementaciones:
EstucturasEstucturas de Datosde Datos PPáágina gina 2525
Unidad III: Tipos GenUnidad III: Tipos Genééricos en Java ricos en Java ((GenericsGenerics))
public class Box {
private Object object;
public void add(Object object) {
this.object = object;
}
public Object get() {
return object;
}
}
Ejemplo 1: Uso de una clase que almacena un Object
EstucturasEstucturas de Datosde Datos PPáágina gina 2626
Unidad III: Tipos GenUnidad III: Tipos Genééricos en Java ricos en Java ((GenericsGenerics))
public class BoxDemo1 {
public static void main(String[] args) {
Box integerBox = new Box();
integerBox.add(new Integer(10));
Integer someInteger = (Integer)integerBox.get();
System.out.println(someInteger);
}
}
Ejemplo 1: Uso de una clase que almacena un Object
EstucturasEstucturas de Datosde Datos PPáágina gina 2727
Unidad III: Tipos GenUnidad III: Tipos Genééricos en Java ricos en Java ((GenericsGenerics))
public class BoxDemo2 {
public static void main(String[] args) {
Box integerBox = new Box();
integerBox.add("10");
// note que el tipo es ahora una cadena
Integer someInteger = (Integer)integerBox.get();
System.out.println(someInteger);
}
}
Ejemplo 1: Uso de una clase que almacena un Object
Error en Tiempo de Ejecución:
Exception in thread "main"
java.lang.ClassCastException:
java.lang.String cannot be cast to java.lang.Integer at
BoxDemo2.main(BoxDemo2.java:5)
EstucturasEstucturas de Datosde Datos PPáágina gina 2828
Unidad III: Tipos GenUnidad III: Tipos Genééricos en Java ricos en Java ((GenericsGenerics))
/** * Versión genérica de la clase Box */
public class Box<T> {
private T t; // T de "Type"
public void add(T t) {
this.t = t;
}
public T get() {
return t;
}
}
Ejemplo 2: Uso de Tipo Genérico
EstucturasEstucturas de Datosde Datos PPáágina gina 2929
Unidad III: Tipos GenUnidad III: Tipos Genééricos en Java ricos en Java ((GenericsGenerics))
/** * Uso de la Versión genérica de la clase Box */
public class BoxDemo3 {
public static void main(String[] args) {
Box<Integer> integerBox = new Box<Integer>();
integerBox.add(new Integer(10));
Integer someInteger = integerBox.get(); // no cast!
System.out.println(someInteger);
}
}
Ejemplo 2: Uso de Tipo Genérico
EstucturasEstucturas de Datosde Datos PPáágina gina 3030
Unidad III: Tipos GenUnidad III: Tipos Genééricos en Java ricos en Java ((GenericsGenerics))
Ejemplo 3: Uso de Tipo Genérico
/** * Uso de la Versión genérica de la clase Box */
public class BoxDemo3 {
public static void main(String[] args) {
Box<Integer> integerBox = new Box<Integer>();
integerBox.add(new Integer(10));
Integer someInteger = integerBox.get(); // no cast!
System.out.println(someInteger);
}
}
Error en Tiempo de Compilación:
BoxDemo3.java:5: add(java.lang.Integer) in
Box<java.lang.Integer> cannot be applied to
(java.lang.String) integerBox.add("10");
^ 1 error