El documento describe los conceptos básicos de una pila, incluyendo su definición como una estructura de datos especial de lista abierta donde sólo se pueden insertar y eliminar elementos en un extremo, sus operaciones principales de apilar y desapilar, y tres notaciones matemáticas (prefija, infija y posfija). También explica los pasos para convertir una expresión de notación infija a posfija usando pilas.
0 calificaciones0% encontró este documento útil (0 votos)
89 vistas11 páginas
El documento describe los conceptos básicos de una pila, incluyendo su definición como una estructura de datos especial de lista abierta donde sólo se pueden insertar y eliminar elementos en un extremo, sus operaciones principales de apilar y desapilar, y tres notaciones matemáticas (prefija, infija y posfija). También explica los pasos para convertir una expresión de notación infija a posfija usando pilas.
El documento describe los conceptos básicos de una pila, incluyendo su definición como una estructura de datos especial de lista abierta donde sólo se pueden insertar y eliminar elementos en un extremo, sus operaciones principales de apilar y desapilar, y tres notaciones matemáticas (prefija, infija y posfija). También explica los pasos para convertir una expresión de notación infija a posfija usando pilas.
El documento describe los conceptos básicos de una pila, incluyendo su definición como una estructura de datos especial de lista abierta donde sólo se pueden insertar y eliminar elementos en un extremo, sus operaciones principales de apilar y desapilar, y tres notaciones matemáticas (prefija, infija y posfija). También explica los pasos para convertir una expresión de notación infija a posfija usando pilas.
Ministerio del Poder Popular para la Educación Universitaria
Instituto Universitario Politécnico “Santiago Mariño”
Barcelona – Edo. Anzoátegui
Pilas
Profesor: Bachiller:
Ing. José A. Castillo Anderson D. Chauran D.
Estructura de Datos C.I: V-25.852.816
Barcelona, 11 de Noviembre de 2019
1 Índice
Pag.
Introducción......………………………………………………………………… 3
Pila (definición)………...……………………………………………………… 4
Operaciones sobre pilas………………………………………………………. 5
Notaciones (Prefija, infija y posfija)………………………………………….. 6
Notación Prefija………………………………………………………… 6
Notación Infija…………………………………………………………... 7
Notación Postfija………………………………………………………. 7
Pasos para la conversión Infija a Postfija usando pilas…………………… 8
Conclusión…………………………………………………………………….... 10
Bibliografía……………………………………………………………………… 11
2 Introducción
En este trabajo vamos a hablar sobre unos conceptos básicos que nos da a entender lo que se refiere a una pila, refiriéndonos a una estructura de datos “una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista.”. Con este pequeño concepto nos damos cuenta que una pila es básicamente una cantidad x de objetos montados uno encima de otro y que solamente vamos a poder ver de esta pila el objeto que se encuentre en el tope de dicha pila, por ejemplo una pila de ropa o una pila de vajillas. En lo que queda de trabajo vamos a ver conceptos amplios sobre este concepto, sus operaciones y tres notaciones o expresiones de lo que se refiere al concepto de “pila”. Espero este trabajo sea entendible a los lectores.
3 Pilas
Una pila (stack en inglés) 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.
Un concepto básico de esto es que una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista.
4 Operaciones sobre pilas
A modo de resumen, la pila es un contenedor de nodos y tiene dos operaciones
básicas: push (o apilar) y pop (o desapilar). «Push» añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos ya presentes en la pila. «Pop» devuelve y elimina el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos dispuesta en una cafetería en un contenedor con un muelle que mantiene la pila a nivel. En esa serie, solo el primer plato es visible y accesible para el usuario, todos las demás permanecen ocultos. Como se añaden nuevos platos, cada nuevo plato se convierte en la parte superior de la pila, permaneciendo escondidos debajo los demás. A medida que el plato superior se extrae de la pila, la inmediatamente inferior pasa a ocupar la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: únicamente se accede al plato que se encuentra en la parte superior (el último en depositarse), y el resto de platos de la pila permanecen ocultos. Para extraer un plato distinto al superior habrá que extraer antes los que se encuentran sobre él.
Habitualmente, junto a las dos operaciones básicas de apilar y desapilar (push,
pop), las pilas puede implementar otra serie de funciones:
Crear (constructor): crea la pila vacía.
Tamaño (size): regresa el número de elementos de la pila. Apilar (push): añade un elemento a la pila. Desapilar (pop): lee y retira el elemento superior de la pila. Leer último (top o peek): lee el elemento superior de la pila sin retirarlo. Vacía (empty): devuelve cierto si la pila está sin elementos o falso en caso de que contenga alguno.
Una pila puede implementarse fácilmente ya sea mediante una matriz o una lista enlazada. Lo que identifica a una estructura de datos como una pila en cualquier caso no es su estructura sino su interfaz: al usuario solo se le permite colocar y
5 extraer datos en el modo que se espera de una pila y algunas otras operaciones auxiliares.
Otro tipo de estructura de datos es la cola (FIFO, del inglés First In First Out), «primero en entrar, primero en salir».
Notaciones (Prefija, infija y posfija).
PreFija: La expresión o notación prefija nos indica que el operador va antes
de los operando, sus características principales son: El orden de esta notación es:
- Los operando 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 él es una operación. - Se evalúa de izquierda a derecha hasta que encontremos el 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. El orden de esta notación es: a) Operador. b) Primer operando. c) Segundo operando.
6 InFija: La expresión o notación infija es la forma más 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: 3 * 4 = 12 3 * 4 + 2 = 14 3 * (4 + 2) = 18 El orden de esta notación es: a) Primer operando. b) Operador. c) Segundo operando.
PosFija: Como su nombre lo indica se refiere a que el operador ocupa la
posición después de los operando, 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. - La operación posfija no es exactamente lo inverso de la operación prefija equivalente. El orden de esta notación es: a) Primer operando. b) Segundo operando. c) Operador. La notación postfija es un método algebraico alternativo de introducción de datos que permite reducir el acceso a la memoria del ordenador, sobretodo en cálculos masivos y complejos ya que los cálculos se realizan secuencialmente según se van introduciendo los operadores (en vez de tener que esperar a escribir la expresión al completo).
7 Básicamente consiste en que en una expresión de ese tipo primero están los operandos y después viene el operador. Ejm: “3 + 5” pasado a notación postfija seria: “3 5 +”
Un ejemplo de estas tres tipos de expresiones o notaciones (prefija, infija y
postfija) sería el siguiente:
Si deseamos representar las expresiones ( 2 + ( 3 * 4 ) ) = x y ( ( 2 + 3 ) * 4 ) = x,
en las tres notaciones mencionadas el resultado sería:
1) Añadir “(“ al principio y “)” al final de EXPR. Seguidamente agregar uno a
uno todos los parámetros de EXPR a la Pila E. (, 2, *, (, 23, +, 6, ), -, 1, ) 2) Examinar E de izquierda a derecha y repetir los pasos 3 a 6 para cada elemento de E hasta que quede vacía. 3) Si se encuentra “(“, meterlo en P. 4) Si se encuentra un OPERADOR (+, -, *, /) entonces:
8 a) Repetidamente sacar de P y añadir a S cada operador (de la cima de P) que tenga la misma precedencia o mayor que el operador de E. b) Añadir Operador a P [Fin de condicional] 5) Si se encuentra un “)”, entonces: a) Repetidamente sacar de P y añadir a S cada operador (de la cima de P), hasta que encuentre un “(“. b) Eliminar el “(“ de P (No añadir a S) [Fin de condicional] 6) Si se encuentra un operando (2, 23, 6…), añadirlo a S. [Fin del Bucle] 7) Salir
Nota: Los operandos siguen la siguiente jerarquía (el de arriba es el que tiene mayor jerarquía hasta abajo el que tiene la menor):
1. ˄ 2. * / 3. + - 4. ) 5. (
9 Conclusión Vemos que este trabajo diferentes expresiones que nos ayudan a entender sobre un concepto que normalmente vemos en nuestro diario vivir pero que no hemos profundizado sobre ello, todo lo que hemos aprendido, el concepto general y científico sobre una pila, las operaciones que se pueden ejecutar en ellas en la estructura de datos, así como también las expresiones aritméticas prefija, infijas y postfija, esos conocimientos nos mantienen nutridos e interesados sobre lo que podemos hacer, porque cuando se conoce el concepto sobre algo no vamos a seguir viendo eso de la misma forma, dándole una especie de sentido a lo que estamos haciendo y el por qué lo estamos haciendo, una pila es un conjunto de objetos ordenados de tal forma que solamente se puede ver el extremo superior y si se quiere ver lo que está por debajo de él primero hay que sacar el que esta arriba, por eso una de las expresiones que leímos en este trabajo “ultimo en entrar, primero en salir”, esa es la expresión que englobaría lo que se conoce como una pila, espero que este trabajo haya sido llenando los conocimientos de los lectores, bendiciones.
