Definiciones, Mapa Conceptual de Pilas y tratamiento de expresiones.

            
Introducción:

Este blog impartirá conocimientos enfocados en Pilas y colas, con sus definiciones básicas y algunos ejemplos necesarios y fáciles para su entendimiento. De manera ordenada este blog explicará la manera en la que funcionan estos dos temas de estructura de datos.

Pilas.

Definición:

En estructura de datos linealmente los elementos pueden ser añadidos (conocido como PUSH) o removidos (conocido como POP) solamente por un extremo.

Una de sus características principales es que trabaja con la filosofía LIFO (Last In-First Out). Primer elemento en entrar es el primer elemento en salir.

Operaciones básicas:

-       Push: Agrega un elemento a la pila en el extremo “tope”. “public void push(int elem)”

-       Pop: Remueve el elemento de la pila que se encuentra en el extremo “tope”. “public int pop()”

-       Vacia: Indica si la pila contiene o no contiene elementos. “public boolean vacia()”

-       Llena: Indica la posibilidad de agregar o no más elementos a la pila. “public boolean llena()”

Figura 1. Demostración de funcionamiento de pilas. 

Figura 2. Mapa conceptual de estructura de pilas.

Tratamiento de expresiones.

Notación Infija: Los operadores aparecen en medio de los operandos.

Ejemplos:

                               A - 1

                               E / F

                               A * C

                               A + B + C

                               A + B – C

Notación Prefija: Los operadores aparecen antes de los operandos.

Ejemplos:

                               - A1

                               /EF

                               *AC

                               +AB+C

                               +AB-C

Notación Posfija: Los operadores aparecen al final de los operandos.

Ejemplos:

                               A1-

                               EF/

                               AC*

                               AB+C+

                               AB+C-                  

Código de ejemplo de Pila.

Clase estudiante

class Estudiante {
    
    private String nombre;
    private int numeroMaterias;

    public Estudiante(String nombre, int numeroMaterias) {
        this.nombre = nombre;
        this.numeroMaterias = numeroMaterias;
    }

    public String getNombre() {
        return nombre;
    }

    public int getNumeroMaterias() {
        return numeroMaterias;
    }

    public void setNombre(String nombre) {
        this.nombre = nombre;
    }

    public void setNumeroMaterias(int numeroMaterias) {
        this.numeroMaterias = numeroMaterias;
    }
    
    
}

Clase Nodo

public class Nodo {
    
    private Estudiante datos;
    private Nodo anterior;
    private Nodo siguiente;

    public Nodo(Estudiante datos, Nodo anterior, Nodo siguiente) {
        this.datos = datos;
        this.anterior = anterior;
        this.siguiente = siguiente;
    }

    public Estudiante getDatos() {
        return datos;
    }

    public Nodo getAnterior() {
        return anterior;
    }

    public Nodo getSiguiente() {
        return siguiente;
    }

    public void setDatos(Estudiante datos) {
        this.datos = datos;
    }

    public void setAnterior(Nodo anterior) {
        this.anterior = anterior;
    }

    public void setSiguiente(Nodo siguiente) {
        this.siguiente = siguiente;
    }
           
}

Clase Pila

public class Pila {
    
    private Nodo cima;
    
    public Pila(){
        cima=null;
    }
    
    //agregarInicio
    public void push(Estudiante x, int num){
        
        if(num<=8){
            
        Nodo nuevo=new Nodo (x, null, cima);
        if(cima!=null){
            cima.setAnterior(nuevo);
        }
        cima=nuevo;
    }
        //System.out.println("ERROR: Maximo puede coger 8 materias");
      }
    
