Estructuras de datos y algoritmos
Oscar Bedoya.
[email protected]
http://eisc.univalle.edu.co/~oscarbed/Estructuras/
Edificio 331, 2º piso, E.I.S.C.
Pila
Definición
Una pila es una secuencia de elementos de un
tipo base, el último elemento se le llama tope.
En una pila sólo se puede adicionar al tope y solo
se puede retirar de él.
Pila
Definición
TDA
Pila
Descripción:
Una pila es una secuencia de elementos de un tipo base, el
último elemento se le llama tope. En una pila solo se puede
adicionar al tope y solo se puede retirar de él.
Invariante:
Pila=<elem0, elem1, . . . , elemn-1> л ( i, 0 <= i < n, elemi
 Tipo) л elemn-1 = tope
Pila
Operaciones:
Pila (Constructor)
Push
Pop
Imprimir pila
Buscar elemento en la pila
Es una pila vacía?
Pila
Cada nodo se representa por
medio de dos campos:
51
dato
Tope de la
pila
siguiente
Campo dato: contiene el valor
del nodo
Campo siguiente: indica cuál es
90
dato
el nodo con el que se enlaza
Siguiente(NULL)
Pila
Operación: push
23
dato
Tope de la
pila
siguiente
Insertar un nuevo nodo
a la pila. El elemento que
se inserta, pasa a ser el
tope de la pila
51
dato
siguiente
90
dato
Siguiente(NULL)
Pila
Operación: pop
51
dato
Tope de la
pila
siguiente
Eliminar un elemento de
la pila. El elemento que
se elimina es el que esté
en el tope.
90
dato
Siguiente(NULL)
Pila
•Imprimir pila
Recorre toda la pila, comenzando por el tope, y muestra el
elemento de cada nodo
•Buscar elemento en la pila
•Es una pila vacía?
Pila
•Pila (Constructor)
Al crear una pila, se crea el nodo
cabecera.
El nodo cabecera tiene como
dato null y como siguiente null.
Pila
•Push ( La Pila está vacía)
•Se crea un nuevo nodo con el
dato que se desee colocar y con
siguiente null
23
•El campo siguiente del nodo
cabecera pasa de ser null a ser el
nodo que estamos insertado
Pila
•Push( La pila no está vacía)
•Se crea un nuevo nodo con el dato que
se desee colocar y en su campo
siguiente se establece el siguiente del
nodo cabecera
•Al nodo cabecera se le asigna como
23
51
23
siguiente el nodo que estamos
insertando
Pila
•Pop
•Al nodo cabecera se le asigna como
siguiente, el siguiente del primer nodo
51
23
23
Pila
•Imprimir datos
Pila
•Está una pila vacía?
Cuando la pila está vacía el campo siguiente de la
cabecera es null
Pila
class Nodo{
Object dato;
Nodo siguiente;
Nodo(Object o)
{
dato=o;
siguiente=null;
}
Nodo(Object o, Nodo n)
{
dato=o;
siguiente=n;
}
} }
}
Cada nodo se
representa por medio
de dos campos:
Campo dato: contiene
el valor del nodo
Campo siguiente:
indica cuál es el nodo
con el que se enlaza
Pila
class Pila{
Nodo cabecera;
Pila()
{
cabecera=new Nodo(null);
}
…
}
Crear Pila
Al crear una Pila, se
crea el nodo cabecera.
El nodo cabecera tiene
como dato null y como
siguiente null.
Pila
public boolean estaVacia()
{
if (cabecera.siguiente==null)
{
return true;
}
else
{
return false;
}
}
•Está una pila
vacía?
Cuando la pila está
vacía el campo
siguiente de la
cabecera es null
Pila
public void push(Object o)
{
Nodo nuevo=new Nodo(null);
if ( estaVacia() )
{
nuevo=new Nodo(o);
nuevo.siguiente=null;
cabecera.siguiente=nuevo;
}
else
{
nuevo=new Nodo(o);
nuevo.siguiente=cabecera.siguiente;
cabecera.siguiente=nuevo;
}
}
Push
( La pila está vacía)
•Se crea un nuevo nodo con el
dato que se desee colocar y con
siguiente null
•El campo siguiente del nodo
cabecera pasa de ser null a ser el
nodo que estamos insertado
Pila
public void push(Object o)
{
Nodo nuevo=new Nodo(null);
if ( estaVacia() )
{
nuevo=new Nodo(o);
nuevo.siguiente=null;
cabecera.siguiente=nuevo;
}
else
{
nuevo=new Nodo(o);
nuevo.siguiente=cabecera.siguiente;
cabecera.siguiente=nuevo;
}
}
Push
( La pila no está vacía)
•Se crea un nuevo nodo con el
dato que se desee colocar y en
su campo siguiente se
establece el siguiente del nodo
cabecera
•Al nodo cabecera se le asigna
como siguiente el nodo que
estamos insertando
Pila
public void pop()
{
if (cabecera.siguiente==null)
System.out.println("LA PILA ESTA VACIA");
else{
Nodo borrar=cabecera.siguiente;
cabecera.siguiente=borrar.siguiente;
}
}
Pop
•Al nodo cabecera se le
asigna como siguiente,
el siguiente del primer
nodo
Pila
public void imprimir()
{
Nodo actual=new Nodo(null);
if (estaVacia())
System.out.println("Vacio");
else
{
actual=cabecera;
System.out.println("\n");
while( actual != null){
System.out.print(" |" + actual.dato + "|->" );
actual=actual.siguiente;
}
}
}
•Imprimir datos
Descargar

Pila(Stack)