Pilas (Stack)

Una pila o stack es una lista de elementos a la cual se le pueden insertar o extraer elementos solo por uno de sus extremos. Las pilas son estructuras de datos en las que la inserción de datos se hace por el frente y la eliminación de los datos de igual manera se hace por el frente, se elimina un dato por el mismo lado de donde se inserta; debido a esta característica de inserción y eliminación de datos también se le conoce como estructura LIFO (Last-In, First-Out: Ultimo en entrar, primero en salir).

Una representación analógica de una pila con objetos cotidianos, podría ser una pila de platos: En una mesa se colocan muchos platos uno encima del otro (una pila de platos), para colocar un nuevo plato en la pila se coloca el plato en la cima de la pila. Para sacar un plato de la pila es necesario sacar el plato que esta encima de la pila (el ultimo plato que fue colocado en la pila de platos).

(a) Una pila de libros. (b) Una pila de CD's. (c) Una pila de platos.

Al igual que en en la analogía de la pila de platos, en las pilas de datos la información se almacena de la misma manera y se inserta nueva información y se elimina un dato del mismo modo. Ahora, para comodidad del lector vamos a representar una pila de datos de la siguiente manera:

En la figura anterior podemos observar una pila de datos con 4 elementos apilados. Podrían ser 4 elementos de cualquier tipo, hablando de programación en Java podrían ser: int, string o incluso objetos.

Las pilas son estructuras de datos generalmente estáticas  ya que regularmente se crean usando la implementación de arreglos, y como se sabe: su tamaño no puede crecer en memoria en tiempo de ejecución  es decir, debemos establecer un tamaño fijo de elementos que se guardaran en la pila. Las Stack tienen 2 operaciones básicas: push (apilar, insertar) y pop (desapilar o eliminar), aunque se puede implementar más métodos a una pila para obtener alguna otra información que se requiera.

➮ Pila vacía y llena.

En la siguiente figura se representan 2 pilas de tamaño de 5 elementos: la primera pila esta vacía (Empty Stack) y la segunda pila esta llena (Full Stack).

En la figura anterior se representa una pila vacía  cuando no tiene ningún elemento insertado; y la pila llena cuando tiene la capacidad máxima de elementos que le hemos asignado para insertar. La pila vacía  no tiene ningún elemento, sin embargo tiene espacio para almacenar 5 elementos como máximo, como no tiene ningún elemento insertado no es posible eliminar algún elemento de la pila, sin embargo en Java si se intentara eliminar algún elemento de una pila vacía generaría un error de subdesordenamiento;  mientras la pila llena tiene espacio para almacenar 5 elementos, los cuales ya están insertados en la pila y ya no puede insertarse ningún elemento más; en Java si se intentara insertar otro elemento más a la pila arrojaría un error de desbordamiento.

➮ El tope de la pila.

El tope de la pila es el elemento que se encuentra en la cima de la pila. Aquí se representan 4 pilas con sus respectivos topes en diferente posición cada uno:

Cuando se crea una pila por medio de arreglos es importante recalcar que tiene las características del arreglo mismo (Un arreglo tiene un nombre propio y para acceder a cada uno de sus datos es necesario hacer mención del nombre de arreglo y del subíndice [posición] donde esta el dato que queremos obtener).

Para obtener información sobres el tope de una pila solo se tiene que escribir una instrucción donde hagamos referencia al nombre del arreglo y el subíndice que contenga el ultimo elemento insertado en la pila.

Por ejemplo, para la Pila A el tope es -1 debido a que es una pila vacía y no contiene ningún elemento insertado. En la Pila B el tope esta en el subíndice 2 y contiene el elemento [3 verde]. En la Stack C el tope esta situado en el subíndice 4 que contiene al elemento [5 rojo] y es el tamaño máximo de la pila. En la Pila D el tope esta en la posición 0 y contiene [1 Lila].

➮ Push & Pop.

Las operaciones básicas de la pila son: insertar un elemento (push) y quitar un elemento (pop).

PUSH: cuando se ejecuta la instrucción Push en una Pila, se ejecuta un algoritmo que inserta un elemento dentro de la pila de datos. Suponga que queremos insertar el numero 5 en una pila de números:

En la imagen anterior hay una pila de números de tamaño 5 (osea que se pueden insertar hasta 5 números). En la pila solo existen 4 números insertados (1,2,3 y 4) que ocupan desde la posición 0 hasta la posición 3 de la pila. Cuando ejecutamos la instrucción  Push(5); indicamos que se va a inserta el numero 5 en nuestra pila, de este modo el numero 5 que sera insertado quedara ocupando la posición 4 de nuestra pila.

POP: cuando se ejecuta la instrucción Pop en una pila se esta indicando que queremos borrar el elemento que se encuentre en la cima de nuestra pila:

Para este ejemplo se tiene una pila con 5 elementos insertados (1,2,3,4 y 5), estos van desde la posición 0 hasta la posición 4; Cuando indicamos una instrucción Pop() se elimina el ultimo elemento insertado (el elemento de la cima de la pila), de este modo el ultimo elemento insertado en la pila (el numero 5, en la posición 4) se elimina de la pila.