    //Quitar INICIO
    public Estudiante pop(){
        if(cima==null){
            System.out.println("ERROR: Maximo puede coger 8 materias. La pila esta vacia");
            return null;
        }
        else if(cima.getSiguiente()==null){
            Nodo aux=cima;
            cima=null;
            return aux.getDatos();
        }else{
            Nodo aux=cima;
            cima=cima.getSiguiente();
            cima.setAnterior(null);
            aux.setSiguiente(null);
            return aux.getDatos();
        }
    }
    
public Nodo Imprimir(Nodo aux){
    if(aux!=null){
        System.out.println("Nombre: "+aux.getDatos().getNombre()+" Numero de materias: "+aux.getDatos().getNumeroMaterias());
        aux=aux.getSiguiente();
        Imprimir(aux);
    }
    return aux;
}

public void Imprimir(){
    Nodo aux=cima;
    Imprimir(aux);
}

}

Clase Principal

import java.util.Scanner;

public class Principal {

  
    public static void main(String[] args) {
           
            Pila pA=new Pila();
            
            pA.push(new Estudiante("Juan",5),5);
            pA.push(new Estudiante("Ana",7),7);
            pA.push(new Estudiante("Pepe",3),3);
            pA.Imprimir();
            Estudiante r=pA.pop(); 
                       
                    
            if(r!=null){
                  System.out.println("Nombre: "+r.getNombre()+" toma "+r.getNumeroMaterias()+" materias");
           Scanner n= new Scanner(System.in);
                 System.out.println("1= Extraordinario");
                  System.out.println("2= no Extraordinario");
                  int dato= n.nextInt();
            if(dato==2){
                int total=r.getNumeroMaterias()*135;
            System.out.println("Debe pagar "+total);
            }
            if(dato==1){
                 float total=r.getNumeroMaterias()*135;
                 float adicion=(float) (total*0.15);
                 total= total+adicion;
            System.out.println("Debe pagar "+total); 
            }
            }
            
            r=pA.pop();
            
             if(r!=null){
                 
            System.out.println("Nombre: "+r.getNombre()+" toma "+r.getNumeroMaterias()+" materias");
           Scanner n= new Scanner(System.in);
                 System.out.println("1=Extraordinario");
                  System.out.println("2= no Extraordinario");
                  int dato= n.nextInt();
            if(dato==2){
                int total=r.getNumeroMaterias()*135;
            System.out.println("Debe pagar "+total);
            }else{
                 int total=r.getNumeroMaterias()*135;
            System.out.println("Debe pagar "+total*(15/100));
            
            }
                         
            }
            
             
                  r=pA.pop();
            
             if(r!=null){
                 
            System.out.println("Nombre: "+r.getNombre()+" toma "+r.getNumeroMaterias()+" materias");
           Scanner n= new Scanner(System.in);
                 System.out.println("1=Extraordinario");
                  System.out.println("2= no Extraordinario");
                  int dato= n.nextInt();
            if(dato==2){
                int total=r.getNumeroMaterias()*135;
            System.out.println("Debe pagar "+total);
            }else{
                 int total=r.getNumeroMaterias()*135;
            System.out.println("Debe pagar "+total*(15/100));
            
            }
                         
            }               
    }
}

Código de ejemplo de tratamiento de expresiones infija.

Codigo infijo

import java.util.Scanner;
import java.util.Stack;
 
public class Infijo {
  public static void main(String[] args) {
 
    //Entrada de datos
    System.out.println("*Escribe una expresión algebraica: ");
    Scanner leer = new Scanner(System.in);
 
    //Depurar la expresion algebraica
    String expr = depurar(leer.nextLine());
    String[] arrayInfix = expr.split(" ");
 
    //Declaración de las pilas
    Stack < String > E = new Stack < String > (); //Pila entrada
    Stack < String > P = new Stack < String > (); //Pila temporal para operadores
    Stack < String > S = new Stack < String > (); //Pila salida
 
    //Añadir la array a la Pila de entrada (E)
    for (int i = arrayInfix.length - 1; i >= 0; i--) {
      E.push(arrayInfix[i]);
    }
 
    try {
      //Algoritmo Infijo a Postfijo
      while (!E.isEmpty()) {
        switch (pref(E.peek())){
          case 1:
            P.push(E.pop());
            break;
          case 3:
          case 4:
            while(pref(P.peek()) >= pref(E.peek())) {
              S.push(P.pop());
            }
            P.push(E.pop());
            break; 
          case 2:
            while(!P.peek().equals("(")) {
              S.push(P.pop());
            }
            P.pop();
            E.pop();
            break; 
          default:
            S.push(E.pop()); 
        } 
      } 
 
      //Eliminacion de `impurezas´ en la expresiones algebraicas
      String infix = expr.replace(" ", "");
      String postfix = S.toString().replaceAll("[\\]\\[,]", "");
 
      //Mostrar resultados:
      System.out.println("Expresion Infija: " + infix);
      System.out.println("Expresion Postfija: " + postfix);
 
    }catch(Exception ex){ 
      System.out.println("Error en la expresión algebraica");
      System.err.println(ex);
    }
  } 
 
