Introducción a las Estructuras de Datos

Vista previa del material en texto

Introducción a las Estructuras de Datos: 
Pilas. 
Una pila (stack en inglés) es una estructura de datos en la que el modo de acceso 
a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, 
primero en salir) que permite almacenar y recuperar datos, es decir, la inserción y 
extracción de elementos de la pila siguen el principio LIFO ya que el último 
elemento que se agrega a la pila es el primero en salir de la misma. Tanto la 
inserción como la eliminación de los elementos de una pila se realizan solo por un 
extremo que se denomina tope, es decir, que el último elemento en entrar, es el 
único accesible en cada momento. 
 
Tipos. 
Pila de llamada: Es un segmento de memoria que utiliza esta estructura de datos 
para almacenar información sobre las llamadas a subrutinas actualmente en 
ejecución en un programa en proceso. 
 Cada vez que una nueva subrutina es llamada, se apila una nueva entrada con 
información sobre esta tal como sus variables locales. En especial, se almacena 
aquí el punto de retorno al que regresar cuando esta subrutina termine (para 
volver a la subrutina anterior y continuar su ejecución después de esta llamada). 
Como tipo abstracto de datos: La pila es un contenedor de nodos y tiene dos 
operaciones básicas, push (o apilar) y pop (o desapilar). “Push” añade un nodo a 
la parte superior de la pila, dejando por debajo el resto de los nodos. “Pop” elimina 
y devuelve el actual nodo superior de la pila. 
Funcionalidades. 
Las pilas se utilizan en muchas aplicaciones que utilizamos con frecuencia: 
• Gestión de ventanas en Windows o Linux (cuando cerramos una ventana 
siempre recuperamos la que teníamos detrás). 
• Evaluación general de cualquier expresión matemática para evitar tener que 
calcular el número de variables temporales que hacen falta. 
• Navegador Web 
– Se almacenan los sitios previamente visitados 
– Cuando el usuario quiere regresar (presiona el botón de retroceso o regresar), 
simplemente se extrae la última dirección (pop) de la pila de sitios visitados. 
• Editores de texto u otras herramientas 
– Los cambios efectuados se almacenan en una pila 
– El Usuario puede deshacer los cambios mediante la operación “undo” o 
deshacer, la cual extrae el estado del texto o cualquier elemento, antes del último 
cambio realizado. 
Colas. 
 Una cola es una estructura de datos en la que el modo de acceso a sus 
elementos es de tipo FIFO (del inglés First Input First Output, primero en entrar, 
primero en salir). Permite almacenar y recuperar datos, es decir, la inserción y 
extracción de elementos de la cola siguiendo el principio FIFO. Cuando se agrega 
un elemento a la cola, éste se agrega al final. Cuando se elimina un elemento de 
la cola, se elimina el que está al frente de la cola, es decir, el primero 
Tipos. 
Colas circulares: Es aquella en la cual el sucesor del último elemento es el 
primero. Por lo tanto, el manejo de las colas como estructuras circulares permite 
un mejor uso del espacio de memoria reservando para la implementación de las 
pilas. 
Colas dobles: Permiten realizar las operaciones de inserción y eliminación por 
cualquiera de sus extremos. 
Una cola doble también puede ser circular, en dicho caso, será necesario que los 
métodos de inserción y eliminación (sobre cualquiera de los métodos de inserción 
y eliminación (sobre cualquiera de los extremos) considere el movimiento 
adecuado de los punteros. 
Colas de Prioridad: En ellas, los elementos se atienden en el orden indicado por 
una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, 
se atenderán de modo convencional según la posición que ocupen. Hay dos 
formas de implementación. 
 Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la 
cola ordenada por orden de prioridad. 
 Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola. 
Bicolas de entrada registrada: Son aquellas donde la inserción solo se hace por 
el final, aunque podemos eliminar al inicio o al final. 
Bicolas de salida restringida: Son aquellas donde solo se elimina por el final, 
aunque se puede insertar al inicio y al final. 
Funcionalidades. 
Las colas se utilizan en muchas aplicaciones que utilizamos con frecuencia. 
 Impresión de documentos: Cuando imprimimos varios documentos, éstos 
se imprimen en el orden en que lo mandamos a imprimir. 
 Los números de tickets para atender público. 
 La simulación de cualquier cola de elementos. 
Árboles. 
Un árbol es una estructura de datos que consta de un conjunto finito de 
elementos, denominados nodos y un conjunto finito de líneas dirigidas 
denominadas ramas que conectan los nodos. 
 
Estructura de un árbol 
Si un árbol no está vacío, pueden distinguirse varias partes: la raíz, nodos hijos, 
nodos padres, nodos hojas, ramas. 
Raíz: es el primer nodo del árbol. 
Nodos hijos: son los sucesores de otros nodos. 
Nodos padre: son nodos que tienen nodos sucesores. 
Nodos hojas: son los nodos terminales, es decir, los que no tienen nodos hijos. 
Ramas: corresponde a un conjunto de nodos conectados. 
Tipos. 
Arboles binarios: Se define un árbol binario como un conjunto finito de elementos 
(nodos) que bien está vacío o está formado por una raíz con dos árboles binarios 
disjuntos, es decir, dos descendientes directos llamados subárbol izquierdo y 
subárbol derecho. 
 Los árboles binarios (también llamados de grado 2) tienen una especial 
importancia. 
 Las aplicaciones de los arboles binarios son muy variadas ya que se les puede 
utilizar para representar una estructura en la cual es posible tomar decisiones con 
dos opciones en distintos puntos. 
Arboles Binarios De Búsqueda: Son árboles binarios ordenados. Desde cada 
nodo todos los nodos de una rama serán mayores, según la norma que se haya 
seguido para ordenar el árbol, y los de la otra rama serán menores. 
 Los árboles binarios se utilizan frecuentemente para representar conjuntos de 
datos cuyos elementos se identifican por una clave única. Si el árbol está 
organizado de tal manera que la clave de cada nodo es mayor que todas las 
claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho 
se dice que este árbol es un árbol binario de búsqueda. 
Arboles- B: Son árboles cuyos nodos pueden tener un número múltiple de hijos 
 
 
 
 
 
 
 
 
Autor: 
Nombre: Katherin Carrillo 
C.I: 31.040.100 
Profesor: Edgar Valero 
Institución: Universidad Politécnica del Estado Trujillo.