• Author / Uploaded
• Rick

Citation preview

República Bolivariana De Venezuela Ministerio Del Poder Popular Para La Educación Superior I. U. P. “Santiago Mariño” Estructura de Datos Ingenieria De Sistemas

Profesor:

Alumno:

José Castillo

José Figueira

Barcelona, Junio 2019

CI: 26.704.385

Indice Introduccion ............................................................................................................. 3 Pila .......................................................................................................................... 4 Operaciones ............................................................................................................ 4 Notaciones .............................................................................................................. 5 Conversion de Expresion Infija a Posfija ................................................................. 5 Conclusion............................................................................................................... 8 Anexos .................................................................................................................... 9

Introduccion El presente trabajo de investigacion se refiere al interesante tema de laspilas sobre estructura de datos, en las cuales se pueden definir de una manera muy simple como un tipo especial de lista lineal, donde la inserción y borrado de nuevos elementos se realizará sólo por un extremo que se denomina tope. Ya que estas operaciones de insertar y eliminar se realizan por un extremo, los elementos solo se eliminaran en orden inverso al que se inserta en la pila. El último elemento que está en la pila es el primero que se puede sacar; por ello, a estas estructuras se le conoce por el nombre de LIFO (last-in, first-out, último en entrar, primero en salir) Este tipo de estructuas es muy vista en bases de datos y tiene varios usos en sistemas que usamos en el dia a dia

Pila Una pila es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura. Representación gráfica de una pila Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado. En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo. Las pilas son utilizadas ampliamente para solucionar una amplia variedad de problemas. Se utiliza en compiladores, sistemas operativos y en programas de aplicación. Su implementación se puede hacer mediante Arrays Y Mediante listas enlazadas.

Un ejemplo de sus aplicaciones podría ser los siguientes:

Los Navegadores en Internet almacenan en una pila las direcciones de los sitios más recientemente visitados. Los editores de texto proporcionan normalmente un botón deshacer que cancela las operaciones de edición recientes y restablece el estado anterior del documento.

Operaciones Una pila cuenta con 2 operacines imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual. Crear: se crea la pila vacía. Apilar: se añade un elemento a la pila.(push) Desapilar: se elimina el elemento frontal de la pila.(pop) Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)

Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.

Notaciones Notación PreFija: nos indica que el operador va antes de los operandos sus características principales son:    

Los operandos conservan el mismo orden que la notación infija equivalente. No requiere de paréntesis para indicar el orden de precedencia de operadores ya que el es una operación. Se evalúa de izquierda a derecha hasta que encontrémosle primer operador seguido inmediatamente de un par de operandos. Se evalúa la expresión binaria y el resultado se cambia como un nuevo operando. Se repite este hasta que nos quede un solo resultado.

Notación prefija: El orden es operador, primer operando, segundo operando

Notacion InFija : La Expresión o Notación InFija es la forma mas común que utilizamos para escribir expresiones matemáticas, estas notaciones se refiere a que el operador esta entre los operandos. La notación infija puede estar completamente parentizada o puede basarse en un esquema de precedencia de operadores así como el uso de paréntesis para invalidar los arreglos al expresar el orden de evaluación de una expresión: Notación infija: La notación habitual. El orden es primer operando, operador, segundo operando.

Notacion PosFija : Como su nombre lo indica se refiere a que el operador ocupa la posición después de los operandos sus características principales son: -El orden de los operandos se conserva igual que la expresión infija equivalente no utiliza paréntesis ya que no es una operación ambigua. Notación postfija: El orden es primer operando, segundo operando, operador.

Conversion de Expresion Infija a Posfija El siguiente algoritmo traduce una expresión en notación infija a notación postfija: Entrada: Una lista que contiene los términos de la ecuación en notación infija (la notación habitual).

Salida: Una lista que contiene los términos de la ecuación en notación postfija. Datos locales: Una pila, que va a contener operadores y paréntesis izquierdos.

INICIO Crear pila y la lista de salida, inicialmente vacias. MIENTRAS lista de entrada no este vacia y no se ha encontrado ningun error HACER Extraer el primer termino de la lista (lo llamaremos E) SEGUN-SEA E CASO E es número : Insertar E al final de la lista de salida CASO E es la variable x : Insertar E al final de la lista de salida CASO E es un paréntesis izquierdo : Insertar E en la pila CASO E es un paréntesis derecho : MIENTRAS La pila no este vacía y su cima no sea un paréntesis izquierdo HACER Extraer elemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS SI Encontramos el parentesis izquierdo ENTONCES Extraerlo de la pila y destruirlo SINO Se ha detectado un ERROR 2 FIN-SI Destruir E CASO E es un operador :

MIENTRAS La pila no este vacía y su cima sea un operador de precedencia mayor o igual que la de E HACER Extraer elemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS Insertar E en la pila FIN-SEGUN-SEA FIN-MIENTRAS MIENTRAS Pila no esté vacía HACER Extraer elemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS Destruir pila FIN

Conclusion Podemos concluir que del presente trabajo de investigación sobre pilas como estructuras de datos, se menciona las pilas son una estructura de datos en la que el modo de acceder a sus elementos es de tipo LIFO (Last In First Out, último en entrar, primero en salir) y esto permite almacenar y también recuperar datos. Esta estructura tiene gran importancia en las tecnologías actuales y se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación de la propia estructura. Por otra parte para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.

Anexos Figura 1: Ilustracion Pila

Figura 2: Ejemplo de Pila

Figura 3: Operaciones de Pila

Bibliografias Referencias Electronicas Pila (Estructura de datos) https://www.ecured.cu/Pila_(Estructura_de_datos)

EcuRed.

Pila (informática). https://es.wikipedia.org/wiki/Pila_(inform%C3%A1tica)#Operaciones

(2019). (2019).