Pilas en Java

Una pila (stack) es una colección ordenada de elementos a los que sólo se puede acceder por un único lugar o extremo de la pila.  Al primer elemento agregado se lo denomina como "fondo", mientras que al último se lo conoce como "cima". Los elementos de la pila se añaden o se borran de la misma sólo por su parte superior (cima).

Debido a su propiedad específica “último en entrar, primero en salir ” se conoce a las pilas como

estructura de datos LIFO (last-in / first-out). 

Una pila es una estructura para el almacenamiento de datos, en la cual la información posee solamente una entrada y salida para su acceso, es decir mantiene una estructura LIFO(Last in First out) lo que quiere decir que el ultimo elemento ingresado debe ser el primero al cual accedemos, por ende el primer elemento ingresado puede solamente ser visto si pasamos por todos los elementos de la Pila.Dentro de java podemos acceder a este tipo de clase mediante el uso de la clase Stack.

Una pila se puede implementar de las siguientes formas:

1. Guardando los elementos en un arreglo en cuyo caso su dimensión o longitud es fija. 
2. Utilizando un vector para almacenar los elementos. 
3. Construir una lista enlazada, cada elemento de la pila forma un nodo de la lista; la lista crece o decrece según se añaden o se extraen, respectivamente, elementos de la pila; ésta es una representación dinámica y no existe limitación en su tamaño excepto la memoria de la computadora.

Operaciones de las Pilas:

Una pila cuenta con 2 operaciones imprescindibles:

Apilar (push): 

Consiste en añadir un elemento a la pila. En la siguiente imagen se explica de una forma más abstracta en la que se puede ver que se está añadiendo el dato "7" sobre el dato "8", convirtiéndose éste en la "cima" de la pila.

Desapilar (pop): 

Es la operación contraria de "apilar", es decir, en lugar de añadir elementos a la pila, se los va a quitar de la misma. En la siguiente imagen se explica de una forma más abstracta en la que se puede ver que se está quitando de la pila el dato "7" establecido anteriormente como la "cima".

Ejemplo práctico:

Clase pilas

package estructurasDeDatos;

public class Pila {
 private int[] pila;
 private int top;
 private int tamanioPila;
 
 public Pila(){
  tamanioPila = 1;
  top = -1;
  pila = new int[tamanioPila];
 }
 
 //las operaciones basicas de la pila
 public void push(int dato){
  if (top == (tamanioPila -1))
   redimensionar();
  pila[++top] = dato;
 }
 
 public Integer pop(){
  if(top < 0)
   return null;
  return pila[top--];
 }
 
 private void redimensionar(){
  int[] temp = pila;
  tamanioPila *= 2;
  pila = new int[tamanioPila];
  
  for(int i = 0; i <= top; i++)
   pila[i] = temp[i];
 }
}

Clase principal

package estructurasDeDatos;

public class PilaPrueba {

 public static void main(String[] args) {
  Pila pila = new Pila();
  
  pila.push(10);
  pila.push(20);
  pila.push(30);
  
  System.out.println(pila.pop());
  System.out.println(pila.pop());
  System.out.println(pila.pop());
  System.out.println(pila.pop());
 }

}

Después de las dos operaciones fundamentales en una pila, se pueden establecer otras, las cuales servirán para obtener información y manipular su contenido:

CrearPila: Inicia la pila

Pila vacía (Empty): Comprueba si la pila no tiene elementos

Pila llena: Comprueba si la pila está llena de elementos

Limpiar pila: Quita todos sus elementos y deja la pila vacía

CimaPila (Peek): Obtiene el elemento cima de la pila

Tamaño de la pila: Número de elementos máximo que puede contener la pila

Buscar (Search): Busca un elemento determinado que esté dentro de la pila y devuelve su posición.

Una pila es una estructura de datos del tipo LIFO, con dos operaciones imprescindibles: apilar (push) y desapilar (pop), al primer elemento se lo conoce como "fondo" y al último como "cima".

Aplicaciones de las Pilas

Cuando un programa llama a un subprograma, internamente, se utilizan pilas para guardar el lugar desde donde se hizo la llamada, y el estado de las variables en ese momento.
Otro ejemplo es que todo algoritmo recursivo, puede ser implementado en forma iterativa utilizando una pila para almacenar los valores de las variables y parámetros.

En java podemos importar la librería java.util.Stack

Con las Pilas podemos hacer operaciones como Push (apilar)

Push o apilar .-los elementos se introducen en la pila por un extremo

POP .- sacar datos de la pila (desapilar)

EMPTY.- comprueba si la pila está vacía.

PEEK (consulta el primer elemento de la cima de la pila)

SEARCH (que busca un determinado elemento dentro de la pila y devuelve su posición dentro de ella).

Código Pila

            import java.util.Stack;

public class Principal {

    public static void main(String[] args) {
   
        Stack pila=new Stack();
        for(int x=5;x<=10;x++){
            pila.push(Integer.toString(x));
            while(!pila.empty()){
                System.out.println(pila.pop());
            }
        }
    }
    
}

