Tema4_Pilas.pdf

2010
UNAN – LEON
Departamento de Computación
Ingeniería en Sistema y Telemática
Docente: Ing. Juan Carlos Antón S.

Asignatura:
Algoritmo y Estructuras de Datos

ESTRUCTURAS DINÁMICAS DE DATOS
(PILAS)

Estructuras Dinámicas de Datos 2010

Pilas
Definición
Una pila es una colección ordenada de elementos, en una pila se insertan o suprimen los
elementos en un extremo al cual se lellama tope ó cima.
Esto sugiere la idea de una serie de platos, en la que se van apilando uno encima de otro. En un
momento determinado, si se decidiera quitar un plato, el plato que se quitaría sería el último que
pusimos en la pila, es decir, el plato que está más arriba; de ahí, el nombre de estructuras tipo
LIFO (Last In, First Out) último en entrar, primero en salir.
En una pila sepueden agregar nuevos elementos en el tope de la pila o se pueden quitar los
elementos que estén en el tope.
Elemento T

Tope de la lista

El elemento más importante de la pila, es el
último elemento insertado (Elemento T), ya
que es el primero en ser eliminado.

Elemento T-1
Elemento T-2
Elemento T-3
Elemento T-n

Inicio de la lista

Las operaciones más usadas asociadas a las pilasson:
Push (apilar): operación de insertar un elemento en la pila.
Pop (desapilar): operación de eliminar un elemento en la pila.
Ejemplo: si se tiene una pila p y un elemento i, para insertar un elemento se realiza la operación
push (p, i) y para eliminar un elemento se utiliza la operación pop(p)
No existe un límite superior para una pila o por lo menos no se acostumbra a que lo tenga, ponerun nuevo elemento en la pila solo ocasiona una mayor colección de elementos. Al realizar una
operación pop en la pila se debe tener especial consideración al número de elementos que ésta
contenga, ya que si la pila está vacía se puede producir un error por acceder a una zona de
memoria no valida.
Ejemplo: Operaciones sobre una pila, se ha de suponer que la pila está vacía.
push (pila, 1)1

push (pila,8)

push (pila, 5)

8

5

push (pila, 3)

3
5

1

1

1

1

pop (pila)

5
1

pop (pila)

1

Estructuras Dinámicas de Datos 2010

Implementación de una pila utilizando arreglos
Las pilas se suelen comparar con los arreglos, un arreglo simula las inserciones y eliminaciones
como si se tratara de una pila dinámica. La diferencia de un arreglo con elde una pila es que
tiene un tamaño fijo mientras que una pila dinámica crece o decrece conforme a las actividades
que realice el usuario.
Si hemos de utilizar un arreglo como una pila, siempre se ha de llevar un conteo del número de
elementos de la pila para no sobre pasar la dimensión del arreglo. Tanto con el límite superior
(tope) como el inferior.
La inserción o extracción de un elementose realiza siempre por la parte superior, su
implementación mediante arrays limita el máximo número de elementos que la pila puede
contener.
A continuación se presentan dos algoritmos para las dos operaciones básicas:
Operación Push
Inicio
Si tope = MaximoElementosPila entonces
Imprimir “Desbordamiento de la pila”
Fin-si
pila[i] = tope
tope = tope + 1
Fin

Operación Pop
Inicio
Sitope = 0 entonces
Imprimir “Pila Vacia”
Fin-si
Eliminar elemento de la pila
tope = tope – 1
Fin

Ejemplo de una pila implementada con arreglos

#include
#include
#define ELEM_MAX

10

//indica que la pila tendrá un máximo de 10 elementos

int top = -1;
//top o cima indica que la pila está vacía
int contador = 0; //lleva el control del total de números ingresados o sacados

2Estructuras Dinámicas de Datos 2010

//Declaracion de operaciones básicas para la manipulación de pilas
void Push(int Pila[], int dato);
void Pop(int Pila[]);
void ConsultarPila(int Pila[], int Total); //Visualizará los valores introducidos dentro de la pila
void main()
{
int Pila[ELEM_MAX];
Push(Pila, 10);
Push(Pila, 5);
Push(Pila, 3);
ConsultarPila(Pila, contador);
Pop(Pila);...