  //Depurar expresión algebraica
   
  private static String depurar(String s) {
    s = s.replaceAll("\\s+", ""); //Elimina espacios en blanco
    s = "(" + s + ")";
    String simbols = "+-*/()";
    String str = "";
   
    //Deja espacios entre operadores
    for (int i = 0; i < s.length(); i++) {
      if (simbols.contains("" + s.charAt(i))) {
        str += " " + s.charAt(i) + " ";
      }else str += s.charAt(i);
    }
    return str.replaceAll("\\s+", " ").trim();
  } 
 
  //Jerarquia de los operadores
  private static int pref(String op) {
    int prf = 99;
    if (op.equals("^")) prf = 5;
    if (op.equals("*") || op.equals("/")) prf = 4;
    if (op.equals("+") || op.equals("-")) prf = 3;
    if (op.equals(")")) prf = 2;
    if (op.equals("(")) prf = 1;
    return prf;
  }
}

Código de ejemplo de tratamiento de expresiones prefija.

Código Prefijo

import javax.swing.JOptionPane;
 
public class Pilas {
 
    public static void main(String[] args) {
        String text = JOptionPane.showInputDialog("Dame infijo :");
        System.out.println("Prefijo : "+ Infijo2PrefijoTxt(text));
    }
    public static String Infijo2PrefijoTxt(String infijo){
        Pila p1 = Infijo2Prefijo(infijo);
        String text = "";
        while (p1.i > 0)
            text += p1.pop();
        return text;
 
    }
 
    public static Pila Infijo2Prefijo(String infijo) {
        infijo = '(' + infijo ; // Agregamos al final del infijo un ')'
        int tamaño = infijo.length();
        Pila PilaDefinitiva = new Pila(tamaño);
        Pila PilaTemp = new Pila(tamaño);
        PilaTemp.push(')'); // Agregamos a la pila temporal un '('
        for (int i = tamaño-1; i > -1; i--) {
            char caracter = infijo.charAt(i);
            switch (caracter) {
            case ')':
                PilaTemp.push(caracter);
                break;
            case '+':case '-':case '^':case '*':case '/':
                while (Jerarquia(caracter) > Jerarquia(PilaTemp.nextPop()))
                    PilaDefinitiva.push(PilaTemp.pop());
                PilaTemp.push(caracter);
                break;
            case '(':
                while (PilaTemp.nextPop() != ')')
                    PilaDefinitiva.push(PilaTemp.pop());
                PilaTemp.pop();
                break;
            default:
                PilaDefinitiva.push(caracter);
            }
        }
        return PilaDefinitiva;
    }
 
    public static int Jerarquia(char elemento) {
        int res = 0;
        switch (elemento) {
        case ')':
            res = 5; break;
        case '^':
            res = 4; break;
        case '*': case '/':
            res = 3; break;
        case '+': case '-':
            res = 2; break;
        case '(':
            res = 1; break;
        }
        return res;
    }
}

Código de ejemplo de tratamiento de expresiones posfija.

Código Posfijo

import java.util.Scanner;
import java.util.Stack;
 
