Tema 2: Tipos Abstractos de Datos: Listas, Pilas, Colas.

Diapositivas de clase.

• Aquí puedes descargar las diapositivas utilizadas en clase, que prácticamente contienen lo mismo que la web: diapositivas tema 2

Presentación.

• Son una serie de TADs considerados fundamentales.
• Las listas son secuencias de elementos.
• Pueden ser implementadas de distinto modo.
• Pilas y colas son un tipo especial de listas

Listas.

• Son flexibles, pueden crecer y decrecer.

• Podemos acceder a cualquier posición dentro de la lista.

• Podemos insertar y borrar elementos de cualquier posición.

• Pueden ser concatenadas o divididas (sublistas ).

• Una lista se suele representar como una sucesión de elementos separados por comas: (a₁, a₂, …, a_n : n >= 0).

• Matemáticamente una lista es una secuencia de cero o más elementos.

• Si tiene 0 elementos se llama lista vacía.

• (a₁) es el primer elemento (cabeza ) y (a_n) el último (cola ).

• Decimos que (a_i) precede a (a_i+1) y (a_i) sucede a (a_i-1) y que (a_i) ocupa la posición i-ésima.

Listas. Operaciones básicas.

• Insert (L, x, i) : añade el elemento x a la lista L en la posición i. Implica reorganizar los elementos de la lista.

• Append (L, x) : añade el elemento x al final de la lista L. Si se ha podido hacer devuelve el valor booleano true y si no false.

• Retrieve (L, i) : Devuelve el elemento en la posición iésima o null si no existe.

• Delete (L, i) : Elimina el elemento de la posición iésima. Si se ha podido hacer devuelve el valor booleano true y si no false. Implica reorganizar los elementos de la lista.

• Length (L) : Devuelve |L|, la longitud de L.

• Reset (L) : Hace que la posición actual sea igual la cabeza de la lista y devuelve el valor 1, si la lista está vacía devuelve 0.

• Current (L) : Devuelve la posición actual en la lista L.

• Next (L) : Incrementa y devuelve la posición actual en la lista L.

Listas. Implementación.

• Aprovechamos el uso de un LOO como es C++.

• Usaremos todos los términos en inglés.

• Cada TAD será una clase, p.e.:

  typedef char Element;           // Hasta que veamos genericidad
                                  // usaremos estos typedef.
  typedef int  Position;
  
  class List {
    public:
      void insert (Element x, Position i); // Dónde está el primer
                                           // parámetro 'L'?
      ...
  };
  
  List l;
  l.insert ('a', 1);

• Diversas opciones para la representación interna.

• Puede ser un vector (array ).

• Puede ser una serie de elementos en la cual cada uno sabe sólo cuál es su siguiente (simplemente enlazada ):

Pilas.

• Una pila es un tipo especial de lista.
• Sigue unas normas estrictas en lo referente a la inserción y extracción de elementos.
• Es una estructura LIFO (Last In, First Out ).

Pilas. Operaciones básicas.

• Push (S, x) : Inserta x en S.

• Top (S) : Devuelve el último dato insertado en S (cabeza). Aplicada sobre una pila vacía lanzará una excepción de tipo EmptyStackException.

• Pop (S) : Elimina el último dato insertado en S (cabeza). En la práctica lo devuelve antes de eliminarlo. Aplicada sobre una pila vacía lanzará una excepción de tipo EmptyStackException.

• Empty (S) : Devuelve true si la pila no tiene elementos.

Ejemplo, apilamos A, B, C y desapilamos.

Figura 3: Apilar.

Pilas. Implementación.

• Hemos dicho que son una Lista pero con ciertas restricciones.

• Podemos aprovechar el concepto de herencia de la POO.

• ¿Sería válida esta implementación de la clase Pila?:

  class Stack : public List {
  public:
    void push (Element x);
  ...
  };

• ¿Y esta?:

  #include "list.h"
  
  class Stack : private List {
  public:
    void push (Element x);
  ...
  };

• ¿O esta otra?:

  #include "list.h"
  
  class Stack {
  public:
    void push (Element x);
  ...
  private:
    List _l;
  };

Colas.

• Una cola es un tipo especial de lista.
• Sigue unas normas estrictas en lo referente a la inserción y extracción de elementos.
• Es una estructura FIFO (First In, First Out ).

Colas. Operaciones básicas.

• Enqueue (Q, x) : Inserta x en Q.

• Head (Q) : Devuelve el dato que más tiempo lleva en Q (cabeza). Aplicada sobre una cola vacía lanzará una excepción de tipo EmptyQueueException.

• Dequeue (Q) : Elimina el dato que más tiempo lleva en Q (cabeza). Aplicada sobre una cola vacía lanzará una excepción de tipo EmptyQueueException.

