Particularizaciones de 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 la 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 entrar es el primero en salir.
Operaciones sobre una pila
Cuatro operaciones posibles:
- inicializar
- Comprobar si está vacía
- push (meter)
- pop (sacar)
Implementación: Como una lista
pero restringiendo las operaciones posibles.
Funcionamiento de una pila
(dibujo)
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 retornar luego de manera adecuada al punto de
llamada.
Evaluación de expresiones en
notación postfija.
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 (dibujo)
0 comentarios:
Publicar un comentario