Pilas

EDA I

Definición de pila
EDA I

Pilas

Una pila es una colección lineal de
elementos en la que sólo se pueden añadir
y retirar elementos por uno de sus
extremos.
Se procesa con una estrategia LIFO (Last
In First Out)
tercero
1.
2.
3.
4.

push “primero”
push “segundo”
push “tercero”
pop

top

segundo
primero

Pilas

2

EDA I

tipo pila(T)
(Recuérdese:Metodología
de la programación)
usa bool
operaciones
pvacia: → pila(T)
apilar: T × pila(T) → pila(T)
cima: pila(T) → T
desapilar: pila(T) → pila(T)
es_vacia: pila(T) → bool
ecuaciones
(1) cima(pvacia) = error
(2) cima(apilar(x, p)) = x
(3) desapilar(pvacia) = error
(4) desapilar(apilar(x, p)) = p
(5) es_vacia(pvacia) = True
(6) es_vacia(apilar(x, p)) = False
Pilas

3

EDA IOperaciones en una pila
Operación
push
pop
peek
isEmpty
size

Pilas

Descripción
Añade un elemento a la parte superior de la pila
Elimina y devuelve un elemento de la parte superior
de la pila (supone que la pila no está vacía)
Da acceso al elemento situado en la parte superior de
la pila (supone que la pila no está vacía)
Determina si la pila está vacía
Determina el número de elementos dela pila

4

EDA I

EDA I

Pila genérica de elementos T

Interfaz del TAD Pila

Pila(T) // El identificador T es un parámetro genérico de clase
// crea una pila de elementos de clase T vacía
crear:
Pila(T)
// añade un elemento de clase T a la cima de una pila
push: Pila(T) × T
Pila(T)
// devuelve y retira el elemento de la cima de una pila
// (supone que la pila no está vacía)pop: Pila(T)
T ×Pila(T)
// devuelve el elemento de la cima de una pila
// (supone que la pila no está vacía)
peek: Pila(T)
T
// true si la pila está vacía y false en el caso contrario
isEmpty: Pila(T)
boolean
// devuelve el número de elementos que hay en la pila
size: Pila(T)
natural

public interface PilaTAD {
//Añade un elemento a la cima de la pila
public void push (T element);//Elimina y devuelve el elemento de la cima de la pila
//(supone que la pila no está vacía)
public T pop ();
//Devuelve, sin eliminarlo, el elemento de la cima de la pila
//(supone que la pila no está vacía)
public T peek ();
//Devuelve true si esta pila no contiene ningún elemento,
//y false en caso contrario
public boolean isEmpty ();
//Devuelve el número de elementos de la pilapublic int size();
}

Pilas

5

Pilas

6

EDA I

EDA I

Problemas a resolver

Invertir una palabra
algoritmo

Apilando según
vamos leyendo
Cada tarea que llega,
interrumpe la que se esté haciendo
y debe ser atendida.
Luego debe continuarse con la última
tarea que se estuviera haciendo.
Implementación con una pila de tareas
Pilas

7

Pilas

o
m
t
i
r
o
g
l
aomtirogla

construyendo según
vamos desapilando

(Véase Reverser)

8

EDA I

Problema:

EDA I

Uso de una pila para la solución

Determinar si los delimitadores {, }, [, ],
(, ), están bien emparejados en una
cadena de caracteres dada.

Para la entrada A{B(C[D]E)F}

Pilas

9

Pilas

10

EDA I

EDA I

Comprobador de delimitadores

Arrays en Java

Variable deestado String input

Los arrays en java son objetos

public void check() {
Crear pila theStack del tamaño de input
para cada ch de input hacer
{
si ch es '{‘, '[‘ o ‘(‘ entonces
theStack.push(ch); (*Apilar ch*)
si no
si ch es ‘}‘, ‘]‘ o ‘)‘ entonces
si ( !theStack.isEmpty() ) (*Pila no vacía*) entonces
{
chx = theStack.pop(); (*Desapilar*)
si (chx y ch no emparejan bien)
Comunicarel error y terminar
}
si no // la pila está vacía prematuramente
Comunicar el error y terminar
} // fin del para
// Todos los caracteres de input se han procesado
si ( !theStack.isEmpty() ) (*Pila no vacía*)
Comunicar el error
} // end check()

int[ ] miTabla;
miTabla = new int[100];

// define una referencia a un objeto array de enteros
// crea un objeto array de tamaño 100 y
//...