• Author / Uploaded
• Cristian Jesus

Citation preview

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS FACULTAD DE INGENIERÍA DE SISTEMAS E INFORMÁTICA

CURSO: ESTRUCTURA DE DATOS CLASE 07 PILAS

CONTENIDO DEFINICIÓN DE PILAS CARACTERÍSTICAS OPERACIONES CON PILAS OPERACIONES CON PILAS

PILAS DEFINICIÓN DE PILAS Una PILA es una lista de elementos en el cual un elemento sólo se puede adicionar (insertar) o eliminar por un extremo llamado CIMA o top de la pila Esto significa que los elementos se sacan o eliminan en el orden inverso al que se insertaron en la pila. CIMA O TOP de la pila INSERCION

BASE de la Pila

ELIMINACION

TERMINOLOGIA: Se utiliza una terminología especial para las dos operaciones básicas con pilas: -

empilar, meter, poner push son terminos utilizados para insertar un elemento en la pila desempilar, sacar, quitar, pop, son terminos utilizados para eliminar un elemento en la pila

Estos términos son exclusivos del manejo de pilas Una estructura de pila es llamado de Estructura LIFO (last input,first output) o último en ingresar, primero en salir. Ejemplos de pilas: -pila de platos - pila de libros - pila de CDs etc. Ejemplo: Supongamos que se PONEN en la pila vacia 6 elementos en el orden siguiente: AAA, BBB, CCC, DDD, EEE, FFF

FFF EEE DDD CCC BBB AAA

Esta pila se puede mostrar de 3 formas:

Primera forma: CIMA

FFF EEE DDD CCC BBB AAA

Segunda forma:

CIMA 1

AAA

2

BBB

3

CCC

4

DDD

5

EEE

6

FFF

7 8 9 . . . . n-1 N

Tercera forma: CIMA

AAA BBB CCC DDD EEE FFF 1

2

3

4

5

6

7

8

9

.…

N-1

ACCIONES PRIMITIVAS EN PILAS VACIO(P): Devuelve VERDAD si la Cima C de la Pila P esta vacío EMPILAR (C, V) : Empila V en la cima C de la Pila DESEMPILAR(C,V) : Elimina el elemento V de la cima C de la pila. La pila es una estructura de datos abstracta, es decir que se puede implementar una pila utilizando otras estrcturas. MÉTODOS PARA IMPLEMENTAR PILAS 1. Implementación mediante arreglos 2. Implementación mediante listas enlazadas (Punteros) REPRESENTACIÓN DE PILAS MEDIANTE ARREGLOS La representación mediante arreglos se realiza asociando a cada pila una variable CIMA que apunta al último valor ingresado. DESVENTAJAS DE UTILIZAR ARREGLOS PARA IMPLEMENTAR PILAS La representación mediante arreglos tiene el inconveniente de declarar el tamaño del arrglo.

CIMA

Pila 3 Pila 2 Pila 1

N

Se define el arreglo PILA [ N ]

1

2

3

. . .

N

CIMA

Ejemplo: Sea la reprsentación de una Pila PILA mediante arreglos donde PILA tiene 3 elementos : XXX, YYY, ZZZ y como MAXPILA = 8 Se puede observar que hay espacio para 5 elementos más. PILA

XXX 1

YYY 2

ZZZ 3

4

5

6

7

8

3 CIMA

MAXPILA 8

MODELO 1 Los datos se ingresan de izquierda a derecha CIMA contiene la Dirección del último elemento ingresado Considereamos por convención que cuando CIMA = 0, la PILA P esta vacía La Acción Vacío

VACIO(CIMA) Inicio Si (CIMA = 0)) Retornar Verdad Sino Retornar Falso Finsi FIn

La Acción Empilar

Accion Empilar (P, CIMA, N, V) Inicio Si (CIMA = N) Escribir “ Pila llena” Sino CIMA = CIMA +1 P(CIMA) = V FinSi Fin

La Acción Desempilar

Accion Desempilar (P, CIMA, N, V) Inicio Si ( VACIO(CIMA)) Escribir “ Pila vacía” Sino V= P(CIMA) CIMA = CIMA -1 FinSi Fin

MODELO 2 Los datos se ingresan de derecha a izquierda CIMA contiene la Dirección del último elemento ingresado Considereamos por convención que cuando CIMA = N + 1, la PILA P esta vacía La Acción Vacío

VACIO(CIMA) Inicio Si (CIMA = N + 1)) Retornar Verdad Sino Retornar Falso Finsi FIn

La Acción Empilar

