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;
}
}