Skip to content

Tema 4: Estructuras de datos lineales: Pilas y Colas

Resumen Ejecutivo

Esta sesión profundiza en las estructuras de datos lineales restrictivas: Pilas (LIFO) y Colas (FIFO), analizando sus diferencias conceptuales y sus implementaciones estáticas (arrays) y dinámicas (listas enlazadas). Se pone especial énfasis en la programación práctica de estas estructuras en Java mediante el uso de nodos, punteros (top, head, tail) y clases genéricas. Además, se aborda la distinción crítica entre tipos primitivos (int) y clases envolventes (Integer) de cara a la evaluación.

Conceptos Clave

  • Pila (Stack): Estructura LIFO (Last In, First Out). El último en entrar es el primero en salir.
  • Cola (Queue): Estructura FIFO (First In, First Out). El primero en llegar es el primero en ser atendido.
  • Apilar (Push) / Desapilar (Pop): Operaciones fundamentales de inserción y borrado en pilas.
  • Encolar (Enqueue) / Desencolar (Dequeue): Operaciones de inserción al final y borrado al inicio en colas.
  • Top / Cima: Único punto de acceso en una pila.
  • Head (Cabecera) / Tail (Cola): Punteros necesarios para gestionar una cola dinámica eficientemente.
  • Wrapper Class (Integer): Objeto que envuelve un primitivo y permite valores null y métodos auxiliares .

1. El TAD Pila (Stack)

Definición y Lógica

La pila es una estructura de datos de tipo LIFO (Last In First Out). Imagina una pila de platos: pones uno encima de otro y, para sacar el de abajo, primero debes quitar los de arriba. * Restricción de acceso: No es posible acceder a los elementos intermedios; solo se accede al último que ha entrado, es decir, la cima (top) de la pila.

Ejemplos Prácticos de Clase: * Navegador Web: El botón "Atrás" usa una pila. Las URLs se apilan; al volver atrás, se desapila la cima y se muestra la anterior. * Deshacer (Undo/Control+Z): Las acciones se apilan. Al deshacer, se invierte la última acción registrada en la cima .

Operaciones Básicas

Las operaciones siempre ocurren en un extremo: 1. Inicializar: Crear pila vacía. 2. Apilar (Push): Añadir elemento a la cima. 3. Desapilar (Pop): Extraer y eliminar el elemento de la cima. 4. Cima (Peek): Consultar el valor superior sin extraerlo. 5. Vacía/Limpiar: Verificar estado o reiniciar estructura.

2. Implementaciones de Pila

A. Pila Estática (Arrays)

Se usa un contenedor de tamaño fijo (array). * Limitación: Es necesario prefijar el límite de elementos (size). * Lógica del puntero top: * Al inicio, la pila está vacía y \(top = -1\). * Apilar: Se incrementa el índice (\(top = top + 1\)) y se inserta. * Desapilar: Se decrementar el índice (\(top = top - 1\)). * ¡OJO AL DATO!: Si intentas apilar cuando \(top = size - 1\), ocurre un desbordamiento (Pila Llena).

B. Pila Dinámica (Listas Enlazadas)

No tiene límite prefijado de elementos y usa memoria dinámica (nodos). * Estructura: Se comporta como una lista enlazada donde todas las inserciones y borrados ocurren en la posición 0 (el principio de la lista). * Puntero: Solo necesitamos un puntero top (equivalente a first en listas).

Lógica de programación (Ejercicio BrowserHistory): El profesor explicó paso a paso cómo programar esto en Java: 1. Clase Nodo: Contiene el dato (ej. String url) y el puntero next (al siguiente nodo debajo). 2. Método Apilar (visit): * Crear nuevo nodo: Node newNode = new Node(url). * Enlazar: newNode.next = top (el nuevo apunta al antiguo primero). * Actualizar cima: top = newNode. * Incrementar tamaño (size++). 3. Método Desapilar (goBack): * Si está vacía, retornar null/mensaje. * Si no, guardar dato actual. * Mover puntero: top = top.next (la cima pasa a ser el de abajo). * Decrementar tamaño (size--).

