Teoria De Las Pilas y Colas

1) TEORIA DE PILAS Y COLAS:
-DEFINICION DE PILAS:
Una pila es una estructura de datos de acceso restrictivo a sus elementos. Se puede entender como una pila de libros que se agrupan de abajo hacia arriba. En principio no hay libros; después ponemos uno, y otro encima de éste, y así sucesivamente. Posteriormente los solemos retirar empezando desde la cima de la pila de libros, es decir, desde elúltimo que pusimos, y terminaríamos por retirar el primero que pusimos, posiblemente ya cubierto de polvo.
Es una estructura de tipo LIFO (Last In First Out), es decir, último en entrar, primero en salir.
-OTRA DEFINICION:
Una pila es una lista en que tanto las inserciones como las supresiones se hacen por el mismo extremo, que se conoce como el tope de la pila.
EJEMPLO:
[pic]
-DEFINICIONDE COLAS:
Una cola es una estructura de datos de acceso restrictivo a sus elementos. Un ejemplo sencillo es la cola del cine o del autobús, el primero que llegue será el primero en entrar, y afortunadamente en un sistema informático no se cuela nadie salvo que el programador lo diga.
Es una estructura de tipo FIFO (First In First Out), es decir: primero en entrar, primero en salir.



-OTRADEFINICION:
Es una lista de proceso restringido en la cual las inserciones se hacen por un extremo llamado "último" y las eliminaciones se hacen por el otro extremo llamado "delantero". Por ejemplo, los aviones que esperan despegar de un aeropuerto forman una cola, el que llega a la pista queda de último y el que va a despegar está de delantero en la cola.

EJEMPLO:
[pic]
2) FUNCIONES Y USOSDE LAS PILAS Y COLAS:
-FUNCIONES Y USOS DE LAS PILAS:
A) Se emplea en compiladores y editores de texto dirigidos por la sintaxis.
-Permiten comprobar fácil y eficientemente que los símbolos cuyo uso solo tiene sentido por parejas (llaves, paréntesis, etc.) estén adecuadamente balanceados.
B) También se emplea para la evaluación de expresiones.
-Las expresiones escritas en notaciónconvencional (infija, 7 * 2 + 8) pueden convertirse en notación postfija (7 2 * 8 +) mediante una pila.
-Las expresiones escritas en notación postfija pueden calcularse mediante una pila.
-Una función muy importante de las pilas es la implementación en el código compilado de las llamadas a función realizadas en el código fuente.
-También se emplean para transformar un algoritmo recursivo en otro iterativoequivalente.
-FUNCIONES Y USOS DE LAS COLAS:
A) Se emplea en las operaciones sobre las estructuras de datos de otros TADs por ejemplo:
-Recorrido “por niveles” de los nodo de un árbol.
-Recorrido “primero en anchura” de los nodos de un grafo.
-Obtención “de un orden topológico” de los nodos de un grafo aciclico.
B) Algunos servicios de un sistema operativo también se basan en el TAD colapor ejemplo:
-Servicio de Impresión: Los documentos enviados a una impresora se sitúan en una “ cola de impresión” hasta que pueden ser impresos. Las peticiones de impresión se gestionan casi como una cola (orden de llegada, salvo cancelaciones.)
-Planificador: Diferentes estrategias de planificación de procesos (round robin, prioridades, etc.) emplean colas para los procesos que se van aejecutar y determinar en que orden.
-También se emplean en algoritmos de simulación para problemas de teorías de colas.
3) OPERACIONES DE LAS PILAS Y DE LAS COLAS:
-OPERACIONES DE LAS PILAS:
Operaciones básicas con pilas:
Las pilas tienen un conjunto de operaciones muy limitado, sólo permiten las operaciones de "push" y "pop":
-Push: Añadir un elemento al final de la pila.
-Pop: Leer y eliminar unelemento del final de la pila.

-Push, insertar elemento:

Las operaciones con pilas son muy simples, no hay casos especiales, salvo que la pila esté vacía.






-Push en una pila vacía:

Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero a la pila valdrá NULL:
[pic]
El proceso es muy simple, bastará con que:
1....