estructuras de datos y algoritmos

Oscar Bedoya.

oscarbed@eisc.univalle.edu.co

http://eisc.univalle.edu.co/~oscarbed/Estructuras/

Edificio 331, 2º piso, E.I.S.C.

Estructuras de datos y Estructuras de datos y algoritmosalgoritmos

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)PushPopImprimir pilaBuscar elemento en la pilaEs una pila vacía?

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

9090

5151 dato

siguiente

dato

Siguiente(NULL)

Tope de la pila

Pila

Operación: push

Insertar un nuevo nodo a la pila. El elemento que se inserta, pasa a ser el tope de la pila

dato

siguiente

2323

9090

5151 dato

siguiente

dato

Siguiente(NULL)

Tope de la pila

Pila

Operación: pop

Eliminar un elemento de la pila. El elemento que se elimina es el que esté en el tope.

9090

5151 dato

siguiente

dato

Siguiente(NULL)

Tope de la pila

Pila

Pila

•Imprimir pilaRecorre 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 (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

•El campo siguiente del nodo cabecera pasa de ser null a ser el nodo que estamos insertado

2233

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 siguiente el nodo que estamos insertando

2233

5511

2233

Pila

•Pop•Al nodo cabecera se le asigna como siguiente, el siguiente del primer nodo

5511

2233

2233

Pila

•Imprimir datos

Pila

•Está una pila vacía?

Cuando la pila está vacía el campo siguiente de la cabecera es null

Pila

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

class Nodo{

Object dato; Nodo siguiente;

Nodo(Object o) { dato=o; siguiente=null; }

Nodo(Object o, Nodo n) { dato=o; siguiente=n; }} } }

Pila

Crear Pila

Al crear una Pila, se crea el nodo cabecera.

El nodo cabecera tiene como dato null y como siguiente null.

class Pila{

Nodo cabecera;

Pila() { cabecera=new Nodo(null); }

…

}

Pila

•Está una pila vacía?

Cuando la pila está vacía el campo siguiente de la cabecera es null

public boolean estaVacia() { if (cabecera.siguiente==null) { return true; } else { return false; } }

Pila

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

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

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 siguiente el nodo que estamos insertando

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

Pila

Pop

•Al nodo cabecera se le asigna como siguiente, el siguiente del primer nodo

public void pop() { if (cabecera.siguiente==null) System.out.println("LA PILA ESTA VACIA");

else{ Nodo borrar=cabecera.siguiente; cabecera.siguiente=borrar.siguiente; } }

Pila

•Imprimir datos

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

}}

Pila