Clase sobre Pilas

8/18/2019 Clase sobre Pilas

1/11

UNIVERSIDAD AUTÓNOMA DE ASUNCIÓNFacultad de Ciencias y Tecnologías

Depata!ento de In"o!#tica

Material elaborado por la Prof. Paola PeñaEstructura de Datos y Archivos – Clase Nº 4

1

CLASE 4

Pilas (Stack)

Introducción

E esta uidad se presetara estructuras de datos lieales co restriccioes e cuato a laposici! e la cual se puede llevar a cabo las operacioes de iserci! y eli"iaci! deco"poetes.

Pilas

#a pila represeta ua estructura lieal de datos e la $ue se puede a%re%ar o $uitarele"etos &ica"ete por uo de los e'tre"os. E cosecuecia( los ele"etos de ua pilase eli"ia e orde iverso al $ue se isertaro( es decir el &lti"o ele"eto $ue se "etee la pila es el pri"ero $ue se saca. )a"bi* coocida co"o estructura LIFO +,ast -put(irst /utput0 &lti"o e etrar( pri"ero e salir.

,as pilas al i%ual $ue los arre%los so cosideradas estructuras lieales( ya $ue susco"poetes ocupa lu%ares sucesivos e la estructura y cada uo de ellos tiee u &icosucesor y u &ico atecesor( co e'cepci! del &lti"o y del pri"ero.

,a pila se defie for"al"ete co"o ua colecci! de datos a los cuales se puede acceder"ediate u e'tre"o( $ue se cooce %eeral"ete co"o tope.

Al%uos de los ee"plos "2s co"ues sobre el fucioa"ieto de pilas so3 pila de libros(pila de platos( pila de latas e super"ercado( etc.

Representación de la pilas,as pilas o so estructuras fuda"etales de datos( es decir o est2 defiida co"o talese los le%uaes de pro%ra"aci!. Para su pro%ra"aci! se re$uiere el uso de otrasestructuras de datos( co"o3

• Arre%los• ,istas


2/11




Variables de las pilas

E esta uidad trabaare"os co arre%los. E cosecuecia( es i"portate defiir el ta"año"2'i"o de la pila +A!0( as5 co"o la variable au'iliar "OPE# esta variable se utili6a paraidicar el &lti"o ele"eto $ue se isert! e la pila.

E$e%plo &' 7epresetaci! %r2fica de pila aloada e u arre%lo

1 8A 9

C

A! 4

"OPE *+ C

1 8C 9 A

A! 4"OPE *+ A

18

A! 4 "OPE *+ C

18

A! 4

"OPE *+ A

A9C

C9A


3/11




8

Operaciones con pilas

,as operacioes b2sicas co pilas( per"ite la iserci! y eli"iaci! de ele"etos e uapila.

• -sertar u ele"eto :;Push• Eli"iar u ele"eto :; Pop

)a"bi* e'iste las operacioes au'5liales( $ue per"ite verificar el estado de ua pila

ates de su iserci! +Llena0( o eli"iaci! +Vac,a0. El pri"er arroa u error deo"iado-esborda%iento( debido a $ue la "is"a est2 repleta e su capacidad y o se puedeisertar uevos ele"etos. El se%udo estado arroa el error deo"iadoSubdesborda%iento( debido a $ue la "is"a est2 vac5a y o hay ele"etos para eli"iar.

• Pilaubdesborda"ieto• Pila


4/11




4

Pilaio

)ope ?)ope B 1

pPila)ope ? Dato

i si

i -serta

Eli"ia +Pila( )ope( Nu"el( Dato0

>i Pilaubdesborda"ieto o Pila =ac5a

>io

Dato ? Pila)ope

)ope ? )ope : 1

i si


5/11




i Eli"ia

Aplicaciones de pilas

,as pilas so ua estructura de datos "uy utili6adas e la soluci! de diversos tipos deproble"as( e el 2rea de co"putaci!. Aali6are"os e este apartado al%uos de los casos"2s represetativos de la aplicaci! de las "is"as.

• ,la"adas a subpro%ra"as

•

)rata"ieto de e'presioes arit"*ticas• 7ecursividad• /rdeaci!