➮ Hagamos código.

Este programa esta orientado a objetos y cuenta con 2 clases: La clase Pila y la clase Principal. Es necesario mencionar que en esta ocasión programaremos una pila tradicional, una pila en su modo mas sencillo que solo insertara y eliminara datos en la pila; En la clase pila declararemos los atributos que contiene una pila y programaremos sus métodos a utilizar (push y pop); mientras que en la clase principal crearemos objetos de la clase pila y crearemos una sencilla interfaz en consola para poder utilizar la pila.

La clase Pila:
Primero creamos la clase Pila, que contendrá como atributos: MAXIMO: que es un numero entero el cual indica el tamaño de la pila (para este caso le asignaremos: 5); stack: sera un arreglo de enteros donde se almacenaran los elementos de la pila; y tope: que sera nuestro apuntador para saber cuando la pila esta llena o vacía o en que espacio del arreglo insertar un elemento, este deberá ser de tipo entero, a tope lo inicializaremos en -1, debido a que cuando iniciemos la pila esta sera vacía.

/**
 * Archivo: Pila.java
 * @author Anibal Clavel
 * www.buenasintencions.blogspot.mx
 */

//Inicia la clase pila.
public class Pila {
    
    //Declaracion de atributos a utilizar.
    private final int MAXIMO = 5;
    private int stack[];
    private int tope;
    
    //Constructor.
    public Pila(){
        stack = new int[MAXIMO];
        tope = -1;
    } //Fin del constructor.
    
    //Metodo para insertar.
    public void push(int numero){
        if(tope < MAXIMO-1){
            ++tope;
            stack[tope] = numero;
        }
        else
            System.out.println("Desbordamiento");
    } //Fin de Push.
    
    //Metodo para eliminar.
    public void pop(){
        if(tope >= 0)
            tope = tope-1;
        else
            System.out.println("Subdesordenamiento");
    } //Fin de Pop.
} //Fin de la clase Pila.

Analicemos nuestra clase Pila: De la linea 11 a la 13 se están declarando los atributos tal como lo mencionamos anteriormente. Posterior a eso armaremos nuestros métodos  que son solo 2 (push y pop), de tal modo que podamos realizar las operaciones de la pila con estos.

Constructor:

En la linea 16 iniciamos la codificación de nuestro constructor el cual de primer tarea inicializa nuestro arreglo stack y le asigna de tamaño lo que contiene MAXIMO, en otras palabras: se crea un arreglo stack de tamaño 5.

Push:

Bien, pasemos a nuestro método push para insertar un elemento en la pila, iniciamos en la linea 22, donde establecemos que es un método publico con public, después con void indicamos que es un método que no retorna nada, push es el nombre del método,  (int numero) es una variable que declaramos para ese método y que nos sirve como un parámetro de entrada (el dato que se insertara).

En la linea 23 iniciando el cuerpo del método (lo que el método realiza), hacemos una validación con un if para verificar si tope es menor que MAXIMO-1; recordemos que tope es un apuntador del arreglo stack, tope indica la posición o subíndice donde nos encontramos situados en el arreglo stack. MAXIMO es el tamaño de nuestro arreglo y este valor es 5 (para este ejemplo), entonces, al indicar MAXIMO-1 lo que hacemos realmente es indicar 5-1, esto resulta 4, ya que 4 es el ultimo subíndice de el arreglo stack. Entonces el algoritmo evalúa y si la condición resulta true entonces deducimos que el arreglo (la pila) tiene espacio e inserta el elemento que le proporcionemos. Para cuando sea la primera inserción de datos la pila estará vacía y el tope sera igual a -1, en la linea 24 tope hace un pre incremento de tal modo que tope obtenga el valor de 0. En la linea 25 insertamos en el arreglo en la posición tope (para entonces tope ya vale 0) ya que esta el la primera posición dentro de nuestro arreglo stack; para simplificar la linea 25 decimos que el elemento (el parámetro del método push) es insertado en el arreglo stack en la posición tope.

Cuando ya haya un elemento insertado se realiza la misma validación con if: "¿tope es menor que MAXIMO-1?" y arrojara un true, entonces se ejecutara nuevamente la linea 24 haciendo un pre incremento a tope y entonces tope ya valdrá 1 y en esa posición del arreglo se insertara el nuevo elemento, y así sucederá hasta que la pila este llena.

Si la validación con el if en la linea 23 resulta false, esto significara que tope ya tendrá el valor de 4 (cuatro es la ultima posición de nuestro arreglo stack) por tal motivo tope no sera menor que MAXIMO-1, entonces el método solo mandara un mensaje que indique que hay un desbordamiento porque la pila esta llena y ya no se pueden insertar mas elementos.

Pop:

