ESTRUCTURA DE DATOS PILAS (STACK)

Una pila es una colección ordenada de elementos la cual tiene un extremo por donde se pueden insertar nuevos elementos y por ese mismo extremo se pueden eliminar. Ese extremo de la pila es llamado parte superior de la pila o Top de la pila.

Para eliminar un elemento de la pila, será el elemento que este en la parte superior. El atributo más importante de la pilas es: “El ultimo en entrar es el primero en salir.”

A este tipo de estructura de dato se le llama estructuras tipo LIFO (Last In First Out)

Representación gráfica de Pila

OPERACIONES CON PILAS.

PUSH: Inserta un elemento en la Pila. Por ejemplo: PUSH(Pila, elemento);

POP: Elimina un elemento de la Pila . Por ejemplo: POP(Pila,elemento);

STACK-TOP O TOP: Permite ver cual es el elemento que esta en la parte superior de la Pila. Este se puede implementar mediante las dos operaciones anteriores. Por ejemplo: POP (Pila,elemento);

System.out.println(elemento); PUSH(Pila, elemento);

Si el PUSH está siendo utilizado en pilas estáticas deberán checar si no se ha llenado la Pila (STACK OVERFLOW).

Para el POP debemos checar que la Pila no esté vacía (STACK UNDERFLOW)

APLICACIONES CON PILAS.

Recursión, Memoria de la computadora (STACK), evaluación de expresiones aritméticas, notación Polaca.

EJEMPLO: Checar si una expresión es correcta en cuanto a paréntesis ((X+Y)+(Z+F))*(M+B).

Una posible solución a este problema es: Tener un contador que aumente para cada paréntesis izquierdo ( y disminuya por cada paréntesis derecho ). Será correcta la expresión si el contador al final es cero y nunca tomo valores negativos.

Pero supongamos que utilizamos tres símbolos de asociación: [ ],{},( ) ¿Cómo podemos checar si una expresión es correcta en cuanto a estos 3 símbolos de asociación?

PILA

x

C

*A

Parte superior

1

No podemos hacerlo por contadores porque debemos abrir con [,{,( pero podemos cerrarlos en otro orden:

1. {(X+Y) * [(a+b) * {c+d} (e+f)+a]}+{a+b}

2. [{(A+B)}]

LA SOLUCION A ESTE PROBLEMA ES: Almacenar (PUSH) en una pila los símbolos izquierdos y cuando se identifique un símbolo de asociación derecho equivalente al izquierdo. Entonces se saca (POP) de la Pila el símbolo izquierdo correspondiente y así sucesivamente hasta terminar de analizar la expresión. Si al terminar, la PILA esta vacía entonces la expresión es correcta, en caso contrario la expresión es incorrecta.

OTRO EJEMPLO SON LAS EXPRESIONES REGULARES.

((1 + 2) * 4) + 3

1 2 + 4 * 3 +

Input Operation Stack1 Push(1) 1

2 Push(2)21

+

Suma:

A=Pop(Stack)B=Pop(Stack)C=A+BC=2+1=3Push(C)

1

3

4 Push(4)43

*

Multiplicación:

A=Pop(Stack)B=Pop(Stack)C=A*BC=4*3Push(C)

3

12

3 Push(3) 312

+

Suma:

A=Pop(Stack)B=Pop(Stack)C=A+BC=3+12=15Push(C)

12

15

2

El resultado final es 15, que se encuentra en la parte superior de la Pila.

EJEMPLO DE UN PROGRAMA PILA.

class Pila { private int[]pila; private int tope; private int max; public Pila(){ max=10; pila=new int[max]; tope=-1; } public static void main(String args[]){ Pila p1= new Pila(); int elementos=0, dato= 0; char op,continuar; do{ Menu(); op=Teclado.readChar(); switch(op){ case 'P': System.out.print("Dar numero: ");dato=Teclado.readInt(); p1.Push(dato); break; case 'Q': dato=p1.Pop();System.out.print("Elemento "+ dato); continuar=Teclado.readChar();break; case 'V': dato=p1.Stack_Top();System.out.print("Elemento "+ dato); continuar=Teclado.readChar();break; case 'T': p1.Stack_Look();break; } }while(op!='F'); } //main

public void Push(int dato) { if(tope>=max) System.out.println("Error de dato"); else { tope++; pila[tope]=dato; } }

public int Pop (){ int x=0; if(tope<0) System.out.println("Error de subdesbordamiento"); else{ x=pila[tope];pila[tope]=0; tope--; } return(x);}

3

public int Stack_Top (){ int x=0; if(tope<0) System.out.println("Error de subdesbordamiento"); else x=pila[tope]; return(x);}

public static void Menu(){System.out.println("MENU DE PILA");System.out.println("[P]ONER (push)");System.out.println("[Q]UITAR (pop)");System.out.println("[V]ER LA PARTE SUPERIOR (Stack-Top)");System.out.println("[T]ODA LA PILA");System.out.println("[S]ALIR");

}

public void Stack_Look(){ char continuar; System.out.println("Estado actual de la Pila"); for(int i=tope; tope>=0;i--) System.out.println(pila[i]); continuar=Teclado.readChar(); }

}

4