Estructuras de Datos: Colas, Pilas y Listas Enlazadas

Colas (Queue) - Estáticas

Una cola es una estructura de datos caracterizada por ser una secuencia de elementos en la que la operación de inserción (push) se realiza por un extremo y la operación de extracción (pop) por el otro.

Apuntadores (Repaso)

Los apuntadores son variables que contienen direcciones de memoria como sus valores. Es decir, contienen la dirección de una variable que contiene un valor específico. En este sentido, el nombre de una variable se refiere directamente a un valor y un apuntador se refiere indirectamente a un valor. Referirse a un valor a través de un apuntador se conoce como indirección.

Recomendaciones para el Uso de Apuntadores:

• Incluya las letras Ptr en el nombre de una variable de apuntador para indicar claramente que se trata de un apuntador y debe manejarse de forma apropiada.
• Inicialice los apuntadores para evitar resultados inesperados. Inicializar un apuntador a 0 es equivalente a inicializarlo a NULL (una constante simbólica).
• Evite desreferenciar un apuntador que no haya sido correctamente inicializado o asignado a una posición específica en memoria. Esto podría causar un error fatal en tiempo de ejecución o modificar accidentalmente datos importantes.
• Asegúrese de desreferenciar un apuntador cuando sea necesario obtener el valor al cual apunta.

Estructuras de Datos Dinámicas

Clasificación de las Listas Enlazadas

Las listas se pueden dividir en cuatro categorías:

• Listas simplemente enlazadas: Cada nodo (elemento) contiene un único enlace que conecta ese nodo al nodo siguiente o sucesor. La lista es eficiente en recorridos directos ("adelante").
• Listas doblemente enlazadas: Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor. La lista es eficiente tanto en recorrido directo ("adelante") como en recorrido inverso ("atrás").
• Lista circular simplemente enlazada: Una lista simplemente enlazada en la que el último elemento (cola) se enlaza al primer elemento (cabeza), de modo que la lista puede ser recorrida de modo circular ("en anillo").
• Lista circular doblemente enlazada: Una lista doblemente enlazada en la que el último elemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo circular (en anillo) tanto en dirección directa ("adelante") como inversa ("atrás").

Listas Simplemente Enlazadas

El primer nodo, o frente, de una lista es el nodo apuntado por cabeza (también llamado nodo List). La lista encadena nodos juntos desde el frente hasta el final (cola) de la lista. El final se identifica como el nodo cuyo campo de enlace tiene el valor NULL. La lista se recorre desde el primer hasta el último nodo; en cualquier punto del recorrido, la posición actual se referencia por el puntero actual. Una lista vacía, es decir, que no contiene nodos, se representa con el puntero cabeza (List) apuntando a NULL.

Operaciones de Listas Enlazadas

La implementación del TAD Lista requiere, en primer lugar, declarar la clase Nodo, que contiene el dato (entero, real, doble, carácter o referencias a objetos) y el enlace. Además, se necesita la clase Lista con las operaciones (creación, inserción, etc.) y el atributo cabeza de la lista.

Clase ListaSimple – C++

Insertar al Inicio de la Lista

La posición más fácil y eficiente para insertar un nuevo elemento en una lista es por el inicio. El proceso de inserción se resume en este algoritmo:

1. Crear un nodo e inicializar el campo dato con el nuevo elemento. La dirección del nodo creado se asigna a nuevo.
2. Hacer que el campo enlace del nodo creado apunte al inicio (primero) de la lista.
3. Hacer que primero apunte al nodo que se ha creado.

Pilas (Stack) - Estáticas

Una pila representa una estructura lineal de datos que almacena y recupera sus elementos siguiendo un estricto orden, donde se pueden agregar o quitar elementos únicamente por uno de los dos extremos.