Particularizando en la EDD lista
Hay dos casos especiales de
listas que vamos a estudiar con más detalle: pilas y colas.
Son listas en las que hemos
restringido las operaciones que pueden hacerse para conseguir de ellas un
comportamiento concreto.
Pilas
Tipo especial de lista en las
que las inserciones y los borrados de los elementos se realizan sólo por un
extremo que se denomina cima de la pila.
El concepto es muy similar a
una pila de platos o papeles: yo puedo dejar sobre todo lo que hay, o coger
sólo el elemento que hay encima de todo (en la cima), pero no puedo coger
elementos de en medio o de la parte de abajo.
La pila es una estructura LIFO
(Last In, First Out): el último en enterar es el primero en salir.
Operaciones sobre una pila
Cuatro operaciones posibles:
è Inicializar
è Comprobar si la pila está vacía
è Push (meter)
è Pop (sacar)
Implementación: Como una lista
pero restringiendo las operaciones posibles
Funcionamiento de una pila
Aplicaciones de las pilas
Llamadas a subprogramas:
Durante la ejecución de un programa, se guarda en la pila de ejecución las
funciones que se van llamando para poder retomar luego de manera adecuada al
punto de llamada.
Evaluación de expresiones en
notación postfija.
Esta notación permite expresar
la prioridad de las operaciones en una expresión sin necesidad de hacer uso de
paréntesis.
Consiste en colocar primero
los dos operandos que participan en la operación y posteriormente el signo.
La forma de evaluarlas es,
cuando aparece un número se mete en la pila, cuando se ve un operador, se saca
de la pila los operandos necesarios y se efectúa la operación metiendo el
resultado en la pila.
Evaluación de expresiones en
notación postfija: Ejemplo
è ((3+4)+((1+2)*3))-9
è 3 4 + 1 + 2 + 3 * + 9 -
0 comments:
Publicar un comentario