Listado completo de tutoriales

71 - Colecciones: Stack


Veremos con una serie de ejemplo los métodos disponibles en la clase Stack.

También se las llama listas LIFO (Last In First Out - último en entrar primero en salir)

Problema

Definir un objeto de la clase Stack y llamar a los métodos principales.

Programa:

import java.util.Stack;

public class PruebaStack {

    public static void main(String[] args) {
        Stack<String> pila1 = new Stack<String>();
        System.out.println("Insertamos tres elementos en la pila: juan, ana y luis");
        pila1.push("juan");
        pila1.push("ana");
        pila1.push("luis");
        System.out.println("Cantidad de elementos en la pila:" + pila1.size());
        System.out.println("Extraemos un elemento de la pila:" + pila1.pop());
        System.out.println("Cantidad de elementos en la pila:" + pila1.size());
        System.out.println("Consultamos el primer elemento de la pila sin extraerlo:" + pila1.peek());
        System.out.println("Cantidad de elementos en la pila:" + pila1.size());
        System.out.println("Extraemos uno a un cada elemento de la pila mientras no este vacía:");
        while (!pila1.isEmpty())
            System.out.print(pila1.pop() + "-");
        System.out.println();

        Stack<Integer> pila2 = new Stack<Integer>();
        pila2.push(70);
        pila2.push(120);
        pila2.push(6);
        System.out.println("Imprimimos la pila de enteros");
        for (Integer elemento : pila2)
            System.out.print(elemento + "-");
        System.out.println();
        System.out.println("Borramos toda la pila");
        pila2.clear();
        System.out.println("Cantidad de elementos en la pila de enteros:" + pila2.size());
    }
}

Para poder hacer uso de la clase Stack debemos importarla del paquete 'java.util' ya que no se encuentra en el paquete 'java.lang' que se importa en forma automática:

import java.util.Stack;

Creamos un objeto de la clase Stack indicando que se almacenarán objetos de la clase String:

        Stack<String> pila1 = new Stack<String>();

Para agregar elementos en la pila lo hacemos a través del método push:

        pila1.push("juan");
        pila1.push("ana");
        pila1.push("luis");

Para conocer la cantidad de elementos almacenados en la pila llamamos al método size:

        System.out.println("Cantidad de elementos en la pila:" + pila1.size());

Para extraer un elementos de la pila disponemos del método pop:

        System.out.println("Extraemos un elemento de la pila:" + pila1.pop());

En cambio si queremos conocer el valor que hay en el primer elemento de la pila pero sin eliminarlo hacemos uso del método peek:

    System.out.println("Consultamos el primer elemento de la pila sin extraerlo:" + pila1.peek());

El método isEmpty retorna true si la lista está vacía o false en caso contrario:

        while (!pila1.isEmpty())
            System.out.print(pila1.pop() + "-");

Podemos utilizar un for para recorrer todos los elementos de la colección de tipo Stack con la siguiente sintaxis (no se eliminan los elementos de la pila):

        System.out.println("Imprimimos la pila de enteros");
        for (Integer elemento : pila2)
            System.out.print(elemento + "-");

Finalmente podemos eliminar todos los elementos de la pila mediante el método clear:

        pila2.clear();

Cuando vimos como implementar desde cero una pila en Java desarrollamos un problema de aplicación. Lo volveremos a codificar pero ahora utilizando la clase Stack en lugar de la clase Pila implementada desde cero.

Problema

Todo compilador o intérprete de un lenguaje tiene un módulo dedicado a analizar si una expresión está correctamente codificada, es decir que los paréntesis estén abiertos y cerrados en un orden lógico y bien balanceados.

Se debe desarrollar una clase que tenga las siguientes responsabilidades (clase Formula):

- Ingresar una fórmula que contenga paréntesis, corchetes y llaves.
- Validar que los ( ) [] y {} estén correctamente balanceados. 

Para la solución de este problema la clase formula empleará la clase Stack.

Veamos como nos puede ayudar el empleo de una pila para solucionar este problema.
Primero cargaremos la fórmula en un JTextField.

Ejemplo de fórmula: (2+[3-12]*{8/3})

El algoritmo de validación es el siguiente:

Analizamos caracter a caracter la presencia de los paréntesis, corchetes y llaves.
Si vienen símbolos de apertura los almacenamos en la pila.
Si vienen símbolos de cerrado extraemos de la pila y verificamos si está el mismo símbolo pero de apertura: en caso negativo podemos inferir que la fórmula no está correctamente balanceada.
Si al finalizar el análisis del último caracter de la fórmula la pila está vacía podemos concluir que está correctamente balanceada.