Lla%adas a subpro/ra%as' cuado se tiee u pro%ra"a $ue lla"a a u subpro%ra"a(ta"bi* coocido co"o "odulo o fuci!( itera"ete se usa pilas para %uardar elestado de las variables del pro%ra"a( as5 co"o las istruccioes pedietes de eecuci! eel "o"eto $ue se hace la lla"ada. Cuado ter"ia la eecuci! del subpro%ra"a( losvalores al"aceados e la pila se recupera para cotiuar co la eecuci! del pro%ra"a

e el puto e el cual fue iterru"pido. Ade"2s de las variables se recupera la direcci! delpro%ra"a e la $ue se hi6o la lla"ada( por$ue a esa posici! de re%resa el cotrol delproceso.

"rata%iento de e0presiones arit%1ticas' otro proble"a iteresate e co"putaci!cosiste e covertir e'presioes arit"*ticas e otaci! ifia a su e$uivalete e otaci!prefia o posfia.

E$e%plo 4' E'presi! arit"*tica otaci! ifia a posfia

A 2 3*+ otación In5i$a :; /perador +B0 etre los operados

2 A3 *+ otación Pre5i$a:; /perador +B0 precede a los operados

A3 2*+ otación Pos5i$a:; /perado +B0 se ecuetra despu*s de los operados

Recursión3 sirve para verificar e $u* puto se ecuetra u pro%ra"a cuado tieeprocedi"ietos $ue se lla"a a s5 "is"os.

>e va car%ado e la pila las istruccioes $ue lla"a al procedi"ieto( y cuado elprocedi"ieto retora se va descar%ado e ua secuecia ,-/ hasta $ue vuelva a lapri"era lla"ada y la pila $uede vac5a. Cada ivocaci! al procedi"ieto ecesita serre%resada.


6/11




F

Ordenación3 cosiste e u "*todo para ca"biar la disposici! de los ele"etos de uaestructura( se%& deter"iadas caracter5sticas( dicho "*todo se ver2 co "ayor detalle eua uidad posterior.

Otras aplicaciones

Correspondencia de par1ntesis3 sirve para verificar si cada par*tesis tiee su par( y $ueest* aidados correcta"ete.

Cuado se ecuetra u par*tesis i6$uierdo( se lo "ete e la pila( y cuado se ecuetra

u par*tesis derecho( se saca de la pila *ste y al $ue cierra +par correspodiete0.

>i al ter"iar la cadea( la pila o est2 vac5a( si%ifica $ue hay u par*tesis $ue o cierra( ysi al ecotrar u par*tesis derecho la pila est2 vac5a( si%ifica $ue *ste o cierra upar*tesis i6$uierdo.

El &"ero de ele"etos de la pila( idica la profudidad de aida"ieto.

E$e%plo63 Pila para a2lisis de correspodecia de par*tesis

-f ++a?b0 ad ++a;c0 or +dGf000 theH.

Paso 1 8 4 F I J K 1@Pila + ++ ++?0 ++ +++ ++?0 +++ ++?0 ++?0 +?0


7/11




I

La clase Pila

,a clase pila tiee atributos y "*todos. ,os atributos so la colecci! de ele"etos y el

)/PE. ,os "*todos( por otra parte( so todas a$uellas operacioes aali6adas e la secci!

aterior( Pila


8/11




J

E$e%plo ioDevolver also

fi sifi fucio


9/11




K

fucio)ope


10/11




1@

public iterface -Pila voidapilar+/bect '0Qvoiddesapilar+0 throRs E'ceptioQ/bect ci"a+0 throRs E'ceptioQbooleaes=acia+0Qvoid vaciar+0Q

S

i"portava.util.TQ

public class Pila=ec i"ple"ets -Pila private =ector pQprivateitci"aDePilaQstatic fial it CAPAC-DADer2 las clases $ue i"ple"ete estas iterfaces

las $ue describa la l!%ica del co"porta"ieto de los "*todos.


11/11




Fuentes biblio/r?5ica o @eblio/ra5ia

Cair!( /svaldoVuardati( >ilvia +@@F0. Estructura de Datos. 8ra Edici!.McVraR:Will -tera"ericaa Editores. >.A. de C.=.C!di%o3 KI@:1@:K@J:

http3$ue%rade.or%aputesE-Al%teoria@I:@Jte"a

Clase sobre Pilas

Documents

Transcript of Clase sobre Pilas