Departamento de Ciencias e Ingeniería de la Computación Universidad Nacional del Sur Bahía Blanca, Argentina
– Definición – Implementación – Especificación formal Estructuras de datos ‐ Dr. Sergio A. Gómez
TDA Pila (Stack)
Aplicaciones de Pilas
Pila: Colección de objetos actualizada usando una política LIFO (last‐in first‐out, el primero en entrar es el último en salir).
• Navegador web (browser): Registro de páginas visitadas (implementación de operación “back”) • Editor de textos: Implementación de mecanismo comportamiento de teclas Retroceso y Escape. • Ejecución de procedimientos y funciones (recursivos o no): Organización de los registros de activación • Validación de código HTML • Compilación de una expresión y cálculo de su valor: Paso de notación infija a postfija
Operaciones: • push(e): Inserta el elemento e en el tope de la pila • pop(): Elimina el elemento del tope de la pila y lo entrega como resultado. Si se aplica a una pila vacía, produce una situación de error. • isEmpty(): Retorna verdadero si la pila no contiene elementos y falso en caso contrario. • top(): Retorna el elemento del tope de la pila. Si se aplica a una pila vacía, produce una situación de error. • size(): Retorna un entero natural que indica cuántos elementos hay en la pila. Estructuras de datos ‐ Dr. Sergio A. Gómez
3
Estructuras de datos ‐ Dr. Sergio A. Gómez
• Navegador web (browser): Registro de páginas visitadas (implementación de operación “back”) Pila de URLs (Pila de Strings) • Editor de textos: Implementación de mecanismo comportamiento de teclas Retroceso y Escape. Pila de caracteres • Ejecución de procedimientos y funciones (recursivos o no): Organización de los registros de activación Pila de registros de activación • Validación de código HTML Pila de Tags (pila de strings) • Compilación de una expresión y cálculo de su valor: Paso de notación infija a postfija Pilas de símbolos (operadores y operandos).
4
Implementación de Pila
Aplicaciones de Pilas: Tipo de los objetos
Estructuras de datos ‐ Dr. Sergio A. Gómez
2
Definición de una interfaz Pila: Se abstrae de la ED con la que se implementará Se documenta el significado de cada método en lenguaje natural Se usa un parámetro formal de tipo representando el tipo de los elementos de la pila Se definen excepciones para las condiciones de error 5
Estructuras de datos ‐ Dr. Sergio A. Gómez
6
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Estructuras de Datos. Notas de Clase”. Sergio A. Gómez. Universidad Nacional del Sur. (c) 203-2016.
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
1
3/29/2016 Estructuras de Datos
Dr. Sergio A. Gómez
OJO: En la PC usar comentarios Javadoc.
public interface Stack { // Inserta item en el tope de la pila. public void push( E item );
Implementaciones de pilas 1) Con un arreglo 2) Con una estructura enlazada 3) En términos de una lista (lo dejamos pendiente hasta dar el TDA Lista)
// Retorna true si la pila está vacía y falso en caso contrario. public boolean isEmpty(); // Elimina el elemento del tope de la pila y lo retorna. // Produce un error si la pila está vacía. public E pop() throws EmptyStackException; // Retorna el elemento del tope de la pila y lo retorna. // Produce un error si la pila está vacía. public E top() throws EmptyStackException; // Retorna la cantidad de elementos de la pila. public int size(); } Estructuras de datos ‐ Dr. Sergio A. Gómez
7
8
Pila: Implementación con arreglo
Pila: Implementación con arreglo
// Archivo: PilaArreglo.java public class PilaArreglo implements Stack { protected int tamaño; protected E [] datos; … }
// Archivo: PilaArreglo.java public class PilaArreglo implements Stack { … }
2 8 7 5 3 s
// Archivo: AplicacionUsaPilaArreglo.java public class AplicacionUsaPilaArreglo { public static void main( String [] args ) { Stack s = new PilaArreglo(); s.push( 3 ); s.push( 5); s.push( 7 ); s.push( 8 ); s.push( 2 ); } }
2 8 7 5
9
3 s
5
7
8
2
0
1
2
3
4
5
6
7
8
…
MAX‐1
5
tamaño
s
10
Pila: Implementación con arreglo
// Archivo: PilaArreglo.java public class PilaArreglo implements Stack { protected int tamaño; protected E [] datos; … }
// Archivo: PilaArreglo.java public class PilaArreglo implements Stack { protected int tamaño; protected E [] datos; … }
datos
datos 0
tamaño
3
3
Pila: Implementación con arreglo
2 8 7 5
datos
1 0
2
3
4
5
6
7
8
…
MAX‐1
0
Constructor: Tamaño = 0 datos = (E []) new Object[MAX]
tamaño
NOTA: MAX puede ser una constante o puede ser recibido en el constructor. 11
1 0
2
3
4
5
6
7
8
…
MAX‐1
Pila Vacía: isEmpty() Retornar tamaño== 0
s
12
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Estructuras de Datos. Notas de Clase”. Sergio A. Gómez. Universidad Nacional del Sur. (c) 203-2016.
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
2
3/29/2016 Estructuras de Datos
Dr. Sergio A. Gómez
Pila: Implementación con arreglo
Pila: Implementación con arreglo
// Archivo: PilaArreglo.java public class PilaArreglo implements Stack { protected int tamaño; protected E [] datos; … } datos
2 8 7 5
tamaño
3
5
7
8
2
0
1
2
3
4
5
3
5
6
7
8
// Archivo: PilaArreglo.java public class PilaArreglo implements Stack { protected int tamaño; protected E [] datos; … }
…
Apilar: Push(E item): Si tamaño == MAX entonces error (“Pila llena”) Sino datos[tamaño] = item tamaño = tamaño + 1
// Archivo: AplicacionUsaPilaEnlazada.java public class AplicacionUsaPilaEnlazada { public static void main( String [] args ) { Stack s = new PilaEnlazada(); s.push( 3 ); s.push( 5); s.push( 7 ); s.push( 8 ); s.push( 2 ); } }
s
21
8
71
51
2 8 7 5
Public class PilaEnlazada implements Stack { protected Nodo head; protected int tamaño;
8
2
2
3
4
5
6
7
8
…
MAX‐1
Tope: E pop() Si tamaño == 0 entonces error (“Pila vacía”) Sino aux = datos[tamaño‐1] datos[tamaño‐1] = null tamaño = tamaño – 1 retornar aux
5
21
2 8 7 5 3
8
71
51
Cabeza (head) public class Nodo { private E elemento; private Nodo siguiente;
14
15
31
Cola (tail)
public Nodo() { this(null, null); } public Nodo( E item ) {this(item,null); } public Nodo( E item, Nodo sig ) { elemento=item; siguiente=sig; } public E getElemento() { return elemento;} public void setElemento( E elemento ) { this.elemento=elemento;} public Nodo getSiguiente() { return siguiente;} public void setSiguiente( Nodo siguiente ) { this.siguiente = siguiente; } }
s
Pila: Implementación con nodos enlazados Cabeza (head)
7
1
Pila: Implementación con nodos enlazados
// Archivo: PilaEnlazada.java public class PilaEnlazada implements Stack { … }
3
5
0
s
13
Pila: Implementación con nodos enlazados
2 8 7 5
tamaño
3
3
NOTA: En el caso de la situación de error se puede: (1) Disparar una excepción indicando “pila llena”, o (2) Incrementar el tamaño del arreglo
s
datos
2 8 7 5
MAX‐1
Public class PilaEnlazada implements Stack { protected Nodo head; protected int tamaño; …. }
16
Pila: Implementación con nodos enlazados
31
21
Cola (tail)
8
71
51
Cabeza (head)
Constructor:
2 8 7 5
Head = null Tamaño = 0
…. }
3
Public class PilaEnlazada implements Stack { protected Nodo head; protected int tamaño; ….
31
Cola (tail)
isEmpty(): Return head == null O
}
Retornar tamaño == 0
3
s
s 17
18
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Estructuras de Datos. Notas de Clase”. Sergio A. Gómez. Universidad Nacional del Sur. (c) 203-2016.
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
3
3/29/2016 Estructuras de Datos
Dr. Sergio A. Gómez
Pila: Implementación con nodos enlazados 21
8
71
51
Cabeza (head)
31
21
Cola (tail)
Public class PilaEnlazada implements Stack { protected Nodo head; protected int tamaño;
2 8 7 5
Pila: Implementación con nodos enlazados
…. }
8
71
51
Cabeza (head)
push(E item):
2 8 7 5
Nodo aux = new Nodo( ) aux.setElemento( item ) aux.setSiguiente( head ) head = aux tamaño = tamaño + 1
3
public class PilaEnlazada implements Stack { protected Nodo head; protected int tamaño;
E pop(): Si isEmpty() entonces error( “Pila vacia” )
Sino aux = head.getElemento() head = head.getSiguiente() tamaño = tamaño – 1 retornar aux
…. }
3
s
31
Cola (tail)
s 19
Pila: Implementación con nodos enlazados 21
8
71
Cabeza (head)
2 8 7 5
51
20
Especificación formal de una pila
31
Cola (tail)
Pregunta: ¿Por qué conviene insertar en la cabeza de la lista y no en la cola?
Operaciones: create : Stack push : Stack x E Stack pop : Stack Stack isEmpty : Stack boolean top : Stack E
// Crea una pila vacía // Apila un elemento en una pila // Desapila un elemento de la pila // Testea si la pila está vacía // Retorna el tope de la pila
Axiomas: (1) isEmpty( create ) = true (2) isEmpty( push(s,x) ) = false (3) pop( push(s,x) ) = s (4) top( push( s, x ) ) = x
Si la pila tiene n elementos: Al insertar en la cabeza tenemos operaciones con O(1) Al insertar en la cola tenemos operaciones con O(n)
3 s 21
TDA Cola Cola: Colección de objetos actualizada siguiendo una política FIFO (first‐in first‐out, el primero en entrar es el primero en salir) Operaciones: • enqueue(e): Pone el elemento e al final de la cola • dequeue(): Elimina el elemento del frente de la cola y lo retorna. Si la cola está vacía se produce un error. • front(): Retorna el elemento del frente de la cola. Si la cola está vacía se produce un error. • isEmpty(): Retorna verdadero si la cola no tiene elementos y falso en caso contrario • size(): Retorna la cantidad de elementos de la cola. 23
Estructuras de Datos ‐ Dr. Sergio A. Gómez
22
Cola: Aplicaciones • Colas de pedidos para atención por orden de llegada – Sistema de reservas en una aerolínea – Centros de reservas – Líneas de producción – Colas para atención de procesos – Colas de espera
Estructuras de datos ‐ Dr. Sergio A. Gómez
24
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Estructuras de Datos. Notas de Clase”. Sergio A. Gómez. Universidad Nacional del Sur. (c) 203-2016.
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
4
3/29/2016 Estructuras de Datos
Dr. Sergio A. Gómez
Cola: Aplicaciones
Cola: Aplicaciones (avanzadas)
• Colas de pedidos para atención por orden de llegada
• Buffer de entrada salida • Socket: Estructura de datos para comunicar dos programas: un programa inserta (encola) datos en el socket y otro programa los consume (desencolando). Los datos son consumidos en el orden en que se produjeron.
– Sistema de reservas en una aerolínea Cola de pasajero – Centros de reservas Cola de Asistente a espectáculo – Líneas de producción Cola de productos – Colas para atención de procesos Cola de procesos – Colas de espera Cola de personas Estructuras de datos ‐ Dr. Sergio A. Gómez
25
26
public interface Queue { // Inserta el elemento e al final de la cola public void enqueue(E e);
Implementación de Cola Definición de una interfaz Cola: Se abstrae de la ED con la que se implementará Se documenta el significado de cada método en lenguaje natural Se usa un parámetro formal de tipo representando el tipo de los elementos de la pila Se definen excepciones para las condiciones de error Estructuras de datos ‐ Dr. Sergio A. Gómez
Estructuras de datos ‐ Dr. Sergio A. Gómez
// Elimina el elemento del frente de la cola y lo retorna. // Si la cola está vacía se produce un error. public E dequeue() throws EmptyQueueException; // Retorna el elemento del frente de la cola. // Si la cola está vacía se produce un error. public E front() throws EmptyQueueException; // Retorna verdadero si la cola no tiene elementos // y falso en caso contrario public boolean isEmpty(); // Retorna la cantidad de elementos de la cola. public int size(); 27
}
28
Implementación de cola con un arreglo circular
Implementaciones de colas 1) Con un arreglo circular 2) Con una estructura enlazada 3) En términos de una lista (lo dejamos pendiente hasta dar el TDA Lista)
q
f
3
5
7
8
2
0
1
2
3
4
0
r
5
6
7
8
…
N‐1
5
• q es un arreglo que mantiene los elementos de la cola • El tamaño de q es N • f es la posición en q del próximo elemento a eliminar en un dequeue • r es la posición en la cual se va a insertar el siguiente elemento con un enqueue. • Implementaremos operaciones en O(1) 29
Estructuras de datos ‐ Dr. Sergio A. Gómez
30
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Estructuras de Datos. Notas de Clase”. Sergio A. Gómez. Universidad Nacional del Sur. (c) 203-2016.
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
5
3/29/2016 Estructuras de Datos
Dr. Sergio A. Gómez
Implementación de cola con un arreglo circular q
3
5
7
8
2
0
1
2
3
4
0
f
r
Implementación de cola con un arreglo circular q
5
6
7
8
…
N‐1
5
7
8
2
1
2
3
4
0
r
Constructor: f = 0 r = 0
Estructuras de datos ‐ Dr. Sergio A. Gómez
3
5
7
8
2
0
1
2
3
4
0
r
Constructor: f = 0 r = 0
6
7
8
…
N‐1 f
front(): Si isEmpty() entonces error( “cola vacía”) Sino retornar q[f]
Estructuras de datos ‐ Dr. Sergio A. Gómez
3
5
7
8
2
0
1
2
3
4
0
r
Constructor: f 0 r 0
33
0 f
5
7
1
2
8
Size(): Retornar (N‐f+r) mod N
N‐1
32
5
6
7
8
…
N‐1
5
34
Cola: Implementación con nodos enlazados 5
71
81
21
2
3
0
…
isEmpty(): Retornar f == r
31
3
8
front(): Si isEmpty() entonces error( “cola vacía”) Sino dequeue(): retornar q[f] Si isEmpty() entonces error( “cola vacía”) Sino temp = q[f]; q[f] = null; Estructuras de datos ‐ Dr. Sergio A. Gómez f = (f+1) mod N; retornar temp
Implementación de cola con un arreglo circular q
7
Implementación de cola con un arreglo circular
5
isEmpty(): Retornar f == r
6
Estructuras de datos ‐ Dr. Sergio A. Gómez
q 5
5 5
isEmpty(): Retornar f == r
31
Implementación de cola con un arreglo circular
f
5
0 f
Constructor: f = 0 r = 0
q
3
4 r
5
6
7
8
…
Cabeza (head)
N‐1
5
public class ColaEnlazada implements Queue { protected Nodo head, tail; protected int tamaño;
Nota: La cola puede almacenar N‐1 elementos a lo sumo
enqueue(e): Si size() == N‐1 entonces error( “cola llena”) Sino q[r] = e r = (r+1) mod NEstructuras de datos ‐ Dr. Sergio A. Gómez
…. }
Implementaremos operaciones en orden 1. 35
Cola (tail)
public void enqueue( E elem ) { Nodo nodo = new Nodo(); nodo.setElemento( elem ); nodo.setSiguiente( null ); if (tamaño == 0 ) head = nodo; else tail.setSiguiente( nodo ); tail = nodo; tamaño++; }
36
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Estructuras de Datos. Notas de Clase”. Sergio A. Gómez. Universidad Nacional del Sur. (c) 203-2016.
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
6
3/29/2016 Estructuras de Datos
Dr. Sergio A. Gómez
Cola: Implementación con nodos enlazados 31
5
71
81
Cabeza (head)
….
21
Cola (tail)
public class ColaEnlazada implements Queue { protected Nodo head, tail; protected int tamaño;
}
Problema: Insertar los elementos 1, 2, 3, 4 en una cola y luego mostrar todos los elementos de la cola.
public E dequeue() throws EmptyQueueException { if( tamaño == 0 ) throw new EmptyQueueException( “cola
public class App { public static void main( String [] args ) { try { Queue q = new ColaEnlazada(); for( int i=1; i