# Programación en C++/Estructuras II

Editores: Oscar E. Palacios
| ← Punteros | Plantillas → |

# Introducción

Algunos autores comienzan por definir los conceptos de estructura de datos a raíz de estructuras conocidas como listas. En el mismo contexto, suele suceder que a dichas listas también se les conoce como secuencias y/o colecciones de datos. Hay que decir que dichos autores están (en parte) en lo correcto, ya que una lista (de cualquier tipo) es una estructura ideada con el propósito de albergar datos agrupados bajo un mismo nombre. Al respecto, podemos pensar que las listas son como arreglos de datos, es decir, para hacer una introducción al manejo y programación de listas encadenadas podemos tomar como punto de partida a los arreglos estáticos. Es así como en esta sección se descubrirá la forma de operación de tres tipos comunes de listas conocidas como: PILAS, COLAS Y DOBLE COLA (STACK, QUEUE, DQUEUE). En programación, el uso de listas es una práctica tan extendida que lenguajes tales como (por ejemplo) Java, Python y C++ soportan los mecanismos necesarios para trabajar con estructuras de: Vectores, Pilas, Colas, Listas, etc. En C++, los programadores que usen Dev-Cpp ( Bloodshed.software -Dev-C++ ) pueden aprovechar las ventajas que ofrecen las STL (Standard Templates Libraries) dentro de la cual se pueden encontrar plantillas para la manipulación de listas tales como: Vectores, Listas, Sets, Maps, etc. Por otro lado, los usuarios de Borland C++ ( Turbo C++ version 1.01 ) pueden hacer uso de la CLASSLIB, misma que posee las librerías para los propósitos mencionados.
Nota: En las siguientes secciones se presentarán siete programas, tres para simular listas basadas en arreglos estáticos y tres para simular listas por medio de enlaces dinámicos (punteros). En cuanto al material incluido se debe hacer las siguientes declaraciones:
* Puesto que el material es puramente didáctico, cada programa se escribe en un mismo archivo. La idea es no perder de vista el objetivo. Los entendidos sabrán que normalmente se deben escribir archivos de cabecera, archivos de implementación y archivos de prueba por separado.
* Para cada una de las clases creadas en los programas se han elegido nombres en inglés. La idea es que gran parte de la documentación e implementación referente a listas está en dicho idioma, así, se le da al estudiante la idea básica de como operar con las librerías soportadas por los compiladores Dev-Cpp, Borlan C++, y otros.
* Igual, se debe observar que los métodos de las clases tienen nombres en ingles, y que con el objetivo de establecer cierta estandarización todas las clases poseen los mismos métodos, aunque cada una de ellas implementa los mismos a su manera.

## Pilas o Stacks

Una pila es una estructura en donde cada elemento es insertado y retirado del tope de la misma, y debido a esto el comportamiento de un una pila se conoce como LIFO (último en entrar, primero en salir ).
Un ejemplo de pila o stack se puede observar en el mismo procesador, es decir, cada vez que en los programas aparece una llamada a una función el microprocesador guarda el estado de ciertos registros en un segmento de memoria conocido como Stack Segment, mismos que serán recuperados al regreso de la función.

### Pila en arreglo estático

En el programa que se verá en seguida, se simula el comportamiento de una estructura de pila. Aunque en el mismo se usa un arreglo estático de tamaño fijo se debe mencionar que normalmente las implementaciones hechas por fabricantes y/o terceras personas se basan en listas dinámicas o enlazadas.
Para la implementación de la clase Stack se han elegido los métodos:
El atributo SP de la clase Stack es el puntero de lectura/escritura, es decir, el SP indica la posición dentro de la pila en donde la función put insertará el siguiente dato, y la posición dentro de la pila de donde la función get leerá el siguiente dato.
Cada vez que put inserta un elemento el SP se decrementa.
Cada vez que get retira un elemento el SP se incrementa.
En el siguente ejemplo se analiza lo que sucede con el SP (puntero de pila) cuando se guardan en la pila uno por uno los caracteres 'A', 'B', 'C' y 'D'. Observe que al principio el SP es igual al tamaño de la pila.
Llenando la pila.
Vaciando la pila.
Nota: observe que al final la lista está vacía, y que dicho estado se debe a que el puntero está al final de la pila y no al hecho de borrar físicamente cada elemento de la pila.
Ejemplo: Pila basada en un arreglo estático

### Pila dinámica