• Empty (Q) : Devuelve true si la cola no tiene elementos.

  Por completitud, al dato que menos tiempo lleva en la cola se le llama cola (del inglés tail ).

Ejemplo, encolamos A, B, C y desencolamos.

Figura 4: Encolar.

Colas. Implementación.

• Hemos dicho que son una Lista pero con ciertas restricciones.

• Podemos aprovechar el concepto de herencia de la POO.

• ¿Sería válida esta implementación de la clase Cola?:

  class Queue : public List {     // Herencia pública.
  public:
    void enqueue (Element x);
  ...
  };

• ¿Y esta?:

  #include "list.h"
  
  class Queue : private List {    // Herencia privada
  public:
    void enqueue (Element x);
  ...
  };

• ¿O esta otra?:

  #include "list.h"
  
  class Queue {
  public:
    void enqueue (Element x);
  ...
  private:
    List _l;                      // Composición
  };

Ejemplo 1: implementación iterativa de una lista, con solo nodos (sin struct Lista).

• Aquí tienes un ejemplo de cómo se podría implementar una lista de forma sencilla utilizando únicamente un struct.

#include <iostream>

using namespace std;

struct Nodo {
    int dato;
    Nodo* siguiente;
};

// Función para insertar un elemento al final de la lista
void insertar(Nodo*& cabeza, int valor) {
    Nodo* nuevo = new Nodo{valor, nullptr};
    if (!cabeza) {
        cabeza = nuevo;
    } else {
        Nodo* temp = cabeza;
        (*temp).siguiente;
        while (temp->siguiente) {
            temp = temp->siguiente;
        }
        temp->siguiente = nuevo;
    }
}

// Función para liberar la memoria de la lista
void liberarLista(Nodo*& cabeza) {
    while (cabeza) {
        Nodo* temp = cabeza;
        cabeza = cabeza->siguiente;
        delete temp;
    }
    cabeza = nullptr;
}

int main() {
    Nodo* lista = nullptr;

    insertar(lista, 10);
    insertar(lista, 20);
    insertar(lista, 30);

    //Intenta implementar una función que imprima los datos de la lista y comprueba que realmente se están añadiendo.

    liberarLista(lista);
    return 0;
}

Ejemplo 2: implementación iterativa de una lista.

• Aquí tienes otra alternativa, en la cuál una lista la representamos por el registro Lista, que contiene un puntero a un nodo llamado cabeza, que se trata del primer nodo de la lista (inicialmente con valor nullptr). En este caso, la implementación sigue una forma iterativa (como el Ejemplo 1). En el siguiente apartado puedes ver una versión recursiva de este código.

// Forma iterativa.

#include <iostream>

using namespace std;

struct Nodo
{
    int valor;
    Nodo *siguiente;
};

struct Lista
{
    Nodo *cabeza;
    //Más todo lo que necesites para la lista...
};

bool insertaNodo(Lista &l, Nodo *n, unsigned posicion)
{
    if (n == nullptr) return false;

    Nodo **nodoActual = &l.cabeza;

    for (unsigned i=0; i < posicion; i++)
    {
        if (*nodoActual == nullptr)
            return false;
        nodoActual = &((*nodoActual)->siguiente);
    }

    n->siguiente = *nodoActual;
    *nodoActual = n;
    return true;
}

void imprimeLista(const Lista &l)
{
    const Nodo *nodoActual = l.cabeza;

    while(nodoActual != nullptr)
    {
        cout << nodoActual->valor << " ";
        nodoActual = nodoActual->siguiente;
    }
    cout << endl;
}

//Función que crea un nuevo nodo con memoria dinámica para poder utilizarlo fuera de la función.
Nodo* creaNodo(int valor)
{
    Nodo* nodoNuevo = new Nodo;
    nodoNuevo->valor = valor;
    nodoNuevo->siguiente = nullptr;
    return nodoNuevo;
}


int main()
{
    Lista lista;
    lista.cabeza = nullptr; //inicialización de lista vacía.

    Nodo* n1 = creaNodo(4);
    Nodo* n2 = creaNodo(8);
    Nodo* n3 = creaNodo(16);

    insertaNodo(lista, n1, 0);
    insertaNodo(lista, n2, 1);
    insertaNodo(lista, n3, 3);

    imprimeLista(lista);
}

Ejemplo 3: implementación recursiva de una lista.

• Esta es la versión recursiva del ejemplo 2. Si te fijas, la recursión es otra forma de implementar un bucle. En un bucle, tenemos lo siguiente:

mientras (condición parada)
{
    Instrucciones
    Acción que puede llevar a la finalización del bucle (incremento la mayor parte de las veces)
}

En una función recursiva, este bucle se puede reescribir de la siguiente manera:

recursividad ()
{
    condición parada (caso base)

    Instrucciones
    Acción que puede llevar a la finalización del bucle (incremento la mayor parte de las veces)
}

