PILAS SIMPLES, Y SUS FUNCIONES

CC2M – ALGORITMOS Y ESTRUCTURAS DE DATOS I[pic 1]

Docente: MSc. Amparo Herrera García

Informe de pilas

Autores:

• Carlos Ernesto Guadamuz Espinoza
• Jorling Víctor Cerda Solís

  ---

Concepto de pila

En informática, una pila es un tipo de datos abstractos que sirve como una colección de elementos, con dos operaciones principales:

Push, que agrega un elemento a la colección.

• Pop, que elimina el elemento agregado más recientemente que aún no se eliminó.

El orden en que los elementos salen de una pila da lugar a su nombre alternativo, LIFO (último en entrar, primero en salir). Además, la operación Peek puede dar acceso a la parte superior sin modificar la pila. El nombre de "pila" para este tipo de estructura proviene de la analogía de un conjunto de elementos físicos apilados uno encima del otro, lo que facilita tomar un artículo fuera de la parte superior de la pila, mientras que llegar a un artículo más profundo en la pila puede requerir quitar varios otros artículos primero

Usos e implementaciones de las pilas

Pilas y recursividad

Las pilas son una forma importante de soportar llamadas a funciones anidadas o recursivas.

La idea general detrás de la recursividad se basa en dividir un problema en piezas más pequeñas hasta llegar a un caso base, fácil de resolver. Luego, para resolver el problema resolviendo estos pequeños problemas y fusionando las soluciones entre sí.

Ejemplo de una función recursiva “FactorialRecursivo()” la cual retorna el factorial de num.[pic 2]

Vemos que la misma función se llama a sí misma muchas veces para dividir el problema en partes más pequeñas. Dado que muchas funciones con el mismo nombre se llaman, ¿cómo conocería el algoritmo qué función recibe el resultado de la ronda actual?[pic 3]

Al observar la última función de la pila de recursión, se puede encontrar la función de llamada. Al enviar resultados a la función de llamada, la función en la parte superior de la pila se elimina. La nueva función emergente calcula el resultado en función de los resultados devueltos de la función anterior. Este proceso se repite hasta eventualmente agotar la pila y obtener el resultado de la función recursiva.

[pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12]

Pilas y subrutinas (Métodos, SubProgramas etc…)

La mayoría de las implementaciones modernas de una llamada de subrutina utilizan una pila de llamadas, un caso especial de la estructura de datos de la pila, para implementar llamadas y devoluciones de subrutina. Cada llamada a procedimiento crea una nueva entrada, llamada marco de pila, en la parte superior de la pila; cuando el procedimiento regresa, su marco de pila se elimina de la pila, y su espacio puede usarse para otras llamadas de procedimiento. Cada marco de pila contiene los datos privados de la llamada correspondiente, que generalmente incluye los parámetros del procedimiento y las variables internas, y la dirección de retorno.

Evaluaciones aritméticas usando pilas.

La organización de la pila es muy efectiva para evaluar expresiones aritméticas. Las expresiones generalmente se representan en lo que se conoce como notación infija, en la que cada operador se escribe entre dos operandos (es decir, A + B). Con esta notación, debemos distinguir entre (A + B) * C y cómo difiere de A + (B * C) mediante el uso de paréntesis o alguna convención de precedencia de operador. Por lo tanto, el orden de los operadores y operandos en una expresión aritmética no determina de manera exclusiva el orden en que se realizarán las operaciones.

Los humanos utilizamos expresiones infijas en nuestra vida cotidiana. Las computadoras tienen problemas para entender este formato porque deben tener en cuenta las reglas de precedencia del operador y también los corchetes. Las expresiones de prefijo y postfijo son más fáciles de entender y evaluar para una computadora.

Notación polaca (notación prefija):

Se refiere a la notación en la que el operador se coloca antes de sus dos operandos. Aquí no se requieren paréntesis, es decir,

+ AB

Notación polaca inversa (notación postfija) -

Se refiere a la notación análoga en la que el operador se coloca después de sus dos operandos. Nuevamente, no se requieren paréntesis en la notación polaca inversa, es decir,

AB +

Las computadoras organizadas en pila son más adecuadas para la notación postfija que a la infija. Por lo tanto, la notación infija debe convertirse a la notación posterior al arreglo. La conversión de la notación infijada a la notación posterior al arreglo debe tener en cuenta la jerarquía operativa.[pic 13]

Secuencia de pasos evaluar 15 7 1 1 + − ÷ 3 × 2 1 1 + + −

O su equivalente infijo ((15 ÷ (7 − (1 + 1))) × 3) − (2 + (1 + 1)).

Conversión de expresiones aritméticas

De infijo a postfijo

Se puede realizar conversiones, solo con tener en cuenta las siguientes reglas:

• Cuando se lee un número, se agrega inmediatamente a la cola de salida Q.
• Cuando se lee un '(', se agrega inmediatamente a la pila de operadores S.
• cuando lea un ‘)‘, Usando Pop en la Pila S hasta obtener ‘(‘, y agregue todos los operadores salidos de S a Q.
• Al final de la lectura, saque todos los operadores de la pila y colóquelos en la cola Q.
• cuando leemos un operador, necesitamos verificar su precedencia con el operador en la parte superior de la pila.

Ejemplo:

Entrada: I = "2 + 6 * (3 - 4)"

Defina una cola (la cual puede ser implementada con el uso de 2 pilas) Q para registrar la expresión final en notación polaca inversa.

Defina una pila S para contener los operadores.

• Lea 2 de la entrada E. omo 2 es un número, póngalo en Q. ahora Q = [2]
• Lea + de la expresión infija, colóquelo en la pila S, ahora S = [+]
• Lea 6, como es un número, póngalo en Q, ahora Q = [2, 6]
• Lea *, como es un operador, su asociativo izquierdo y su precedencia es mayor que la parte superior de S, póngalo en S, ahora S = [*, +].
• Leer “(“, simplemente colóquelo en la pila. Ahora S = [(, *, +]
• Lea 3, póngalo en Q, ahora Q = [2, 6, 3]
• Lea -, la precedencia de '-' siempre es mayor que ‘)‘, ponga ‘-‘ en S, ahora S = [-, (, *, +]
• Lea 4, póngalo en Q, ahora Q = [2, 6, 3, 4]
• Leer), ahora hacemos pop desde S hasta que obtenemos ‘(‘, todos los operadores a los que se les hizo Pop se agregan a Q.
• Ahora Q = [2, 6, 3, 4, -], S = [*, +]
• Como ya no quedan elementos para insertar; seguimos haciendo Pop en S y colocamos los elementos en Q
• Ahora Q = [2, 6, 3, 4, -, *, +] y S = [].
• Imprimimos Q como cadena para obtener el resultado postfijo: "2 6 3 4 - * +"

De infijo a prefijo.

El algoritmo que nos ayuda a transformar esta función de infija a prefija es parecido al anterior que nos ayudaba a convertirlo a expresión postfija:

...