En el siguiente programa se presenta una implementación de una estructura dinámica tipo pila o stack. Es importante hacer notar que, a diferencia de una pila basada en un arreglo estático, una pila enlazada dinámicamente no posee de forma natural el mecanismo de acceso por índices, en ese sentido, el programador puede crear los algoritmos necesarios para permitir tal comportamiento. En la clase que presentaremos en el ejemplo no se ha implementado el mecanismo de acceso por índices, ya que la misma se presenta como una alternativa para la simulación de una pila o stack.
Uno de los puntos más destacables en cuanto al uso de listas enlazadas dinámicamente es el hecho de crear estructuras conocidas como nodos. Un nodo es una especie de eslabón (similar al de una cadena de bicicleta), es decir, cada nodo se enlaza con otro a través de un puntero que apunta a una estructura del mismo tipo que el nodo. Por ejemplo, para crear una estructura de nodo para almacenar enteros y a la vez para apuntar a otro posible nodo podemos emplear la sintaxis:
observe que con la declaración anterior estamos creando el tipo estructurado nodo, mismo que posee a los miembros: data para guardar valores enteros, y siguiente para apuntar o enlazar a un supuesto siguiente nodo.
Ya que las listas dinámicas inicialmente se encuentran vacías, y más aún, una lista dinámica no posee una dirección establecida en tiempo de compilación ya que las dirección de memoria que ocupará cada uno de los elementos se establecerá en tiempo de ejecución, entonces cómo determinar la condición de vacío ?. En nuestro ejemplo usaremos un contador ( ITEMS ) que dicho sea de paso, si ITEMS = 0, entonces la lista está vacía. ( la condición de vacío también podría determinarse al verificar el SP, es decir, si el SP = NULL, significa que la lista no posee elementos ).
Al hacer un análisis previo de los eventos que acontecerán en la pila y su puntero de lectura y escritura (SP, que en esta ocasión es una estructura tipo nodo), se tiene lo siguiente:
    1) Al principio la lista está vacía, en ese caso el SP es igual a NULL y, en consecuencia, el puntero next también es NULL.
    2) Después de agregar el primer elemento la situación se vería así:
    3) Después de agregar otro elemento la situación se vería así:
Ejemplo: Pila basada en un arreglo dinámico

## Colas o Queues

Un ejemplo a citar de cola es el comportamiento del buffer del teclado.
Cuando en el teclado se oprime una tecla, el código del carácter ingresado es trasladado y depositado en una área de memoria intermedia conocida como "el buffer del teclado", para esto el microprocesador llama a una rutina específica. Luego, para leer el carácter depositado en el buffer existe otra función, es decir, hay una rutina para escribir y otra para leer los caracteres del buffer cada una de las cuales posee un puntero; uno para saber en donde dentro del buffer se escribirá el siguiente código y otro para saber de donde dentro del buffer se leerá el siguiente código.

### Cola en un arreglo estático

En el programa que se ve en seguida, se simula el comportamiento de una estructura de cola simple. Aunque en el mismo se usa un arreglo estático de tamaño fijo se debe mencionar que normalmente las implementaciones hechas por fabricantes y/o terceras personas se basan en listas dinámicas o dinámicamente enlazadas.
Para la implementación de la clase Queue se han elegido los métodos:
Es decir, la cola indica la posición dentro de la lista en donde la función put insertará el siguiente dato, y la cabeza indica la posición dentro de la lista de donde la función get leerá el siguiente dato.
En el siguiente ejemplo se analiza lo que sucede con la cola y la cabeza (punteros de escritura y de lectura de la Lista) cuando se guardan en la cola uno por uno los caracteres 'A', 'B', 'C' y 'D'. Observe que al principio: cola = cabeza = cero.
Llenando la cola.
Vaciando la cola.
Obsérvese que al final el cabeza apunta hacia el mismo elemento que la cola, es decir, la cola vuelve a estar vacía. Puesto que la cola que estamos proyectando reside en un arreglo estático los componentes del arreglo aún están dentro de la misma, salvo que para su recuperación se debería escribir otro método. En una cola dinámica (como se demostrará más adelante) los elementos retirados de la misma se eliminan de la memoria y podría no ser posible su recuperación posterior.
Nota: En el programa que aparece en seguida, al tipo de lista implementado por la clase Queue se le conoce como "lista circular" debido al comportamiento de sus punteros. Es decir si los métodos para escribir o leer detectan que el puntero correspondiente ha sobrepasado el tamaño máximo de elementos permitidos dentro de la cola, éste es puesto a cero.
Ejemplo: cola en un arreglo estático
Ejemplo: cola en un arreglo dinámico

## Colas de doble enlace

En el programa que se verá en seguida, se simula el comportamiento de una estructura de cola doble con base en un arreglo estático. En dicho programa se declara e implementa la clase SDQueue con los siguientes métodos:
Nota: observe que para los métodos put_front y get_front se hace uso de la función memmove, esto es necesario debido al hecho de que put_front tiene que mover una posición hacia atrás todos los elementos en la lista antes de insertar el componente indicado; por otro lado, la función get_front tiene que mover una posición hacia adelante a todos los elementos que le siguen al primer elemento.
Ejemplo: doble cola en un arreglo estático
Una cola doblemente encadenada es una estructuras en donde cada elemento puede ser insertado y recuperado por la parte del frente (cabeza) o por la parte de atrás (cola) de la lista. A diferencia de una cola sencilla, en donde solo se necesita un puntero a un siguiente elemento, la estructura del nodo para una doble cola debe poseer un puntero a un posible siguiente elemento y un puntero a otro posible anterior elemento. Por ejemplo, para crear una estructura de nodo con doble enlace para coleccionar números enteros podemos usar la sintaxis:
Gráficamente podemos imaginar la estructura anterior como:
En el programa que se verá en seguida, se simula el comportamiento de una estructura de cola de doble enlace. Para la implementación de la clase DDqueue en el programa se han elegido los métodos:
| ← Punteros | Arriba | Plantillas → |