La estructura básica de una pila

Mgter. Juan Pablo Apaza Condori 1

UNIVERSIDAD CATÓLICA DE SANTA MARIA

P. P. INGENIERÍA SISTEMAS

LABORATORIO DE ALGORITMIA Y ESTRUCTURA DE DATOS I

PILAS Y COLAS

I OBJETIVOS

Explicar la estructura dinámica Pila.

Explicar la estructura dinámica Cola.

Implementar el TAD Pila.

Implementar el TAD cola.

Utilizar los TADs pila y cola para resolver problemas.

II TEMAS

Pilas

Colas

Colas de prioridad

III MARCO TEÓRICO

PILAS

Una pila es un tipo especial de lista, concretamente, es una lista LIFO (Last In First

Out o último en entrar, primero en salir).

Se denomina así porque el comportamiento de esta estructura de datos es similar al de un

conjunto de elementos apilados unos sobre otros.

Como no se conoce, a priori, el número de elementos que pueden estar en la pila, una

implementación adecuada para una pila será una implementación en la memoria dinámica.

La estructura básica de una pila es una lista enlazada, y la diferencia entre una pila y

una lista enlazada reside en las operaciones; las operaciones aplicadas a una pila son un

subconjunto de las operaciones aplicables a una lista, considerando que las inserciones y

borrados tienen lugar siempre en la misma posición, posición que recibe el nombre de cima

de la pila.

Sesión

7

APILADOS

Mgter. Juan Pablo Apaza Condori 2

También se puede definir como una estructura de datos de entrada ordenada por la CIMA

Se puede introducir y eliminar en la CIMA.

Entrada Ordenada: No significa que se puedan comparar con el operador “<“ (menor que).

LIFO: Last Input, First Output.

Operaciones típicas: Insertar(push), retirar (pop)

|

62

244

22

2

CIMA

FONDO

NIL

Agregar un

nuevo

elemento

Eliminar un

elemento

PUSH

POP

P

Mgter. Juan Pablo Apaza Condori 3

OPERACIONES BÁSICAS DE LA PILA

PUSH (X, P): introduce el elemento x en la cima de la pila p.

POP (P): elimina de la pila p el elemento de la cima de la pila.

TOPE (X, P): devuelve en x el elemento que está en la cima de la pila p.

Únicamente puede consultarse el valor del elemento que está en la cabeza de la pila.

CREAPILA (P): crea la pila p.

PILAVACIA (P): es una función que informa sobre el estado de la pila p: devuelve True si la pila

p está vacía y False en otro caso.

APLICACIONES DE LAS PILAS

Se utilizan en:

Compiladores (parsers: reconocedores sintácticos de los compiladores).

Programación de sistemas (para registrar llamadas a subprogramas, y recuperar los datos

anteriores, o recuperar los parámetros).

Recuperación de elementos en orden inverso al que fueron colocados (en un depósito, una pila

de contenedores, sillas, etc. ).

Convertir notación infija a posfija o prefija.

Implementación de recursividad.

Mgter. Juan Pablo Apaza Condori 4

PUSH

CIMA

FONDO

NIL

PUSH: UCSM

U

CIMA

FONDO

NIL

C

U

CIMA

FONDO

NIL

C

S

U

CIMA

FONDO

NIL

PILA VACIA PUSH: U PUSH: C PUSH: S PUSH: M

C

S

M

U

CIMA

FONDO

NIL

P

P

P

P

P

Mgter. Juan Pablo Apaza Condori 5

POP

Se puede implantar con Arrays (estáticos) o con Listas (dinámicas).

Se deben evitar los errores de acceso:

UnderFlow: Sacar un elemento de una Pila Vacía

OverFlow: Meter un elemento en una pila llena (no hay mas espacio estático o para asignar)

Estudiaremos la Pila implementada con Listas enlazadas.

CIMA

FONDO

NIL

POP: UCSM

U

CIMA

FONDO

NIL

C

U

CIMA

FONDO

NIL

C

S

U

CIMA

FONDO

NIL

PILA CON DATOS POP: M POP: S POP: C POP: U

C

S

M

U

CIMA

FONDO

NIL

PILA VACIA

P

P

P

P

P

Mgter. Juan Pablo Apaza Condori 6

TAD PILA CON LISTAS SIMPLEMENTE ENLAZADAS

VENTAJAS:

No se desperdicia posiciones de memoria

El tamaño de la pila se ajusta exactamente a la cantidad de elementos.

El OverFlow estará ligado a la capacidad de RAM y del direccionamiento del Sistema

Operativo.

DESVENTAJAS:

Más Lento por la gestión de memoria

Mayor Complejidad Espacial: se necesita mas memoria por cada elemento de la pila para

guardar el ptr

PILAS CON LISTAS SIMPLEMENTE ENLAZADAS: DECLARACIÓN FORMAL

class nodo

{

public:

nodo(int v,nodo *sig=NULL)

{

valor=v;

siguiente=sig;

}

private:

int valor;

nodo *siguiente;

friend class pila;

};

typedef nodo *pnodo;

class pila

{

public:

pila()

{

cima=NULL;

}

~pila();

void PUSH(int v);

void POP();

bool PilaVacia()

{

return cima==NULL;

}

int* TOPE();

private:

pnodo cima;

};

23

4

CIMA

FONDO

NIL

P

Mgter. Juan Pablo Apaza Condori 7

PILAS CON LISTAS SIMPLEMENTE ENLAZADAS: INSERCIÓN

Parámetros: Pila (P) , elemento (e)

Procedimiento:

1. Crear el nodo con el elemento

2. Actualizar los apuntadores involucrados

EJEMPLO

Dada la siguiente pila con listas simplemente enlazadas, se desea se desea realizar la operación

PUSH con el valor de 10.

SOLUCIÓN

1. Crear nuevo nodo

1. Crear nuevo

nodo

new nodo(10, cima);

10

23

4

CIMA

FONDO

NIL

P

Mgter. Juan Pablo Apaza Condori 8

2. Actualizar apuntadores del nuevo nodo

void pila::PUSH(int v)

{

cima=new nodo(v,cima);

}

23

4c

CIMA

FONDO

NIL

P

10

cima== new nodo(10, cima);

2. Actualizar

apuntadores

del nuevo

nodo

Mgter. Juan Pablo Apaza

...