07_estructuraslineales-pilas

Estructuras de datos lineales: pilas

Felipe Restrepo [email protected]

Departamento de Ingeniería de Sistemas e IndustrialFacultad de Ingeniería

Universidad Nacional de ColombiaSede Bogotá

mailto:[email protected]

• Listas

• Pilas

• Colas

Estructuras de Datos Estructuras lineales 2

Estructuras de datos lineales

1. ADT Pila

2. Aplicaciones

3. Implementaciones

PilasADT Aplicaciones Implementaciones


Pila (Stack)

• Lista de elementos con restricciones.

• Existe una relación de orden entre los elementos.

• El criterio de ordenación se establece en sentido inversoal orden de llegada.

• El último elemento que llegó al conjunto será el primeroen salir del mismo, y así sucesivamente.

• Sólo se tiene acceso a un elemento de la lista en cadamomento: el elemento añadido más recientemente.



Modelo de pila – Listas LIFO

Comportamiento LIFO (Last In First Out)



Operaciones en una pila

Dos operaciones principales:• push (apilar)• pop (desapilar)

Otras operaciones:• top/peek• isEmpty• makeEmpty• print



Errores en una pila

• Realizar pop o top en una pila vacía Error en el ADT

• Cuando se acaba el espacio de almacenamiento cuando estamos realizando un push Limitación en la implementación, no es

un error en el ADT



1. ADT Pila

2. Aplicaciones

3. Implementaciones



Aplicaciones

• Evaluación de recursividad

• Notación postfijo

• Balanceo de paréntesis, llaves, corchetes (análisis sintáctico)



Recursividad

• Usar pila para evaluar la recursividad• Se hace push con los llamados recursivos a un

procedimiento• Cuando llega al(los) caso(s) base, se empieza a hacer

pop y a evaluar

• Ejemplo: factorial de un número entero NN! = N * (N-1)!

1! = 1



Recursividad

Ejemplo: cálculo de 6!



Recursividad



6!


Recursividad



6! = 6 * 5!


Recursividad



5! = 5 * 4!

6! = 6 * 5!


Recursividad



4! = 4 * 3!

6! = 6 * 5!

5! = 5 * 4!


Recursividad



3! = 3 * 2!

6! = 6 * 5!

5! = 5 * 4!

4! = 4 * 3!


Recursividad



2! = 2 * 1!

6! = 6 * 5!

5! = 5 * 4!

4! = 4 * 3!

3! = 3 * 2!


Recursividad



1! = 1

6! = 6 * 5!

5! = 5 * 4!

4! = 4 * 3!

3! = 3 * 2!

2! = 2 * 1!


Recursividad



2! = 2 * 1 = 2

6! = 6 * 5!

5! = 5 * 4!

4! = 4 * 3!

3! = 3 * 2!


Recursividad



3! = 3 * 2 = 6

6! = 6 * 5!

5! = 5 * 4!

4! = 4 * 3!


Recursividad



4! = 4 * 6 = 24

6! = 6 * 5!

5! = 5 * 4!


Recursividad



5! = 5 * 24 = 120

6! = 6 * 5!


Recursividad



6! = 6 * 120 = 720


Notación postfija (postfix)

La notación postfija ubica el operador después de losoperandos (para evitar ambigüedades).

Ejemplo: 3 + 2 * 10

Si no está clara la precedencia de operadores puede ser ambiguo

3 2 + 10 * ((3 2 +) 10 *) ((3+2) * 10)

3 2 10 * + (3 (2 10 *) +) (3 + (2*10))




• Apilar (push) los símbolos (operandos) a medida que van apareciendo

• Cuando se lea un operador, desapilar (pop) dos operandos• Evaluar la operación y apilar (push)

Ejemplo:






Ejemplo:



Chequeo sintáctico

• Realizar balanceo de: • paréntesis ()• llaves {}• corchetes []

• Hacer un barrido del código fuente:• Si vemos un símbolo de apertura, lo apilamos (push)• Si vemos un símbolo de cierre, lo desapilamos (pop) y

comparamos con el esperado



Chequeo sintáctico



1. ADT Pila

2. Aplicaciones

3. Implementaciones



Implementaciones

• Java Collections

• Listas enlazadas

• Arreglos



Pila en Java Collections: Stack




• Esta clase es considerada como una clase “legado” de versionesanteriores (“legacy class”) y no se utiliza mucho en la actualidad.

• Hereda de la clase Vector y añade 5 métodos para operar comouna pila.

• Una estructura en Java más completa, consistente y eficiente pararealizar operaciones de pila (LIFO) se encuentra en la interfaceDeque (“deck”) y sus implementaciones. Se deben usar éstaspreferiblemente (en lugar de Stack). Ejemplo:

Deque<Integer> stack = new ArrayDeque<Integer>();



Pila mediante una lista enlazada

• ¿Tipo de lista enlazada? ¿simple, doble, circular, …? Lista enlazada simple

• ¿Se añade en la primera posición o en la última? Primera: Operaciones en tiempo constante

• Operaciones: push(x)

pop()

top()


add(0, x)

remove(0)

get(0)


Pila mediante un arreglo (alternativa más popular)

• ¿Se añade en la primera posición o en la última? Última. Operaciones en tiempo constante

• Operaciones: push(x)

pop()

top()


array[k++]=x

return array[--k]

return array[k-1]


Algoritmos básicos con pilas

• Escribir el contenido de una pila en pantalla (sin usar estructuras adicionales, ni modificar la pila)

public static <E> void print (MyStack<E> s)

{

E elem;

if (!s.isEmpty ()) {

elem = s.pop ();

System.out.println (elem);

MyStack.<E>print (s);

s.push (elem);

}

}



Algoritmos básicos con pilas

• Escribir el contenido de una pila en pantalla (sin usar estructuras adicionales, ni modificar la pila)

public static void main(String[] args) {

MyStack<Integer> pila = new MyStack<>();

pila.push(1);

pila.push(2);

pila.push(3);

pila.push(4);

pila.pop();

MyStack.<Integer>print(pila);

pila.pop();

MyStack.<Integer>print(pila);

}



Tarea

1. Implementar MyStack:• Usando MyArrayList• Usando MySingleLinkedList

2. Implementar los siguientes métodos:a) Contar el número de elementos de una pila (sin usar estructuras adicionales,

ni modificar la pila). Ayuda: similar al método print.

b) Obtener el duplicado de una pila. Se trata de obtener un duplicado de la pila que se pasa como argumento. En consecuencia, el algoritmo necesitará dos argumentos: la pila origen y la pila destino.

c) Comprobar si un elemento pertenece a una pila. Método que devuelve un valor booleano que determina si un elemento está en la pila o no.

Estructuras de Datos Listas 77


Estructuras de datos lineales: pilashttps://sites.google.com/a/unal.edu.co/estructuras-de-datos-2015-2/

Felipe Restrepo [email protected]

Departamento de Ingeniería de Sistemas e IndustrialFacultad de Ingeniería

Universidad Nacional de ColombiaSede Bogotá

https://sites.google.com/a/unal.edu.co/estructuras-de-datos-2015-1/

mailto:[email protected]

07_estructuraslineales-pilas

Documents