Arbol Y Pila

INTRODUCCIÓN

En este trabajo se estudian en detalle las estructuras de datos pilas y arboles que son probablemente las utilizadas más frecuentemente en los programas más usuales. Las pilas se conocen también como estructuras lifo (last-in, first-out, último en entrar-primero en salir).Entre las numerosas aplicaciones de las pilas destaca la evaluación de expresiones algebraicas, así como laorganización de la memoria. Los árboles son muy utilizados para representar formulas algebraicas como un método eficiente para búsquedas generales y complejas, listas dinámicas y aplicaciones diversas tales como inteligencia artificial o algoritmos de cifrado.

PILA

Una pila (stack) es una colección ordenada de elementos a los que sólo se puede acceder por un único lugar o extremo de lapila. Los elementos de la pila se añaden o quitan (borran) de la misma sólo por su parte superior (cima) de la pila. Éste es el caso de una pila de platos, una pila de libros, etc.

Una pila es una estructuta de datos de entradas ordenadas tales que soolo se pueden introducir y eliminar por un extremo que se llama cima.

Cuando se dice que la pila está ordenada, lo que se quiere decir es que hayun elemento al que se puede acceder primero (el que está encima de la pila), otro elemento al que se puede acceder en segundo lugar (justo el elemento que está debajo de la cima), un tercero, etc. No se requiere que las entradas se puedan comparar utilizando el operador «menor que» (<) y pueden ser de cualquier tipo.
Las entradas de la pila deben ser eliminadas en el orden inverso al que sesituaron en la misma. Por ejemplo, se puede crear una pila de libros, situando primero un diccionario, encima de él una enciclopedia y encima de ambos una novela de modo que la pila tendrá la novela en la parte superior.

Cuando se quitan los libros de la pila, primero debe quitarse la novela, luego la enciclopedia y, por último, el diccionario. Debido a su propiedad específica «último en entra6primero en salir» se conoce a las pilas como estructura de datos LIFO (last-in, first-out). Las operaciones usuales en la pila son Insertar y Quitar. La operación Insertar (push) añade un elemento en la cima de la pila y la operación Quitar (pop) elimina o saca un elemento de la pila. La Figura muestra una secuencia de operaciones Insertar y Quitar. El último elemento añadido a la pila es el primeroque se quita de la pila.

La operación Insertar (push) sitúa un elemento dato en la cima de la pila y Quitar (pop) elimina o quita el elemento de la pila.

La pila se puede implementar mediante arrays en cuyo caso su dimensión o longitud es fija, y mediante punteros o listas enlazadas en cuyo caso se utiliza memoria dinámica y no existe limitación en su tamaño.

Una pila puede estar vacía(no tiene elementos) o llena (en el caso de tener tamaño fijo, si no cabe más elementos en la pila). Si un programa intenta sacar un elemento de una pila vacía, se producirá un error debido a que esa operación es imposible; esta situación se denomina desbordamiento negativo (underflow). Por el contrario, si un programa intenta poner un elemento en una pila se produce un error llamado desbordamiento(overflow) o rehosamiento. Pata evitar estas situaciones se diseña funciones, que comprueban si la pila está llena o vacía.

ESPECIFICACIONES DE UNA PILA

Las operaciones que sirven para definir una pila y poder manipular su contenido son las siguientes (no todas ellas se implementan al definir una pila).

Tipo de dato | Dato que se almacena en la pila. |
Insertar (push) | Insertar undato en la pila. |
Quitar (pop) | Sacar (quitar) un dato de la pila. |
Pila vacía | Comprobar si la pila no tiene elementos. |
Pila llena | Comprobar si la pila está llena de elementos. |
Limpiar pila | Quitar todos sus elementos y dejar la pila vacía. |
Tamaño de la pila | Número de elementos máximo que puede contener la pila. |
Cima | Obtiene el elemento cima de la pila. |

EL TIPO...