3. El TAD Cola (Queue)

Definición y Lógica

Estructura de tipo FIFO (First In First Out). El primero en entrar es el primero en salir. * Restricción: Solo se accede a la cabecera (inicio) para sacar elementos y al final (cola) para meterlos. * Analogía: Una cola en el supermercado o para comprar el pan; se atiende en orden de llegada.

Operaciones Básicas

  1. Encolar (Enqueue): Añadir al final de la cola.
  2. Desencolar (Dequeue): Extraer del principio de la cola.
  3. Primero/Front: Consultar quién es el siguiente en ser atendido sin sacarlo.

4. Implementaciones de Cola

A. Cola Dinámica (Nodos)

A diferencia de la pila, aquí necesitamos controlar dos extremos: * Head (Cabecera): Donde ocurren los borrados (salidas). * Tail (Cola): Donde ocurren las inserciones (entradas).

Lógica de programación (Ejercicio PatientQueue): Se destacó la importancia de gestionar los punteros al insertar/eliminar:

  1. Caso Base (Cola Vacía):

    • Al crearla: head = null, tail = null, size = 0.
    • Al añadir el primer elemento: Tanto head como tail deben apuntar al nuevo nodo (newNode).

  2. Encolar (Añadir Paciente):

    • Crear nodo.
    • Si no está vacía:
      • El último actual debe apuntar al nuevo: tail.next = newNode.
      • Actualizamos el puntero final: tail = newNode (el nuevo es ahora el último).

  3. Desencolar (Atender Paciente):

    • Guardar dato del head.
    • Mover cabeza: head = head.next (el segundo pasa a ser el primero).
    • ¡OJO AL DATO!: Si al sacar un elemento la cola se queda vacía (es decir, head se vuelve null), hay que asegurarse de actualizar también tail a null.

5. Java Práctico: Tipos de Datos y Comparaciones

Para el examen y las actividades, es crucial distinguir entre tipos primitivos y objetos.

int vs Integer

Característica int (Primitivo) Integer (Clase/Wrapper)
Naturaleza Valor simple, no objeto. Objeto que envuelve un entero.
Valor Null No puede ser null (defecto 0). Puede ser null (útil para BD o formularios).
Métodos No tiene métodos. Tiene métodos (parseInt, equals).

Comparación de Objetos (Importante para el examen)

El profesor enfatizó un error común: * Usar == compara referencias de memoria (identificadores), no el contenido del objeto. * Correcto: Para comparar el valor de dos objetos Integer (o String), siempre debes usar el método .equals(). * Ejemplo: if (objetoA.equals(objetoB)) { ... }

Preguntas de Autoevaluación

  1. Si insertas los elementos 1, 2, 3 en una Pila y luego haces dos operaciones de desapilar, ¿qué elemento queda en la cima?
    • Respuesta: El 1. (Entran 1, 2, 3 -> Top es 3. Sale 3, sale 2 -> Top queda en 1).
  2. En una implementación dinámica de una Cola (Queue), ¿por qué es necesario mantener un puntero tail?
    • Respuesta: Para poder realizar la operación de encolar (añadir al final) con eficiencia O(1), sin tener que recorrer toda la lista para encontrar el final.
  3. ¿Cuál es la diferencia crítica al inicializar una cola vacía respecto al primer elemento que se inserta?
    • Respuesta: Al estar vacía, head y tail son null. Al insertar el primer elemento, ambos punteros deben actualizarse para apuntar a ese único nuevo nodo.
  4. ¿Por qué no deberías usar == para comparar dos variables de tipo Integer en Java?
    • Respuesta: Porque == compara si son el mismo objeto en memoria. Si son dos objetos distintos con el mismo valor numérico (fuera del rango de caché de Java), == devolverá false. Se debe usar .equals().
  5. ¿Qué valor tienen top y size al inicializar una pila estática y una dinámica respectivamente?
    • Respuesta: Estática: \(top = -1\), size fijo. Dinámica: top = null, \(size = 0\).