Para el método pop que inicia en la linea 32, es un método publico que no retornará ningún valor, también es un método que no recibe ningún parámetro, debido a que no insertara nada y no necesitara ningún valor porque solo eliminará un dato de la pila. Ya en la linea 33 realizamos una validación con if para saber si la pila contiene elementos o esta vacía, de este modo la función del if es preguntar: "¿tope es mayor igual que 0?", si la respuesta es un true significara que la pila contiene elementos debido a que tope que es el apuntador del indice donde nos encontramos situados en nuestro arreglo stack es mayor o igual a 0 y la posición del arreglo sera valida, así que se pasara a la linea 34 donde a tope se le asignara el valor que tenga tope en ese momento menos 1 (tope-1). De este modo se hace una re-asignación del apuntador tope.

Ejemplo: si en la pila tenemos insertados 3 elementos, tope contendrá el valor de 2 que es el subíndice del arreglo stack donde estamos posicionados, cuando hagamos pop, a tope se le resta 1, de tal modo que después tope valdrá 1 y en ese subíndice del arreglo estaremos ubicados ahora, para cuando se haga un push con base en su algoritmo: tope incrementara en uno y volverá a tener el valor de 2 y en ese subíndice del arreglo se posicionara y sobrescribirá el nuevo valor en esa posición  de tal modo que borra el valor contenido ahí y escribe el nuevo valor a insertar.

Si en la linea 33 la validación del if arroja un false entonces entenderemos que el valor de tope es menor a 0 y tope tendrá el valor de -1, esto querrá decir que la pila esta vacía y que no hay datos para borrar, de tal modo que el método enviara un mensaje que informe que la pila esta vacía y que hay un error de subdesordenamiento.

La clase Principal:

Bien, una vez terminado la clase Pila, crearemos objetos de dicha clase en nuestra clase principal para hacer uso de sus métodos y así manipular una pila.

/**
 * Archivo: Principal.java
 * @author Anibal Clavel
 * www.buenasintencions.blogspot.mx
 */

import java.util.Scanner;

public class Principal {
    
    public static void main (String args[]){
        
        Pila pila = new Pila();
        Scanner scanner = new Scanner(System.in);
        String respuesta = "Si";
        int valor = 0;
        
        System.out.println("*** Bienvenido al programa Pila ***"
                + "\n\npila de enteros, tamaño: 5...\n"
                + "se ha creado la pila.\n");
        
        while(respuesta.equalsIgnoreCase("Si")){
            
            System.out.println("¿Que Operacion desea realizar?"
                    + "\n1. Push.\n2. Pop.\n");
            valor = scanner.nextInt();
            
            switch(valor){
                case 1:
                    System.out.println("Selecciono: Push");
                    System.out.println("Ingrese un numero a insertar: ");
                    valor = scanner.nextInt();
                    pila.push(valor);
                    System.out.println();
                break;
                case 2:
                    System.out.println("Selecciono: Pop");
                    pila.pop();
                    System.out.println();
                break;
                default:
                    System.out.println("Opcion no valida");
                    System.out.println();
            }
            
            System.out.println("¿Desea continuar?"
                    + "\nEscriba << si >> para continuar"
                    + "\nEscriba << no >> para salir");
            respuesta = scanner.next();
            System.out.println();
        }
    }
}

Este es un programa que contiene un menú con algunos adornos, usando un ciclo while, un switch, métodos de la clase String como el .equalsIgnorecase() a los cuales no les prestaremos mucha atención. Solo daremos una explicación muy general sobre esto: El while y el método .equalsIgnoreCase() los usamos para que el programa termine hasta que el usuario lo indique; El switch lo usamos como apoyo a un menú para que el usuario pueda elegir que operación (push o pop) desea realizar a su pila.

En este programa usamos la clase Scanner y sus métodos para obtener respuestas del usuario. Así que crearemos un objeto Scanner para usarlo a conveniencia del programa; También creamos un objeto de nuestra clase Pila (que es la que definimos anteriormente) y a nuestro objeto le asignamos el nombre de "pila" para poder usar sus métodos.

De la linea 24 a la 28 el programa preguntara al usuario que operación desea realizar, si el usuario responde insertando el valor de 1, entonces en la linea 29 se ejecutara el case 1 del switch y aquí enviamos un mensaje al usuario pidiendo que ingrese el numero que desea insertar en la pila, cuando el usuario introduce el valor haremos uso de nuestro objeto pila de la clase Pila y llamaremos a su método push (esto sucede en la linea 33) y le pasamos de parámetro el valor que el usuario nos ha proporcionado y de este modo se ejecutara el algoritmo del meto push que escribimos en la clase Pila y quedara insertado el valor en la pila.

De la linea 24 a la 28 si el programa hubiese recibido de respuesta el valor de 2, entonces se pasaría hasta la linea 36 donde entraría al case 2 del switch y ahí solo se hace de nuestro objeto pila de la clase Pila, quien manda a llamar a su método pop que no recibe parámetros  esto pasa en la linea 38, cuando el objeto pila manda a llamar al meto pop, este ejecuta el algoritmo que codificamos en la clase Pila y "elimina" el ultimo elemento que fue insertado.

Esto es todo el funcionamiento general de una pila de datos.