La Pila o Stack
Programación en Java
LA PILA
La pila (stack) es una estructura ordenada de
elementos en la que se pueden insertar o Cima de
remover elementos por un extremo llamado la la pila
cima de la pila (stack top).
El apuntador de pila (stack pointer) señala al
elemento de la cima.
La pila puede carecer por completo de
elementos, en tal caso se le llama pila vacía. Apuntador
En una pila vacía el apuntador de pila señala a de pila
NULL.
Una pila
OPERACIONES BÁSICAS
Las operaciones básicas de la pila son:
Apilar (push(s, i)) - inserta un nuevo elemento a la pila.
Desapilar (pop(s)) - remueve el elemento de la cima de la pila.
E
D D D
C C C C i=D
B B B B
A A A A
Pila antes de Pila después de Pila antes de i Pila después de i
Push(s, E) Push(s, E) Pop(s) Pop(s)
EVOLUCIÓN DE UNA PILA
I=POP(S) PUSH(S,E) PUSH(S,F) I=POP(S) I=POP(S) I=POP(S)
F
D E E E
C C C C C C
B B B B B B B
A A A A A A A
sale D entra E entra F sale F sale E sale C
OTRAS OPERACIONES
La función EMPTY(S) es verdadera si la pila está vacía.
La operación STACKTOP(S), que es equivalente a un POP
seguido de un PUSH.
I = POP(S);
PUSH(S,I);
determina el valor del elemento de la cima sin removerlo.
LA CLASE PILA
La clase pila tiene atributos y métodos:
Los atributos son la colección de elementos y el TOPE.
Los métodos, por otra parte, son todas aquellas operaciones analizadas en la sección
anterior, Pila_Vacia, Pila_Llena, Inserta_Pila, Elimina_Pila.
Algunos lenguajes de programación como por ejemplo los POO, orientados por objetos tiene
predefinidas determinadas estructuras de datos como la clase pila, donde es necesario
declarar una nueva estructura que haga referencia a la clase predefinida para poder acceder y
utilizar a sus atributos y métodos.
Preparado por: Ms. Blanca Duarte de Báez
Ejemplo: Clase Abstracta Pila
TOPE numérico
Datos = Arreglo[1..Max]
Crea_Pila
Pila_Vacia()
Pila_Llena()
Tope_Pila()
Inserta_Pila()
Elimina_Pila()
Preparado por: Ms. Blanca Duarte de Báez
Ejemplo: Definición y desarrollo en
pseudocódigo de procedimientos de la Clase Pila.
‘Declaración e inicialización de constante’
MAX numérico
MAX = 10
Clase Pila
Tope numérico
Dato arreglo[1..MAX]
Crea_Pila
Pila_Vacia()
Pila_Llena()
Tope_Pila()
Inserta_Pila()
Elimina_Pila()
Fin clase
Preparado por: Ms. Blanca Duarte de Báez
P = Clase Pila
procedimiento Crea_Pila(P)
[Link]= 0
fin procedimiento
funcion Pila_Vacia (P)
Si [Link] = 0
Devolver verdadero
Sino
Devolver Falso
fin si
fin funcion
función Pila_Llena (P)
Si [Link] = [Link]
Devolver Verdadero
Sino
Devolver Falso
fin si
fin funcion
Preparado por: Ms. Blanca Duarte de Báez
funcionTope_Pila (P)
si P.Pila_Vacia = Verdadero
‘error de Desbordamientos o - Pila Vacía’
Devolver 0
sino
devolver [Link]
fin si
fin funcion
procedimiento Inserta_Pila(Dato, P)
si P.Pila_Llena = Verdadero
error Desborda miento o Pila llena
sino
[Link] = [Link] + 1
P[Tope] = Dato
Fin Procedimiento
Preparado por: Ms. Blanca Duarte de Báez
Procedimiento Elimina_Pila ( P, Dato )
Si P.Pila_Vacia = Verdadero
error Subdesbordamiento o Pila Vacía
sino
Dato = P[Tope]
[Link]=[Link] - 1
fin si
fin procedimiento
Preparado por: Ms. Blanca Duarte de Báez
Implementación de clase Pila a base de Vectores
con Java
// OPERACIONES PÚBLICAS
// void apilar(x) ->Inserta x
// voiddesapilar() ->Elimina el último elemento insertado
// Objectcima() ->Devuelve el último elemento insertado
// booleanesVacia() ->Devuelve true si vacía, sino false
// void vaciar() ->Elimina todos los elementos
// ERRORES: cima o desapilar sobre la pila vacía
public interface IPila {
voidapilar(Object x);
voiddesapilar() throws Exception;
Object cima() throws Exception;
booleanesVacia();
void vaciar();
}
[Link].*;
Preparado por: Ms. Blanca Duarte de Báez
public class PilaVec implements IPila {
private Vector p;
private int cimaDePila;
static final int CAPACIDAD_POR_DEFECTO = 10;
public PilaVec() {
p = new Vector(CAPACIDAD_POR_DEFECTO);
cimaDePila = -1;
}
Public boolean esVacia() {
return (cimaDePila == -1);
}
Public void vaciar() {
cimaDePila = -1;
}
Preparado por: Ms. Blanca Duarte de Báez
public void apilar(Object x) {
if (++cimaDePila == [Link]()) [Link](x);
[Link](cimaDePila, x);
}
public void desapilar() throws Exception {
if (esVacia()) throw new Exception("pila vacía");
cimaDePila--;
}
public Object cima() throws Exception {
if (esVacia()) throw new Exception("pila vacía");
[Link](cimaDePila);
}
}
Observación: Una interface en Java es una colección de métodos abstractos y
propiedades. En ellas se especifica qué se debe hacer pero no su
implementación. Serán las clases que implementen estas interfaces las que
describan la lógica del comportamiento de los métodos.
Preparado por: Ms. Blanca Duarte de Báez
ALGORITMO DE CHEQUEO DE
PARÉNTESIS
Algoritmo para checar paréntesis. La expresión se almacena en la cadena S.
1. VALIDO = VERDADERO
2. i = 1
3. CONTADOR = 0
4. MIENTRAS VALIDO AND i <= LONGITUD(S) HACER
5. SI S[i] = '(' ENTONCES
6. CONTADOR = CONTADOR + 1
7. SINO
8. SI S[i] = ')' ENTONCES
9. CONTADOR = CONTADOR - 1
10. SI CONTADOR < 0 ENTONCES
11. VALIDO = FALSO
12. i = i + 1
13. SI CONTADOR <> 0 ENTONCES
14. VALIDO = FALSO
Actividad
Escriba el algoritmo de chequeo de paréntesis en Java.
ALGORITMO DE CHEQUEO DE PARÉNTESIS 2
Algoritmo para checar expresiones con paréntesis bien construidas. Se utiliza una pila P. La cadena se
almacena en una variable S.
1. VALIDO = VERDADERO
2. i = 1
3. MIENTRAS VALIDO AND i <= LONGITUD(S)
4. SI (S[i] = '(') OR (S[i] = '[') OR (S[I] = '{') ENTONCES
5. PUSH(P,S[i])
6. SINO
7. SI (S[i] = ')') OR SI (S[i] = ']') OR SI (S[i] = '}') ENTONCES
8. SI EMPTY(P) ENTONCES
9. VALIDO = FALSO
10. SINO
11. C = POP(P)
12. SI NOT((C='(' AND S[i] = ')')OR(C='[' AND S[i] =']')
OR (C='{' AND S[i]= '}')) ENTONCES
13. VALIDO = FALSO
14. i = i + 1
15. SI NOT EMPTY(P) ENTONCES
16. VALIDO = FALSO
REPRESENTACIÓN
Una pila puede representarse con un registro, uno de los campos es
un entero usado como apuntador de pila y el otro campo es un
arreglo lineal de elementos de la pila.
Apuntador de pila Pila
S: 4 '(' '[' '(' '{'
[Link] = apuntador de pila.
[Link][[Link]] = elemento de la cima de la pila
OPERACIONES EMPTY Y POP
NOTA: Se supone una pila de caracteres
Función EMPTY(S:PILA) regresa BOOLEANO
1. SI [Link] = 0 ENTONCES
2. REGRESA VERDADERO
3. SINO
4. REGRESA FALSO
Función POP(S:PILA) regresa CARÁCTER
1. X ¬ [Link][[Link]]
2. [Link] ¬ [Link] - 1
3. REGRESA X
OTRA VERSIÓN DE POP
Función POP(S:PILA) regresa CARÁCTER
1. SI EMPTY(S) ENTONCES
2. ERROR (‘bajo flujo, pila vacía’)
3. SINO
4. X = [Link][[Link]]
5. [Link] = [Link] - 1
6. REGRESA X
OPERACIÓN POPANDTEST
SUBRUTINA POPANDTEST(S: PILA; BAJOFLUJO:
BOOLEANO; X: CARÁCTER)
1. SI EMPTY(S) ENTONCES
2. BAJOFLUJO = VERDADERO
3. SINO
4. BAJOFLUJO = FALSO
5. X = [Link][[Link]]
6. [Link] = [Link] - 1
7. REGRESA X
OPERACIÓN PUSH
SUBRUTINA PUSH(S:PILA, X:CARACTER)
1. [Link] = [Link] + 1
2. [Link][[Link]] = X
SUBRUTINA PUSH(S:PILA, X:CARACTER)
1. SI [Link] = STACKSIZE ENTONCES
2. ERROR (’sobreflujo en la pila’)
3. SINO
4. [Link] = [Link] + 1
5. [Link][[Link]] ¬ X
OPERACIÓN STACKTOP
FUNCION STACKTOP(S:PILA) regresa CARACTER
1. SI EMPTY(S) ENTONCES
2. ERROR (‘pila vacia’)
3. SINO
4. REGRESA [Link][[Link]]
Implementación de pilas en Java
Primero se incrementa, luego se
hace la asignación
public void push(char i){
if(tope+1 < [Link])
public class PilaChar{ pila[++tope] = i;
private char pila[]; }
private int tope; public char pop(){
public PilaChar(int capacidad) if(isEmpty())
{ return 0;
pila = new char[capacidad]; return pila[tope--];
tope = -1; }
} public String toString(){
public boolean isEmpty(){ return new
return tope == -1; String(pila,0,tope+1);
} }
}
Primero se obtiene el valor de pila y luego se decrementa. Convierte a cadena un arreglo de caracteres.
Referencias Bibliográficas
Cairó, Osvaldo/Guardati, Silvia (2006). Estructura de Datos. 3ra
Edición.
McGraw-Hill Interamericana Editores. S.A. de C.V.
ISBN: 970-10-5908-5
LOOMIS,Mary. Estructura de Datos y Organización de Archivos, 2da.
Edición. 1991.
México. Editorial Prentice-Hall Hispanoamericana S.A.
[Link]
colas_y_listas.pdf
[Link]
[Link]