EXPRESIONES InFija, PreFija Y PosFija

PreFija:Notación prefija: El orden es operador, primer operando, segundo operando

InFija: Notación infija: La notación habitual. El orden es primer operando, operador, segundo operando

PosFija:Notación postfija: El orden es primer operando, segundo operando, operador

Código de ejemplo de tratamiento de expresiones posfija

            import java.util.Stack;
/**
 *
 * @author Administrador
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        //Entrada (Expresión en Postfija)
        String expr = "2 23 6 + * 1 -"; // equivale a 2*(23+6)-1
        String[] post = expr.split(" ");    

        //Declaración de las pilas
        Stack < String > E = new Stack < String > (); //Pila entrada
        Stack < String > P = new Stack < String > (); //Pila de operandos

        //Añadir post (array) a la Pila de entrada (E)
        for (int i = post.length - 1; i >= 0; i--) {
          E.push(post[i]);
        }

        //Algoritmo de Evaluación Postfija
        String operadores = "+-*/%"; 
        while (!E.isEmpty()) {
          if (operadores.contains("" + E.peek())) {
            P.push(evaluar(E.pop(), P.pop(), P.pop()) + "");
          }else {
            P.push(E.pop());
          } 
        }

        //Mostrar resultados:
        System.out.println("Expresion: " + expr);
        System.out.println("Resultado: " + P.peek());

      }

      private static int evaluar(String op, String n2, String n1) {
        int num1 = Integer.parseInt(n1);
        int num2 = Integer.parseInt(n2);
        if (op.equals("+")) return (num1 + num2);
        if (op.equals("-")) return (num1 - num2);
        if (op.equals("*")) return (num1 * num2);
        if (op.equals("/")) return (num1 / num2);
        if (op.equals("%")) return (num1 % num2);
        return 0;
      }
}

Referencias:

• Alvarez,D.(2011).Pilas en Java.Recuperado el 28 de noviembre de 2016 de http://soloinformaticayalgomas.blogspot.com/2011/02/pilas-en-java.html
• Sierra,M(s,n).La estructura de datos pila en java.Clase Stac del API Java.Ejemplo Simple y ejercicios resueltos.Recuperado el 28 de noviembre de 2016 de http://aprenderaprogramar.com/index.php?option=com_content&view=article&id=608:la-estructura-de-datos-pila-en-java-clase-stack-del-api-java-ejemplo-simple-y-ejercicios-resueltos-cu00920c&catid=58:curso-lenguaje-programacion-java-nivel-avanzado-i&Itemid=180
• Alvarez,D.(2011).Colas en Java.Recuperado el 28 de noviembre de 2016 de http://soloinformaticayalgomas.blogspot.com/2011/03/colas-en-java.html

Colas en Java

Una cola es una estructura de datos que almacena elementos en una lista y permite acceder a los datos por uno de los dos extremos de la lista. Un elemento se inserta en la cola (parte final) de la lista y se suprime o elimina por el frente (parte inicial, frente) de la lista. Las aplicaciones utilizan una cola para almacenar elementos en su orden de aparición o concurrencia.

Una cola es una estructura de datos en donde las eliminaciones se realizan por uno de sus extremos, denominado frente, y las instrucciones por el otro, denominado final. Se las conoce como estructuras FIFO (First INPUT FIRST OUTPUT).

Una cola se deberá implementar de forma dinámica mediante una array y dos variables numéricas (frente, final).

Una cola se puede componer a partir de una lista enlazada, pero las operaciones son distintas

OPERACIONES

Encolar.- introducir algo en la cola, los elementos se introducen en la cola por el final

Consultar.- Obtener el siguiente elemento de la cola, como es una cola, el siguiente elemento estará al principio de la cola, podemos obtener la cabeza de la cola accediendo al primer elemento de la cola.
Eliminar.- eliminar el siguiente elemento de la cola


En Java podemos crear Colas en pocas lineas de código,usando la clase de java.util.Queue con la cual podemos crear Colas y que contiene los siguientes métodos

Ejemplo práctico:

A continuación se muestra un programa simple, en donde se aplican las operaciones encolar y desencolar elementos en una Cola. El programa está hecho con listas simples enlazadas en el cual se insertan 5 elementos, utilizando la función insertar (encolar). Después se utiliza la función extraer (encolar) para eliminar el primer nodo. Finalmente se cuenta cuantos elementos tiene la nueva lista, e imprime los valores.

Clase Nodo

public class Nodo 
{
 //Declaracion de atributos
 private int dato;
 private Nodo next;
  
 //Constructor
 public Nodo(int dato){
 this.dato=dato;
 }
  
 //Metodos getter and setters
 public int getDato() 
 {
 return dato;
 }
 public void setDato(int dato) 
 {
 this.dato = dato;
 }
 public Nodo getNext() 
 {
 return next;
 }
 public void setNext(Nodo next) 
 {
 this.next = next;
 }
  
 //Metodo toString
 public String toString()
 {
 String s=" "+dato+" ";
 return s;
 }
}

