La estructura básica de una pila
Enviado por thermojetic • 7 de Octubre de 2012 • Documentos de Investigación • 4.048 Palabras (17 Páginas) • 573 Visitas
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
...