// Forma recursiva.

#include <iostream>

using namespace std;

struct Nodo
{
    int valor;
    Nodo *siguiente;
};

struct Lista
{
    Nodo *cabeza;
    //Más todo lo que necesites para la lista...
};

bool insertaNodoRecursivo(Nodo **nodoActual, Nodo *n, unsigned i, unsigned posicion)
{
    if (n == nullptr)
        return false;

    if (i == posicion)
    {
        n->siguiente = *nodoActual;
        *nodoActual = n;
        return true;
    }

    if (*nodoActual == nullptr) return false;

    return insertaNodoRecursivo(&(*nodoActual)->siguiente, n, i+1, posicion);
}

//Al trabajar con un registro Lista y registros Nodo, podemos separar en dos funciones y hacer recursiva la de los nodos,
//que es la que repite las operaciones hasta encontrar la posición buscada.
bool insertaNodoRecursivoLista(Lista &l, Nodo *n, unsigned posicion)
{
    return insertaNodoRecursivo(&l.cabeza, n, 0, posicion);
}


void imprimeNodosRecursivo(const Nodo *nodoActual) {
    if (nodoActual == nullptr) {
        return;
    }

    cout << nodoActual->valor << " ";
    imprimeNodosRecursivo(nodoActual->siguiente);
}

void imprimeListaRecursivo(const Lista &l) {
    imprimeNodosRecursivo(l.cabeza);
    cout << endl;
}

//Función que crea un nuevo nodo con memoria dinámica para poder utilizarlo fuera de la función.
Nodo* creaNodo(int valor)
{
    Nodo* nodoNuevo = new Nodo;
    nodoNuevo->valor = valor;
    nodoNuevo->siguiente = nullptr;
    return nodoNuevo;
}


int main()
{
    Lista lista;
    lista.cabeza = nullptr; //inicialización de lista vacía.

    Nodo* n1 = creaNodo(4);
    Nodo* n2 = creaNodo(8);
    Nodo* n3 = creaNodo(16);

    insertaNodoRecursivoLista(lista, n1, 0);
    insertaNodoRecursivoLista(lista, n2, 1);
    insertaNodoRecursivoLista(lista, n3, 3);

    imprimeListaRecursivo(lista);
}

Consejos para la recursividad

Si te fijas, la recursión puede verse como otra forma de expresar una repetición (un bucle).

En un bucle

Un bucle repite un bloque de instrucciones mientras se cumpla una condición:

mientras (condición de continuación)
{
    instrucciones
    acción que acerca al final del bucle
}

Por ejemplo:

int i = 0;

while (i < N)
{
    cout << i << endl;
    i++; // acción que acerca al final del bucle
}

En este caso:

• La condición de continuación es i < N.
• Las instrucciones son cout << i << endl;.
• La acción que acerca al final es i++;, porque hace que poco a poco i llegue a N.

En una función recursiva

En recursividad, esa repetición no la hace un while, sino la propia función llamándose a sí misma:

función recursiva(estado actual)
{
    si ya no se cumple la condición de continuación (caso base)
        terminar

    instrucciones
    acción que acerca al caso base (actualizar el estado actual)

    llamada recursiva(con el estado actual actualizado)
}

El ejemplo anterior se puede escribir de forma recursiva así:

void imprimir(int i, int N)
{
    if (i >= N) // caso base (la condición de continuación deja de cumplirse en el bucle)
        return;

    cout << i << endl; // instrucciones
    imprimir(i + 1, N); //  acción que acerca al caso base + llamada recursiva con el nuevo estado actual
}

Y se llamaría, por ejemplo, así:

imprimir(0, N);

En este caso:

• El caso base es i >= N, que indica cuándo debe terminar la función.
• Las instrucciones siguen siendo cout << i << endl;.
• La acción que acerca al final consiste en pasar de i a i + 1, cambiando el estado actual para la siguiente repetición.
• La repetición ya no la hace el while, sino la llamada recursiva.

Equivalencia entre ambas ideas

Si comparas ambas versiones:

• while (i < N) se transforma en comprobar si se ha alcanzado el caso base.
• El cuerpo del bucle se convierte en el cuerpo de la función recursiva.
• El i++ se convierte en actualizar el estado antes de la siguiente llamada.
• La repetición ya no depende de un bucle, sino de llamadas sucesivas a la función.

Esquema mental

Un bucle piensa así:

repetir mientras no haya terminado

Una función recursiva piensa así:

si ya he terminado, paro
si no, hago una parte del trabajo y me llamo otra vez

Aclaraciones.

• Este contenido no es la bibliografía completa de la asignatura, por lo tanto debes estudiar, aclarar y ampliar los conceptos que en ellas encuentres empleando los enlaces web y bibliografía recomendada que puedes consultar en la página web de la ficha de la asignatura y en la web propia de la asignatura.