Pilas

Tal vez la palabra pila te haga pensar en ese pequeño utensilio de metal y químicos que insertas en ciertos aparatos portátiles y que te permite abastecerlos de energía eléctrica para poder utilizar dichos aparatos; tal vez el término pila te remita al concepto que se acopla exactamente al tema que vamos a tocar; es decir, pensarías en lo que obtienes como resultado de apilar un conjunto de elementos.

Cuando se realiza una pila de algo, los elementos que se van apilando se ponen uno encima del otro, lo que quiere decir que no hay otra forma de agregar un elemento a la pila más que por encima, ni por abajo, ni en medio y curiosamente, el único elemento que se pude tomar es el último que se puso en la pila; es decir, el de encima.

Para diferenciar lo que revisaremos en el tema, piensa lo siguiente: ¿qué pasaría si intentaras apilar un conjunto de elementos perecederos como las naranjas? Ahora,

¿qué pasaría si al tomar alguna, eligieras siempre la que agregaste al final? Llegará un momento en el que las primeras naranjas que pusiste en la pila se pudrirán. A diferencia de lo anterior, cuando hablamos de pilas desde el punto de vista de un TDA (tipo de datos abstractos), tenemos que pensar los escenarios en que podríamos utilizar este tipo de dato, ya que puede sernos útil en ciertas circunstancias, pero en otras no, como el ejemplo anterior, es decir en algunos casos tenemos que ajustarnos a la realidad sin embargo en la programación por el momento eso no será un obstáculo. 

Definición del tipo de dato abstracto pila

Una pila o stack es un tipo especial de lista en la que la inserción y borrado de nuevos elementos se realiza sólo por un extremo que se denomina cima o tope también conocido como top.

Una pila es una colección ordenada de elementos en la cual, en un extremo, pueden insertarse o retirarse otros elementos, colocados por la parte superior de la pila. Una pila permite la inserción y eliminación de elementos, por lo que realmente es un objeto dinámico que cambia constantemente. 

Es importante notar que los elementos que se agregan por un extremo de la lista o arreglo (pensando en un arreglo, como una lista de elementos), se sacan por el mismo extremo; es decir, el último elemento que se agrega a la lista, es el primer elemento que se puede sacar y ningún otro más, por eso a este tipo de estructuras, se les conoce como LIFO (last-in, first-out o última entrada - primera salida)

Un ejemplo de pila o stack se puede observar en el mismo procesador de un sistema de cómputo; 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.

Elementos de una pila, a continuación en este vídeo se muestra de manera teórica los métodos que se utilizan en la clase Pila. 

Programación de la clase Pila.

Listas

En la vida cotidiana utilizas las listas para organizar una serie de actividades o pasos que son consecutivos el uno del otro y de esa manera puedes organizar también tus ideas, abordando los problemas de manera secuencial y sin olvidar ningún detalle. Un ejemplo de ello pueden ser los pasos que tenemos que seguir para cocinar un pastel, las actividades que tienes que realizar durante el día o, incluso, sólo pueden ser los elementos de un conjunto, sin algún orden particular, como la lista de compras del súper. Dos detalles importantes a tomar en cuenta en una lista, es que en ella estarán todos los datos que vas a necesitar para resolver un problema en cierto contexto y que a un dato de la lista le sigue otro, pudiendo ubicar cada uno de esos datos por su posición en la lista como: el primero, el último, el siguiente o el anterior.

Definición del tipo de dato abstracto lista

Una lista lineal es un conjunto de elementos de un tipo dado, aunque pueden variar en número. Los elementos de una lista se almacenan normalmente de manera contigua, es decir, un elemento detrás de otro en posiciones de la memoria (Informática, 1998).

Una lista enlazada es una estructura de datos fundamental que se utiliza para implementar otras estructuras de datos como fue el caso de las pilas, las colas simples y las bicolas. Éstas cuentan con una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o apuntadores al nodo anterior o posterior.

Delante se muestra la forma en que se puede representar una lista enlazada unidireccional, observa la siguiente imagen.

Figura. Representación de una lista enlazada unidireccional

Fuente: autoría propia, (2020)

Definición de las operaciones sobre listas

Las operaciones que se tienen en una lista son:

• Insert() (Agregar un elemento a la lista) 
• delete() (Quitar un elemento de la lista)

Otras operaciones que son menos relevantes, pero que pueden utilizarse en una lista son:

• isEmpty() (Evalúa si la pila está vacía o no)
• display() (Muestra los elementos de la pila, desde el inicio al final -NULL-)) size() (Muestra el tamaño actual de la pila)

Definición

La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan

de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del nodo

siguiente vale NULO (NULL).

En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un

puntero a ese primer nodo y llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese

único puntero podemos acceder a toda la lista.

Cuando el puntero que usamos para acceder a la lista vale NULO, diremos que la lista está vacía.

El nodo típico para construir listas tiene esta forma:

struct nodo {

int dato;

nodo *siguiente;

}

Declaraciones de tipos para manejar listas

Normalmente se definen varios tipos que facilitan el manejo de las listas, la declaración de tipos puede

tener una forma parecida a esta:

struct nodo {

int dato;

nodo *siguiente;

}

Declaración de la Clase Nodo en java, en este caso como estamos trabajando tanto en pilas como en colas con datos de tipos String por tal motivo listas también trabajaremos con String para el dato o elemento nuevo a insertar. 

Lista es el tipo para declarar listas, como puede verse, un puntero a un nodo y una lista son la misma

cosa. En realidad, cualquier puntero a un nodo es una lista, cuyo primer elemento es el nodo apuntado.

Operaciones básicas con listas

Con las listas tendremos unas operaciones básicas que se pueden realizar:

• Agregar o insertar elementos.
• Buscar o localizar elementos.
• Borrar elementos.
• Moverse a través de una lista, anterior, siguiente, primero.

Cada una de estas operaciones tendrá varios casos especiales, por ejemplo, no será lo mismo insertar

un nodo en una lista vacía, o al principio de una lista no vacía, o la final, o en una posición intermedia.

Insertar elementos en una lista abierta

Algunos casos de inserción en una lista se verán a continuación. Insertar un elemento en una lista vacía. Este es uno de los casos más sencillo. Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero a la lista valdrá NULO:

Fuente: autoría propia (2020)

El proceso es muy simple, bastará con que:

1. nodo.siguiente apunte a NULO.

2. Lista apunte a nodo.

Figura. Insertar un elemento en la primera posición de una lista

Podemos considerar el caso anterior como un caso particular de éste, la única diferencia es que en el caso anterior la lista es una lista vacía, pero siempre podemos, y debemos considerar una lista vacía como una lista.

De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una lista, en este caso no vacía:

A continuación se muestra la Clase Nodo lista para insertar por el principio y por final

Programando la clase Lista, en la cual se incluye un método constructor que nos permite inicializar nuestros punteros inicio y fin, además de dos métodos el primero para agregarAlInicio(String elemento) y el segundo mostrarLista()

Implementación de una lista