Pilas

Las palabras que refieren a la programación o a la estructura de datos, están más que relacionadas a situaciones presentes en nuestra vida diaria.

Las pilas, en un sentido general, manejan lo siguiente: "El último elemento agregado, es el primero en ser retirado".

Para entender este concepto, se hace referencia a la filosofía LIFO = por sus siglas en inglés (Last Input, First Output).

Como se muestra en esta pila de libros y supermercado (figura 1.1)

(figura 1.1)

Además de ser una estructura lineal de datos, en una pila se pueden agregar o quitar elementos, únicamente por uno de los dos extremos, mientras que estos elementos que la integran son limitados, a lo que conocemos como Tope Máximo.

Las pilas indican su posición mediante un apuntador que muestra el último elemento en una pila.

Una pila maneja atributos y métodos para llevar a cabo sus procesos de resolución y entendimiento; los atributos son la colección de elementos y el tope, que es nuestro límite; los métodos integran todas las operaciones posibles, que son PUSH y POP.

PUSH, es una operación que nos ayuda a agregar elementos (su apuntador nos indica incremento).

POP, para esta operación los elementos son extraídos (el apuntador nos indica decremento).

Como se ve a continuación: 

Cada pila y su operación (imagen 1.2)

(figura 1.2)

A pesar de declarar ciertos puntos para las pilas, tanto en sus operaciones, como en lo que deben contener, existen posibles errores en ellas conocidos como, OVERFLOW UNDERFLOW. 

OVERFLOW, este error existe cuando se intenta introducir más elementos a una pila llena.

UNDERFLOW,  para este error lo que se intenta es extraer elementos de una pila vacía.

Colas.

Para comprender primero en qué consisten la colas, hablamos de lo siguiente;

El tema de Colas, para la estructura de datos, también esta presente en casos típicos de nuestra vida, por ello se dice que colas es, "El primer elemento agregado, es el primero en ser retirado"

En este ejemplo se muestra cómo podemos ver el tema de "Colas" en nuestro entorno.(imagen 1.3)

(figura 1.3)

Al igual que las pilas, las colas utilizan una filosofía para relacionar y entender su concepto; ellas hacen uso de la filosofía FIFO = (First Input, First Output)

Una cola utiliza un vector para poder ser implementada y el uso de dos variables que son, FRENTE y FIN

El FRENTE nos ayuda a indicar la posición del primer elemento en una cola, el cual se considera próximo en salir.

FIN indica la posición del último elemento en una cola, para continuar con el proceso, los elementos que vayan llegando, se irán agregando.

En las colas también existen posibles operaciones a llevar acabo; en un sentido general, insertar, eliminar, vacía y llena. como se muestra en la figura 1.4.

Insertar: se encarga de almacenar al final de la cola el elemento que es recibido.

Eliminar: saca el elemento de la cola que se encuentra al frente.

Vacía: regresa un valor indicando si la cola tiene o no elementos (indicación por medio de true y false).

Llena: regresa un valor indicando si la cola tiene espacio disponible para insertar nuevos elementos (la indicación es por medio de true y false).

(figura 1.4)

Existen diferentes tipos de colas, como lo son; las colas dobles y circulares.

 En una cola doble, se permite la inserción y eliminación de elementos desde ambos extremos.(figura 1.5)

(figura 1.5)

En una cola circular, encontramos los elementos, como lo dice su nombre, de forma circular, aquí cada elemento tiene un sucesor y un predecesor.

Para poder añadir o eliminar algún elemento, es necesario hacerlo desde la cabeza.(figura 1.6)

(figura 1.6)

Listas.

Otro tipo lineal conocido son las Listas, su  estructura son datos secuenciales.

Son estructuras lineales donde cada elemento de una lista excepto el primero tiene un único predecesor y cada elemento de la lista excepto el último tiene un sucesor. 

En una lista, para la solución de las mismas, es necesario el uso de operaciones, como las siguientes:

Lista Vacía ( ); en esta operación, devuelve verdadero si la lisa esta vacía, en caso de no estarlo devolverá falso.

Insertar (x, y); aquí el elemento x, se inserta hasta la ultima posición y de la lista.

Buscar (x); en la búsqueda, se devuelve la posición en la lista del elemento x. Y por ultimo.

Eliminar (x); encargado de eliminar de la lista nuestro elemento, en este caso x.

Las listas en las cuales nos basaremos de acuerdo a su estructura se clasifican en:

-Listas simples.

-Listas dobles.

  *Listas dobles lineales.

   *Listas dobles circulares.

-Listas Circulares.

   *Multilistas.

Listas simples. 

Las listas simples enlazadas se puede entender que están compuestas por una serie de nodos las cuales están interconectadas de manera secuencial, un dato con otro, únicamente se puede conocer a su sucesor, cuando una lista está vacía su valor es nulo o null. 

Como se muestra en la figura 1.7 en la cual se representa un ejemplo de lista simplemente enlazada que almacena apellidos:

(figura 1.7)

Listas dobles.

Este tipo de lista son series de nodos ,donde cada nodo tiene 2 enlaces (denominado doble enlace)  uno apuntando al nodo siguiente o predecesor y otro al anterior o a su sucesor, por medio de estos enlaces se podrá avanzar o retroceder a través de la lista.
como se puede apreciar en la figura 1.8

Listas dobles lineales.

En este tipo de lista cada nodo tiene 2 punteros un hacia el nodo siguiente, y otro hacia el nodo anterior. (imagen 1.9)

(imagen 1.9)

Listas dobles Circulares.

En una lista doblemente circular se tiene estructuralmente, cada nodo tiene dos enlaces, similares a los de la lista doble, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero.

Como se había mencionado la lista circular ,tiene cierta similitud a la lista doble lineal,la diferencia es que el primer nodo apunta al ultimo y viceversa. ver figura 2.0

(figura 2.0)

Listas Circulares

  Las listas circulares tienen como característica de que el último elemento de la misma apunta al primero.  

En la siguiente figura 2.1 se hace una representación gráfica de listas circulares.

(figura 2.1)

Multilistas

Las multilistas es un método de búsqueda que nos permite acceder de manera ordenada a la información a través de campos claves.

Las multilistas nos permiten llegar a un registro por diferentes caminos. El camino lo determina el campo clave sobre el cual se va hacer la búsqueda. A continuación se presenta un ejemplo de multilistas. 

Nombre	Profesión	Categoria
Ángel	Químico	1
Carlos	Informático	2
Marcos	Matemático	3
José	Físico	1
Roberto	Abogado	2
Alejandro	Informático	3

En este caso, la información de cada individuo puede acceder por medio de su profesión y por medio de su categoría , que son los atributos que permiten realizar búsqueda directa en el archivo. Como puede verse en la siguiente figura 2.2 , se tiene una lista por profesión y una por categoría.

En general las multilistas son recomendables cuando la búsqueda se hace sobre un solo atributo. En caso de necesitarse una combinación de atributos es preferible usar listas invertidas.