Pilas, colas y árboles: estructuras de datos dinámicas explicadas

Resumen

El documento explica tres estructuras de datos dinámicas: pilas, colas y árboles. Describe el principio LIFO de las pilas y el FIFO de las colas, sus extremos y operaciones básicas, así como las formas de representarlas. Además, presenta los conceptos clave de los árboles, como nodo raíz, nivel, peso, amplitud, hojas, ramas y grado.

Puntos clave

Pila: estructura dinámica lineal que aplica el principio LIFO (último en entrar, primero en salir), con cima y fondo, y operaciones de insertar y eliminar por la cima.
Las pilas pueden representarse mediante vectores, listas enlazadas o bloques.
Cola: estructura dinámica lineal que aplica el principio FIFO (primero en entrar, primero en salir).
En una cola se inserta por el final (punfin) y se elimina por la cabecera (puncol).
Árbol: estructura de datos ramificada y jerárquica formada por nodos, con un nodo raíz como cabecera.
El nivel de un árbol es el número de niveles más uno, y su altura viene dada por el número de nodos de la rama más larga; el peso es la cantidad total de nodos.

Ponte a prueba

Pilas: Estructuras de Datos Dinámicas y Lineales

Pila: Es una estructura de datos dinámica y lineal donde se almacenan los datos en bloques que están superpuestos, es decir, uno encima del otro.

Características de las Pilas

1) Se aplica el principio LIFO para almacenar los datos (Last In, First Out - último en entrar, primero en salir).
2) La pila posee dos extremos: la cima y el fondo.
3) Se realizan las funciones de insertar y eliminar; ambas operaciones se realizan por encima de la pila.
4) Se usa el apuntador denominado punpil para denotar la cima o cabecera de la pila.

Formas de Representación de una Pila

1. Vectores
2. Listas enlazadas
3. Bloques

Colas: Funcionamiento y Características

Colas: Es una estructura de datos dinámica lineal donde los datos se almacenan en bloques o nodos aplicando el principio FIFO (First In, First Out - primero en entrar, primero en salir). Los datos se ubican en línea, es decir, uno detrás del otro.

Características de las Colas

1) La cola posee dos extremos: la cabecera se denomina puncol y la cola se denomina punfin.
2) Se realizan las operaciones de insertar y eliminar.
3) Se insertan los datos por el final de la cola (punfin).
4) Se eliminan los datos por la cabecera de la cola (puncol).

Formas de Representación de una Cola

1) Lista enlazada
2) Bloques
3) Vectores

Árboles: Estructuras de Datos Jerárquicas

Árbol: Es una estructura de datos ramificada (no lineal) que está constituida por nodos, que es el espacio donde se almacenan los datos. Esta estructura es jerárquica y posee como cabecera la raíz del árbol, que representa el padre o la madre de la estructura.

Conceptos Clave de los Árboles

Nodo Raíz: Representa el nodo padre o la cabecera del árbol. Cualquier operación que se realice sobre el árbol se inicia por el nodo raíz.
Nivel: Representa la distancia entre el nodo raíz y los nodos hojas (altura o profundidad).
- 1) Es el número de niveles más uno.
- 2) Viene dada por el número de nodos de la rama más larga.
Peso del Árbol: Es la cantidad de nodos que posee el árbol.
Amplitud: Viene dada por la máxima cantidad de nodos que posea cualquiera de los niveles del árbol.
Nodos Hojas: Son nodos que no poseen descendientes, es decir, hijos.
Nodos Ramas: Son aquellos nodos que no representan al nodo raíz pero tampoco a los nodos hojas; se denominan nodos intermedios.
Grado: Viene dado por la cantidad de nodos que tiene más hijos.

Preguntas frecuentes

¿Qué significa el principio LIFO en una pila?

LIFO significa Last In, First Out, es decir, el último dato en entrar es el primero en salir. Las operaciones de insertar y eliminar se realizan por encima de la pila.

¿En qué se diferencia una cola de una pila?

Una cola aplica el principio FIFO (primero en entrar, primero en salir), mientras que una pila aplica LIFO. En una cola los datos se insertan por el final y se eliminan por la cabecera.

¿Qué son los nodos hojas de un árbol?

Los nodos hojas son aquellos que no poseen descendientes, es decir, no tienen hijos. Los nodos ramas son los intermedios, que no son ni la raíz ni hojas.