2.1 Introducción
Una PILA es una estructura ordenada y homogénea, en la que podemos apilar o desapilar elementos en una única posición llamada CIMA, siguiendo una política LIFO (Last In, F56irst Out).
2.2 Representación de pilas en arrays
Utilizaremos un arreglo llamado Pila de tamaño máximo MaxElemPila y una variable llamada Cima que indicará cual es el último elemento ocupado en el arreglo (es decir la variable Cima contiene la posición del elemento que se encuentra en la cima de la pila).
2.4 Expresiones aritméticas, notación polaca
La notación polaca es la originada por un Autómata con pila, en la que los operadores siempre preceden a los operandos sobre los que actúan, y que tiene la ventaja de no necesitar paréntesis:
Estándar
Ejemplo 1: 2 * ( 3 + 5 )
Ejemplo 2: 2 * 3 + 5
Polaca
Ejemplo 1: * 2 + 3 5
Ejemplo 2: + * 2 3 5
2.5 Recursividad
La recursividad es una característica de los lenguajes de programación en virtud de la cual se permite que un procedimiento haga referencia a sí mismo dentro de su definición.
La definición recursiva debe estar hecha de manera que la cadena de invocaciones termine en algún momento con una llamada que no genere nuevas invocaciones.
La recursión en los subprogramas puede darse de dos maneras diferentes:
a) Directa:
El El subprograma se llama directamente a sí mismo.
Recursión directa
b) Indirecta: El subprograma llama a otro subprograma y éste a su vez llama al primero.Recursión indirecta
La construcción de estos procedimientos no sigue una fórmula concreta, pero el programador puede utilizar la noción de inducción de la siguiente forma:
1. Solucionar el caso/s más simple. Caso base.
2. Expresar el caso general en función de casos más simples que tiendan hacia el caso base.
3. Desarrollar el algoritmo recursivo, que en general tendrá la siguiente estructura:
Si estamos en un caso base entonces
Devolver la solución al caso base
a) Sino
b) - Descomposición del problema
c) - Llamada recursiva
d) - Obtención de la solución a partir del resultado obtenido en la llamada recursiva.
e) - Devolver solución.
f) Fin si
2.6 Comparación de pilas y colas
La diferencia radica en cuales son los elementos que salen primero:
-> Pilas (Primeras en entrar, Ultimas en salir): Son como una pila de libros, los primeros que entran a la pila son los últimos que salen porque quedan abajo de los últimos.
-> Colas(Primeras en entrar, Primeras en salir): Son como la cola para comprar un boleto del cine, los primeros en entrar a la cola son los primeros que salen de ella.
-> Pilas (Primeras en entrar, Ultimas en salir): Son como una pila de libros, los primeros que entran a la pila son los últimos que salen porque quedan abajo de los últimos.
-> Colas(Primeras en entrar, Primeras en salir): Son como la cola para comprar un boleto del cine, los primeros en entrar a la cola son los primeros que salen de ella.
2.7 Ejemplos
No hay comentarios:
Publicar un comentario