public class Infijo {
  public static void main(String[] args) {
 
    //Entrada de datos
    System.out.println("*Escribe una expresión algebraica: ");
    Scanner leer = new Scanner(System.in);
 
    //Depurar la expresion algebraica
    String expr = depurar(leer.nextLine());
    String[] arrayInfix = expr.split(" ");
 
    //Declaración de las pilas
    Stack < String > E = new Stack < String > (); //Pila entrada
    Stack < String > P = new Stack < String > (); //Pila temporal para operadores
    Stack < String > S = new Stack < String > (); //Pila salida
 
    //Añadir la array a la Pila de entrada (E)
    for (int i = arrayInfix.length - 1; i >= 0; i--) {
      E.push(arrayInfix[i]);
    }
 
    try {
      //Algoritmo Infijo a Postfijo
      while (!E.isEmpty()) {
        switch (pref(E.peek())){
          case 1:
            P.push(E.pop());
            break;
          case 3:
          case 4:
            while(pref(P.peek()) >= pref(E.peek())) {
              S.push(P.pop());
            }
            P.push(E.pop());
            break; 
          case 2:
            while(!P.peek().equals("(")) {
              S.push(P.pop());
            }
            P.pop();
            E.pop();
            break; 
          default:
            S.push(E.pop()); 
        } 
      } 
 
      //Eliminacion de `impurezas´ en la expresiones algebraicas
      String infix = expr.replace(" ", "");
      String postfix = S.toString().replaceAll("[\\]\\[,]", "");
 
      //Mostrar resultados:
      System.out.println("Expresion Infija: " + infix);
      System.out.println("Expresion Postfija: " + postfix);
 
    }catch(Exception ex){ 
      System.out.println("Error en la expresión algebraica");
      System.err.println(ex);
    }
  } 
 
  //Depurar expresión algebraica
   
  private static String depurar(String s) {
    s = s.replaceAll("\\s+", ""); //Elimina espacios en blanco
    s = "(" + s + ")";
    String simbols = "+-*/()";
    String str = "";
   
    //Deja espacios entre operadores
    for (int i = 0; i < s.length(); i++) {
      if (simbols.contains("" + s.charAt(i))) {
        str += " " + s.charAt(i) + " ";
      }else str += s.charAt(i);
    }
    return str.replaceAll("\\s+", " ").trim();
  } 
 
  //Jerarquia de los operadores
  private static int pref(String op) {
    int prf = 99;
    if (op.equals("^")) prf = 5;
    if (op.equals("*") || op.equals("/")) prf = 4;
    if (op.equals("+") || op.equals("-")) prf = 3;
    if (op.equals(")")) prf = 2;
    if (op.equals("(")) prf = 1;
    return prf;
  }
}

Definiciones, Mapa Conceptual de Colas y Colas con prioridad.

Cola: 
Una cola está caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. Se la denomina también como estructura FIFO, debido a que el primer elemento en ser ingresado es el primer elemento en salir.

Figura 3. Mapa conceptual de colas.

Figura 4. Mapa conceptual de cola con prioridad

Código de ejemplo de Cola.

Código de Cola:

public void inserta(Elemento x) {
        Nodo Nuevo;
        Nuevo = new Nodo(x, null);
        if (NodoCabeza == null) {
            NodoCabeza = Nuevo;
        } else {
            NodoFinal.Siguiente = Nuevo;
        }
        NodoFinal = Nuevo;
    }
 
    public Elemento cabeza() throws IllegalArgumentException {
        if (NodoCabeza == null) {
            throw new IllegalArgumentException();
        } else {
            return NodoCabeza.Info;
        }
    }
 
    public Cola() {
    // Devuelve una Cola vacía
        NodoCabeza = null;
        NodoFinal = null;
    }

Código de ejemplo de Cola con prioridades.

Código colas con prioridad

import Excepciones.*;
public interface ColaPrioridad {
void insertar (Comparable x);
Comparable buscarMin () throws DesbordamientoInferior;
// devuelve el elemento menor
Comparable eliminarMin () throws DesbordamientoInferior;
// devuelve y elimina el elemento menor
void vaciar ();
boolean esVacia ();
}