Pilas y colas parte 2

Vista previa del material en texto

Algoritmos y Estructuras de 
Datos
Departamento de Informática
LAS - TUP
Unidad N° 4 - Parte II
Temario
Repaso de contenedores lineales: Pilas y Colas
Implementación
Array
Lista enlazada
Repaso de contenedores lineales: Pilas y Colas
Funcionamiento
Especificación del TAD
Métodos
Estructuras de Datos
Memoria: Espacio lógico para guardar información.
Memoria estática:Memoria que no se modifica en tiempo de 
ejecución.
Memoria dinámica:Memoria que puede variar en tiempo de 
ejecución.
Lineal
Almacenamiento contiguo
Almacenamiento no contiguo
Pila con Array
Tamaño?
Donde metemos?
Cuál sacamos?
Pila con Array
public class PilaArr implements OperacionesCL1 {
private Object[] pila;
private int cabeza;
private int tamPila;
La interfaz en JAVA
Public interface OperacionesCL1
{
public void meter(Object elemento);
Object public sacar();’
public void limpiar();
public boolean estaVacia();
}
Pila con Array
public class PilaArr implements OperacionesCL1 {
private Object[] pila;
private int cabeza;
private int tamPila;
.
.
.
Constructor?
Pila con Array
public void meter(Object elemento) {
if (!estaLlena()){
 incrementaCabeza();
 this.pila[this.cabeza] = elemento;
} else {
System.out.println("Error. Pila llena..");
}
}
Pila con Array
public Object sacar() {
Object elemento = null;
if (!estaVacia()){
elemento = this.pila[this.cabeza];
decrementaCabeza();
} else {
System.out.println("Error. Pila vacia..");
}
return elemento; 
}
Cola con Array
Tamaño?
Donde metemos?
Cuál sacamos?
Cuando está llena?
Cola con Array
Object[] cola
frenteC, finalC
frenteC registrará la posición del elemento precedente al ubicado al frente de 
COLA en vez de la posición del elemento ubicado al frente. De esta forma, se 
puede verificar fácilmente si COLA está llena o vacía.
Estructura circular
Capacidad?
Interfaz?
Cola con Array
public class ColaArr implements OperacionesCL1{
private Object[] cola;
private int finalC, frenteC;
private int tamCola;
.
.
.
Cola con Array
public void meter(Object elemento) {
if (!estaLlena()) {
if (this.finalC == this.tamCola - 1){
this.finalC = 0;
}else{
incrementaFinal(); 
}
this.cola[this.finalC] = elemento;
} else {
System.out.println("Error. Cola llena...");
}
}
Cola con Array
public Object sacar(){
Object elemento = null;
if (!estaVacia()){
if (this.frenteC==this.tamCola-1){
this.frenteC=0;
} else{
incrementaFrente();
}
elemento = this.cola[this.frenteC];
} else {
System.out.println(”Error. Cola vacia...”);
}
return elemento;
}
Pilas y colas 
con lista enlazada
Clase Nodo
public class Nodo {
private Object nodoInfo;
private Nodo nextNodo;
public Nodo(Object nodoInfo) {
this(nodoInfo,null);
} 
public Nodo(Object nodoInfo, Nodo nextNodo) {
this.nodoInfo = nodoInfo;
this.nextNodo = nextNodo; 
}
public void setNodoInfo(Object nodoInfo) - public void setNextNodo(Nodo nextNodo) 
public Object getNodoInfo() - public Nodo getNextNodo() }
Implementación de Pila con lista enlazada
Las operaciones de meter y sacar operan sobre el tope de la pila
Implementación de Pila con lista enlazada
public class PilaSLinkedList implements OperacionesCL1 {
private Nodo pila;
public void meter(Object elemento) {
this.pila = new Nodo(elemento, this.pila);
// la cabeza es el elemento ingresado!
} 
Implementación de Pila con lista enlazada
public Object sacar() {
Object elemento = null;
if (!estaVacia()){
elemento = this.pila.getNodoInfo();
this.pila = this.pila.getNextNodo();
}else{
System.out.println("Error sacar. Pila vacia");}
return elemento; 
}
Implementación de Cola con lista enlazada
Para mejorar la eficiencia del método meter se mantiene un puntero al final de la 
cola: frenteC, finalC
Implementación de Cola con lista enlazada
public class ColaSLinkedList implements OperacionesCL1 {
private Nodo frenteC, finalC;
public void meter(Object elemento) {
if (!estaVacia()) {
this.finalC.setNextNodo(new Nodo(elemento));
this.finalC = this.finalC.getNextNodo();
// nuevo nodo es el ultimo.
}else{
this.frenteC = null;
}
}
Implementación de Cola con lista enlazada
public Object sacar() {
Object elemento = null;
if (!estaVacia()) {
elemento = this.frenteC.getNodoInfo();
this.frenteC = this.frenteC.getNextNodo();
if (estaVacia()) {
this.finalC = null; 
}
}else{
System.out.println("Error sacar. Cola vacia");
}
return elemento;
}