Accion Empilar (P, CIMA, N, V) Inicio Si (CIMA = 1) Escribir “ No existe espacio” Sino CIMA = CIMA - 1 P(CIMA) = V FinSi Fin

La Acción Desempilar

Accion Desempilar (P, CIMA, N, V) Inicio Si ( VACIO(CIMA)) Escribir “ Pila lvacía” Sino V= P(CIMA) CIMA = CIMA +1 FinSi Fin

REPRESENTACIÓPN DE PILAS MEDIANTE LISTAS ENLAZADAS Sea una Lista Enlazada con cabecera CIMA CIMA

0

Cuando se adiciona o empila un elemento, este se adiciona por la CIMA Su Implementación es como sigue: La Acción Vacío

Acción VACIO(CIMA) Inicio Si (CIMA = NULL) Retornar Verdad Sino Retornar Falso Finsi FIn

La Acción Empilar

Accion Empilar (CIMA, N, V) Inicio N = nuevo_nodo N-valor = V Nsgte =CIMA CIMA = N Fin

La Acción Desempilar

Accion Desempilar (P, CIMA, V) Inicio Si ( VACIO(CIMA)) Escribir “ Pila lvacía” Sino V= CIMAvalor CIMA = CIMAsgte FinSi Fin

APLICACIONES EXPRESIONES ARITMÉTICAS: NOTACIÓN POLACA Sea Q una expresion de tipo aritmética que incluye constantes y operaciones Calcular el valor de Q utilizando la notación inversa polaca (postfija) Se asumirá 3 niveles de precedencia siguientes para las cinco operaciones aritméticas basicas: MAYOR SIGUENTE MAYOR MENOR

: Potencia ( î ) : Multiplicación ( * ) y División ( / ) : Suma (+ ) y resta ( -)

Se asume que Q no tiene operaciones unarias. Además que en una expresión sin parentesis las operaciones en el mismo nivel se realizan de izquierda a derecha. Ejemplo Evaluar la siguiente expresión aritmética 2 î3 + 5 * 2 î 2 – 12 / 6 Primero se evaluan las potencias 8 + 5 * 4 - 12 / 6 segundo se evaluan la multiplicación y división 8 + 20 - 2 finalmente se evaluan la suma y resta 26 se observa que se ha realizado un recorrido de 3 veces, cada vez correspondiente a un nivel de precedencia de las operaciones.

NOTACIÓN POLACA La mayoría de operaciones aritméticas se expresa en Notación Infija como en el siguiente ejemplo: Ejemplo A+B

C - D

(A + B) * C

E * F

G / H

y A + ( B *

C )

La Notación Polaca debe su nombre al polaco Jan Lukassiewicz, se refiere a la notación polaca en la que el símbolo operador se coloca delante de sus operandos. A esta Notación se le conoce como Notación Prefija Ejemplo: + A B

-CD

*EF

/GH

La notación polaca inversa se refiere a la notación análoga en la que el operador se coloca detrás de sus operandos. A este tipo de notación se le denomina Notación Postfija Ejemplo: A B + C D -

EF*

GH/

La computadora normalmente evalua una expresión aritmética escrita en Notación Infija mediante 2 pasos: 1. Convierte a la Notación Postfija y 2. luego evalua la expresion postfija

La Pila es una estructura muy utilizada para llevar a cabo las operaciones aritméticas. Las operaciones evaluadas como notación postfija Y mediante Pilas se pueden convertir en Notación Infija y viceversa. Ejemplo: Sea la siguiente expresión aritmética P escrita en Notación Postfija EJEMPLO: Sea la siguiente expresión aritmética P escrita en NotaciónPostfija: P: 5, 6,2, +. ¨*, 12, 4, /, Las comas tan solo son separadores La expresión infija equivalente: Q: 5 * (6 + 2) – 12/ 4 Los paréntesis son necesarios en la expresión infija, no en la expresión postfija Evaluando P:

1. se añade un paréntesis derecho como un flag o centinela al final de P para obtener:

P : 5, 6, 2, +, *, 12, 4, /, -, )

5

6

2

+

*

12

4

/

-

)

1

2

3

4

5

6

7

8

9

10

Los elementos de P han sido etiquetados o enumerados de izquierda a derecha para referenciarlos fácilmente, luego la Pila se puede expresar como sigue:

Simbolo examinado (1) 5 (2) 6 (3) 2 (4) + (5 ) * (6) 12 (7) 4 (8) / (9 ) (10) )

PILA 5 5, 6 5, 6, 2 5, 8 40 40, 12 40, 12, 4 40/ 3 37