Ejemplos de fórmulas no balanceadas:

}(2+[3-12]*{8/3})
Incorrecta: llega una } de cerrado y la pila está vacía.
{[2+4}]
Incorrecta: llega una llave } y en el tope de la pila hay un corchete [.
{[2+4]
Incorrecta: al finalizar el análisis del último caracter en la pila queda pendiente una llave {.
Pila

Programa:


import javax.swing.*;
import java.awt.event.*;
import java.util.Stack;

public class Formula extends JFrame implements ActionListener {
    private JTextField tf1;
    private JButton boton1;

    public Formula() {
        setLayout(null);
        tf1 = new JTextField("{2*(4-5)-{3*4}-[4-5]}");
        tf1.setBounds(10, 10, 230, 30);
        add(tf1);
        boton1 = new JButton("Verificar fórmula.");
        boton1.setBounds(10, 70, 180, 30);
        add(boton1);
        boton1.addActionListener(this);
    }

    public void actionPerformed(ActionEvent e) {
        if (e.getSource() == boton1) {
            if (balanceada()) {
                setTitle("Está correctamente balanceada.");
            } else {
                setTitle("No está correctamente balanceada.");
            }
        }
    }

    public boolean balanceada() {
        Stack<Character> pila1 = new Stack<Character>();
        String cadena = tf1.getText();
        for (int f = 0; f < cadena.length(); f++)
            if (cadena.charAt(f) == '(' || cadena.charAt(f) == '[' || cadena.charAt(f) == '{')
                pila1.push(cadena.charAt(f));
            else if (cadena.charAt(f) == ')' || cadena.charAt(f) == ']' || cadena.charAt(f) == '}') {
                if (pila1.isEmpty())
                    return false;
                else if (cadena.charAt(f) == ')' && pila1.pop() != '(')
                    return false;
                else if (cadena.charAt(f) == ']' && pila1.pop() != '[')
                    return false;
                else if (cadena.charAt(f) == '}' && pila1.pop() != '{')
                    return false;
            }
        if (pila1.isEmpty())
            return true;
        else
            return false;
    }

    public static void main(String[] ar) {
        Formula formula1 = new Formula();
        formula1.setBounds(0, 0, 400, 160);
        formula1.setVisible(true);
        formula1.setDefaultCloseOperation(EXIT_ON_CLOSE);
    }

}

Lo primero que hacemos es importar la clase Stack del paquete 'java.util':

import java.util.Stack;

En el método balanceada creamos un objeto de la clase 'Stack' e indicamos que almacenamos objetos de la clase Character (recordemos que con clases genéricas no podemos pasar tipos de datos primitivos como char):

        Stack<Character> pila1 = new Stack<Character>();

Dentro de un for analizamos caracter a caracter la formula ingresada por el operador:

        for (int f = 0; f < cadena.length(); f++)

Si se trata de un caracter de paréntesis, corchetes o llaves de apertura procedemos a insertarlo en la pila:

            if (cadena.charAt(f) == '(' || cadena.charAt(f) == '[' || cadena.charAt(f) == '{')
                pila1.push(cadena.charAt(f));

Si se trata de un paréntesis, corchetes o llaves de cerrado verificamos primero que la pila no esté vacía. Si la pila está vacía podemos decir que la formula no tiene los símbolos correctamente balanceados:

                if (pila1.isEmpty())
                    return false;

Si la pila no está vacía debemos controlar que el elemento de la pila coincida con el mismo elemento de cerrado, si no coincide no esta balanceada la formula:

                else if (cadena.charAt(f) == ')' && pila1.pop() != '(')
                    return false;
                else if (cadena.charAt(f) == ']' && pila1.pop() != '[')
                    return false;
                else if (cadena.charAt(f) == '}' && pila1.pop() != '{')
                    return false;

Cuando se sale del for si la pila no está vacía también significa que no está correctamente balanceados los paréntesis, corchetes y llaves:

        if (pila1.isEmpty())
            return true;
        else
            return false;

Con esto terminamos la codificación del mismo problema resuelto en conceptos anteriores, pero utilizando la clase Stack en lugar de implementar nosotros mismos la clase Pila.

Como programadores debemos conocer tanto las librería que nos proporciona el lenguaje para la administración de estructuras dinámicas como los algoritmos que las implementan a esas estructuras que nos pueden ser muy útiles cuando las clases del API de Java no se adaptan a nuestras necesidades.


Retornar