Estructuras de datos: Stacks en Java

Son estructuras utilizadas como herramientas de programación de tipo LIFO es decir el ultimo producto que entra es el primero que sale.
Solo se permite el acceso a un elemento a la vez: el último elemento insertado.
Poseen dos elementos primario Push: Inserta un elemento en la pila Pop: Elimina un elemento de la pila

En Java, hacen parte del paquete java.util. La clase java.util.Stack es una estructura que guarda objetos genéricos Java e incluye, entre otros los métodos: push( ), pop( ), peek( ) (Equivalente a top( )), size( ) y empty( ) (Equivalente a isEmpty( ) ).

Los métodos pop( ) y peek( ) lanzan la excepción EmptyStackException si son llamados con Pilas Vacías

Un ejemplo del uso de PILAS, son los navegadores web de Internet que guardan las direcciones de los sitios recientemente visitados en una Pila. Cada vez que un usuario visita un nuevo sitio, esa dirección del sitio es guardada en la pila de direcciones. El navegador mediante el botón volver atrás, permite al usuario obtener los sitios previamente visitados.

Una pila es un tipo de dato abstracto (TAD). Posee los siguientes métodos:

push(e): inserta el elemento “e” para que sea la “cima” de la pila
pop( ): quita el elemento de la cima de la pila y lo regresa. Si la pila está vacía y se intenta realizar esta operación se genera un error
size( ): regresa el número de elementos almacenados en la pila.
isEmpty( ): regresa un booleano indicando si la pila está vacía.
Top( ): regresa el elemento de la “cima” de la pila, sin eliminarlo. Si la pila está vacía y se intenta realizar esta operación se genera un error

Si la pila se encuentra llena y se intenta insertar un nuevo elemento, se producirá un error conocido como overflow (Excepción FullStackException)

Algoritmos:

Los siguientes algotimos son para la implementacion de una pila con arrays

PilaVacía

Cuando TOPE = 0, se considera que la Pila se encuentra vacía. No posee elementos. El algoritmo en pseudocódigo es:

Si ( TOPE = 0)
retornar verdadero
SINO:
retornar falso
FSI

PilaLLena

Cuando TOPE = MAX se considera que la Pila se encuentra llena. El algoritmo es similar al anterior modificando solamente el condicional: SI (TOPE = MAX)

Insertar un elemento (PUSH)

Primer se debe verificar que la pila no este llena

Eliminar un elemento (Pop)

Se debe primero verificar que la pila no este vacia

Codigo de Una pila con Array

// Pila de enteros

public class PilaArray {

 /** Máximo número de elementos a insertar en la pila */
 private int numElementos;

 /** Almacén de datos en el que se insertan los elementos **/
 private int elementos[];

 /** Referencia al último elemento insertado. */
 private int indice;

 /** Inicalización del estado del objeto */
 PilaArray(int numElementos) {
  this.numElementos = numElementos;
  // En java el primer índice de un array es 0.
  indice = -1;
  // Creamos el array
  elementos = new int[numElementos];
 }

 /** Indica si la pila está vacia */
 public boolean vacia() {
  return (indice == -1);
 }

 /** Indica si la pila está llena */
 public boolean llena() {
  return (indice == numElementos - 1);
 }

 /** Inserta un elemento en la pila. No hay control de errores. */
 public void apilar(int elemento) {
  indice++;
  elementos[indice] = elemento;
 }

 /** Saca un elemento de la pila. No hay control de errores */
 public int desapilar() {
  int elemento = elementos[indice];
  indice--;
  return elemento;
 }

 /** Devuelve el número de elementos que tiene la pila */
 public int numElementos() {
  return indice + 1;
 }

 /**
  * Imprime los elementos de la pila Este método es de comprobación. No es un
  * método propio de la clase Pila.
  */
 public void imprimir() {
  for (int i = 0; i <= indice; i++)
   System.out.print(elementos[i] + "-");
  System.out.println();
 }
} // Pila

Codigo de Pila con Lista enlazada Doble:
EL siguiente codigo se implmenta con el mismo codigo que se utilizo para listas doble solo eliminando algunos metosdos, necesario tambien tener la clase Nodo_Doble

public class PilaLista {
 private Nodo elemento;
 private int tope;
 
 public PilaLista(){
  this.elemento = null;
  this.tope=-1;
  
 } 
 public void put(Object datos){
  Nodo nuevo_nodo = new Nodo(elemento, datos);
  this.elemento=nuevo_nodo;  
  this.tope++;
 } 
 
 public Object pop(){
  Nodo eliminado = this.elemento;
  this.elemento = this.elemento.getSiguiente();
  this.tope--;
  return eliminado.getData();
 }
 public int tope(){
  return tope;
 } 
 
 public Boolean vacia(){
  //SI es nulo esta vacia 
  return this.tope <0;
 }
 
}

El siguiente codigo resuelve el problema de ingresar un String Infijo y lo convierte a Postfijo

public class Conversor {
 
 
 private String infija;
 private PilaLista pila;
 private String postifla;
 public Conversor(String infija){
  this.pila = new PilaLista();
  this.infija = infija;
  this.postifla=""; 
 }
 
 private short getprioridad(char michar){
  short prioridad=0;
  switch (michar) {
  case '^':
   prioridad = 3;
   break;
  case '/':
   prioridad = 2;
   break;
  case '*':
   prioridad = 2;
   break;
  case '+':
   prioridad =1;
   break;
  case '-':
   prioridad =1;
   break;
  case '(':
   prioridad =0;
   break;
  case ')':
   prioridad=0;
   break;
  default:
   break;
  }
  return prioridad;
 }
 
 private Boolean esOperador(char michar){
  return michar == '^' || michar =='*' || michar == '/' || michar == '+' || michar == '-' ;
 }
 
 
 private void vaciar(char michar){  
  if(this.pila.vacia()){
   return;
  }else{
   Object elemento = this.pila.pop();
   if(elemento.equals('(')){
    return;
   }else if(getprioridad(michar)>getprioridad((char)elemento)){
    this.pila.put(michar);
   }else{
    this.postifla = this.postifla + elemento;
    vaciar(michar);
    
   }
   
   
    
  }
  
 }
 public void convertir(){
  Object elemento =null;
  for(int i =0; i<this.infija.length(); i++){
   if(esOperador(this.infija.charAt(i))){
    if(this.pila.vacia()){
     this.pila.put(this.infija.charAt(i));
     
    }else{
     elemento = this.pila.pop();
     if(getprioridad((char)elemento) < getprioridad(this.infija.charAt(i))){
      this.pila.put(elemento);
      this.pila.put(this.infija.charAt(i));
     }else{
      this.postifla = postifla + elemento;      
      vaciar(this.infija.charAt(i));
      this.pila.put(this.infija.charAt(i));
     }
   
    }
    
    
   }else if(this.infija.charAt(i) == '('){
    this.pila.put(this.infija.charAt(i));
   }else if(this.infija.charAt(i) == ')'){
    vaciar(this.infija.charAt(i));
   }else{
    this.postifla = this.postifla + this.infija.charAt(i);
   }
  }
  if(!this.pila.vacia()){
   vaciar(')');
  }
   
  
  
 }
 public String getPost(){
  return this.postifla;
 }
 
 

}