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

...