Estructura Dinámicas pilas, colas, y listas.

Una pila:
 
Es una estructura de datos homogénea (elementos del mismo tipo), secuencial y de tamaño variable. Sólo es posible un modo de acceso a esta estructura: a través de la cabeza de la pila. De este modo podemos añadir un elemento a la cabeza de la pila o extraer un elemento de la cabeza de la pila. Debido a que las operaciones de extracción e inserción se realizan por el mismo extremo, el último elemento en ser añadido será el primero en ser extraído; por ello a estas estructuras se las conoce con el nombre de LIFO ( last-in, first-out; último en entrar, primero en salir). 

Un ejemplo típico de pila lo constituye un montón de platos: Cuando se quiere introducir un nuevo plato, éste se coloca en la posición más accesible, encima del último plato. Cuando se toma un plato, éste se extrae, igualmente, del punto más accesible, el último que se ha introducido. O, si somos más estrictos, otro ejemplo sería una caja llena de libros. Sólo podemos ver cuál es el libro que está más arriba en la caja, y si ponemos o tomamos un libro, sólo podremos actuar sobre este primer libro. No podemos siquiera saber el número total de libros guardados en la pila. Sólo sabremos el número de elementos de la pila de libros si previamente los sacamos hasta vaciar la caja. 

 

Operaciones con Pila Asociadas con la estructura pila existen una serie de operaciones necesarias para su manipulación. Éstas son: Iniciación de la estructura: - Crear la pila (CrearPila): La operación de creación de la pila inicia la pila como vacía. Operaciones para añadir y eliminar información: - Añadir elementos en la cima (Apilar): pondrá un nuevo elemento en la parte superior de la pila. Eliminar elementos de la cima (Desapilar): lo que hará será devolver el elemento superior de la cima y eliminarlo de la pila. 

Operaciones

 

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

• Crear: se crea la pila vacía. (constructor)
• Tamaño: regresa el numero de elementos de la pila. (size)
• Apilar: se añade un elemento a la pila.(push)
• Desapilar: se elimina el elemento frontal de la pila.(pop)
• Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
• Vacía: devuelve cierto si la pila está vacía o falso en caso contrario (empty).

 Pila como tipo abstracto de datos:

A modo de resumen tipo 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. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primera placa es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas. A medida que la placa superior se elimina de la pila, la segunda placa se convierte en la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: En primer lugar la última salida es un principio, la segunda es que el contenido de la pila está oculto. Sólo la placa de la parte superior es visible, por lo que para ver lo que hay en la tercera placa, el primer y segundo platos tendrán que ser retirados.

Ejemplo en c++:

#ifndef PILA
#define PILA // define la pila
 
 
template <class T>
class Pila {
 
private:
    struct Nodo {
        T elemento;
        Nodo* siguiente;  // coloca el nodo en la segunda posicion
    }* ultimo;
    unsigned int elementos;
 
public:
    Pila() {
        elementos = 0;
    }
 
    ~Pila() {
        while (elementos != 0) pop();
    }
 
    void push(const T& elem) {
        Nodo* aux = new Nodo;
        aux->elemento = elem;
        aux->siguiente = ultimo;
        ultimo = aux;
        ++elementos;
    }
 
    void pop() {
        Nodo* aux = ultimo;
        ultimo = ultimo->siguiente;
        delete aux;
        --elementos;
    }
 
    T cima() const {
        return ultimo->elemento;
    }
 
    bool vacia() const {
        return elementos == 0;
    }
 
    unsigned int altura() const {
        return elementos;
    }
 
};
 
 
#endif

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. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.

Ejemplos de colas en la vida real serían:

 

Personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

 Operaciones Básicas:

• Crear: se crea la cola vacía.
• Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró. 

Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

Ejemplo en  c++:

#ifndef COLA
  #define COLA // Define la cola
  template <class T>
  class Cola{
      private:
        struct Nodo{
            T elemento;
            struct Nodo* siguiente;  // coloca el nodo en la segunda posición
        }* primero;
        struct Nodo* ultimo;
        unsigned int elementos;
      public:
        Cola(){
            elementos = 0;
        }
        ~Cola(){
            while (elementos != 0) pop();
        }
        void push(const T& elem){
            Nodo* aux = new Nodo;
            aux->elemento = elem;
            if (elementos == 0) primero = aux;
            else ultimo->siguiente = aux;
            ultimo = aux;
            ++elementos;
        }
        void pop(){
            Nodo* aux = primero;
            primero = primero->siguiente;
            delete aux;
            --elementos;
        }
        T consultar() const{
            return primero->elemento;
        }
        bool vacia() const{
            return elementos == 0;
        }
        unsigned int size() const{
            return elementos;
        }
    };
    #endif

  

Listas enlazadas lineales

Listas simples enlazadas

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Lista Doblemente Enlazada

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros  

Listas enlazadas circulares simples

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo. 

Lista Enlazada Doblemente Circular

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.

Nodos Centinelas

A veces las listas enlazadas tienen un nodo centinela (también llamado falso nodo o nodo ficticio) al principio o al final de la lista, el cual no es usado para guardar datos. Su propósito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un “primer y último” nodo.

Aplicaciones de las listas enlazadas

Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.

El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta practica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.

A veces, las listas enlazadas son usadas para implementar vectores asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar éstas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer ésta serie de datos.

Ejemplo:

#include <stdio.h>   /* for printf */
#include <stdlib.h>  /* for malloc */
 
typedef struct ns {
        int data;
        struct ns *next;
} node;
 
node *list_add(node **p, int i) {
    /* algunos compiladores no requieren un casting del valor del retorno para malloc  */
    node *n = (node *)malloc(sizeof(node));
    if (n == NULL)
        return NULL;
    n->next = *p;                                                                            
    *p = n;
    n->data = i;
    return n;
}
 
void list_remove(node **p) { /* borrar cabeza*/
    if (*p != NULL) {
        node *n = *p;
        *p = (*p)->next;
        free(n);
    }
}
 
node **list_search(node **n, int i) {
    while (*n != NULL) {
        if ((*n)->data == i) {
            return n;
        }
        n = &(*n)->next;
    }
    return NULL;
}
 
void list_print(node *n) {
    if (n == NULL) {
        printf("lista esta vacía\n");
    }
    while (n != NULL) {
        printf("print %p %p %d\n", n, n->next, n->data);
        n = n->next;
    }
}
 
int main(void) {
    node *n = NULL;
 
    list_add(&n, 0); /* lista: 0 */
    list_add(&n, 1); /* lista: 1 0 */
    list_add(&n, 2); /* lista: 2 1 0 */
    list_add(&n, 3); /* lista: 3 2 1 0 */
    list_add(&n, 4); /* lista: 4 3 2 1 0 */
    list_print(n);
    list_remove(&n);            /* borrar primero(4) */
    list_remove(&n->next);      /* borrar nuevo segundo (2) */
    list_remove(list_search(&n, 1)); /* eliminar la celda que contiene el 1 (primera) */
    list_remove(&n->next);      /* eliminar segundo nodo del final(0)*/
    list_remove(&n);            /* eliminar ultimo nodo (3) */
    list_print(n);
 
    return 0;
}