Clase colas

public class Colas 
{
 //Declaración de atributos
 private Nodo inicio;
 private Nodo termino;
 
 //Constructor sin parametros
 public Colas()
 {
 inicio=null;
 termino=null;
 }
  
 //Metodo insertar
 public void insertar(int dato)
 {
 Nodo i=new Nodo(dato);
 i.setNext(null);
 if(inicio==null & termino==null)
 {
 inicio=i;
 termino=i;
 }
 termino.setNext(i);
 termino=termino.getNext();
 }
  
 //Metodo extraer dato
 public int extraer()
 {
 int dato=inicio.getDato();
 inicio=inicio.getNext();
 return dato;
 }
  
 //Metodo para comprobar que la cola no esta vacia
 public boolean estaVacia()
 {
 boolean cola=false;
 if(inicio==null & termino==null)
 {
 cola=true;
 System.out.println("La cola esta vacia");
 }
 else
 {
 System.out.println("La cola no esta vacia");
 cola=false;
 }
 return cola;
 }
  
 //Metodo para contar los elementos de la cola
 public int contar()
 {
 int contador=0;
 Nodo c=this.inicio;
 while(c!=null)
 {
 contador++;
 c=c.getNext();
 }
 System.out.println("Numero de datos en la cola: "+contador);
 return contador;
 }
  
 //Metodo toString
 public String toString()
 {
 Nodo c=this.inicio;
 String s="";
 while(c!=null)
 {
 s=s+c.toString();
 c=c.getNext();
 }
 return s;
 } 
}

Clase Principal

public class Principal 
{
 public static void main(String[] args) 
 {
  Colas cola1=new Colas();
  cola1.insertar(46);
  cola1.insertar(12);
  cola1.insertar(87);
  cola1.insertar(125);
  cola1.insertar(30);
  cola1.extraer();
  cola1.estaVacia();
  cola1.contar();
  System.out.println(cola1.toString());
 }
}

Para Insertar:
– add(e)
– offer(e)

Para Extraer:
– remove()
– poll()

Para Consultar el Frente:
– element()
– peek()

Ejemplo de Cola

            import java.util.LinkedList;
import java.util.Queue;

public class Principal {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
        /*Creamos la Cola Indicando el tipo de dato*/
        Queue cola=new LinkedList();
        /*Insertamos datos*/
            cola.offer(3);
            cola.add(14);
            cola.offer(12);
            cola.add(7);
            cola.offer(10);
        /*Impresion de la Cola llena con los datos*/
        System.out.println("Cola llena: " + cola);
        /*Estructura repetitiva para desencolar*/
        while(cola.poll()!=null){//Desencolamos y el valor se compara con null
            System.out.println(cola.peek());//Muestra el nuevo Frente
        }
        /*Muestra null debido a que la cola ya esta vacia*/
        System.out.println(cola.peek());     
    }
    
}


       

Ejemplo cola con Prioridades

En java podemos importar la clase java.util.PriorityQueue . A cada elemento ingresado se le da un nivel de prioridad con base en un árbol binario 

            import java.util.PriorityQueue;

/**
 *
 * @author Administrador
 */
public class Principal {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        PriorityQueue pq=new PriorityQueue();
        
        System.out.println(pq.isEmpty());
        pq.isEmpty();
        
        pq.add(3);
        pq.add(14);
        pq.add(12);
        pq.add(7);
        pq.add(10);
        pq.add(1);
        pq.add(6);
        pq.add(-8);
        pq.add(9);
        pq.add(5);
        
        System.out.println(pq);
        System.out.println(pq.isEmpty());
        System.out.println(pq.peek());
        System.out.println(pq);
        /*pq.poll();
        pq.element();
        pq.remove();*/
        
    }
    
}


       

Resumen
Una cola es una estructura de datos del tipo FIFO, con dos operaciones imprescindibles: encolar y desencolar, al primer elemento se lo conoce como "frente o principio" y al último como "final".


En Java podemos crear Colas en pocas lineas de código,usando la clase de java.util.Queue con la cual podemos crear Colas y que contiene los siguientes métodos

Referencias:

• Alvarez,D.(2011).Pilas en Java.Recuperado el 28 de noviembre de 2016 de http://soloinformaticayalgomas.blogspot.com/2011/02/pilas-en-java.html
• Sierra,M(s,n).La estructura de datos pila en java.Clase Stac del API Java.Ejemplo Simple y ejercicios resueltos.Recuperado el 28 de noviembre de 2016 de http://aprenderaprogramar.com/index.php?option=com_content&view=article&id=608:la-estructura-de-datos-pila-en-java-clase-stack-del-api-java-ejemplo-simple-y-ejercicios-resueltos-cu00920c&catid=58:curso-lenguaje-programacion-java-nivel-avanzado-i&Itemid=180
• Alvarez,D.(2011).Colas en Java.Recuperado el 28 de noviembre de 2016 de http://soloinformaticayalgomas.blogspot.com/2011/03/colas-en-java.html