Algoritmia y Porgramacion

1. INTRODUCCIÓN.
Una Pila es una clase especial de lista en la cual todas las inserciones y borrados
tienen lugar en un extremo denominado extremo, cabeza o tope. otro nombre
para las pilas son listas FIFO (último en entrar, primero en salir) o listas
pushdown (empujdas hacia abajo). El modelo intuitivo de una pila es un conjunto
de objetos apilados de forma que al añadir un objeto se colocaencima del ultimo
añadido y para quitar un objeto del montón hay que quitar antes los que están por
encima de él.Un tipo de dato abstracto PILA incluye las siguientes operaciones.

2. OPERACIONES PRIMITIVAS DE LAS PILAS.
Dentro del tipo abstracto de pila podemos proponer las siguientes primitivas:







CREAR()
DESTRUIR(P)
TOPE(P)
POP(P)
PUSH(x,P)
VACIA(P)ESPECIFICACIÓN SEMANTICA Y SINTACTICA


pila crear ()
Efecto: Devuelve un valor del tipo pila preparado para ser usado y que
contiene un valor de pila vacia.Esta operación es la misma que la de las
listas generales.



void destruir (pila *P)
Argumentos: Una pila P.
Efecto: Libera los recursos que mantienen la lista P de forma que para
volver a usarla se debe asignar una nueva pila con laoperación de
creación. Esta operación es la misma que la de las listas generales.



telemento tope (pila P)
Argumentos: Una pila P que debe ser no vacía.
Efecto: Devuelve el elemento en la cabeza de la pila P. Si, como es lógico,
identificamos la cabeza de una pila con la posición 1, entonces TOPE(P)

puede escribirse en términos de operaciones de listas como ELEMENTO
(PRIMERO(P),P).
void pop (pila P)
Argumentos: Una pila P que debe ser no vacía. Es modificada.
Efecto: Borra el elemento del tope de la pila P, esto es, BORRA
(PRIMERO(P),P). Algunas veces es conveniente implementar POP como
una función que devuelve el elemento que acaba de borrar.



void push (telemento x, pila P)
Argumentos:
x: Un elemento que deseamos poner en la pila.
p: Una pila P valí dondedeseamos poner el elemento x.
Efecto:Inserta el elemento x en el tope de la pila P. El elemento tope
antiguo se convierte en el siguiente al tope y asi sucesivamente. En
términos de primitivas de listas esta operación es INSERTA
(x,PRIMERO(P),P).



int vacia (pila P)
Argumentos: Una pila P.
Efecto: Devuelve si P es una pila vacía.

EQUIVALENCIA CON LAS LISTAS

3. IMPLEMENTACIÓN DELAS PILAS.

Todas las implementaciones de las listas que hemos descrito son validas para las
pilas ya que una pila junto con sus operaciones es un caso especial de una lista
con sus operaciones. Aún asi conviene destacar que las operaciones de las pilas
son más específicas y que por lo tanto la implementación puede ser mejorada
especialmente en el caso de la implementación matricial.IMPLEMENTACIÓN MATRICIAL DE LAS PILAS.
La implementacion basada en matrices para las listas que dimos anteriormente,
no es particularmente buena para las pilas, porque cada PUSH o POP requiere
mover la lista entera hacia arriba o hacia abajo y por tanto, requiere un tiempo
proporcional al número de elementos en la pila. Una forma mejor de usar
matrices toma en cuenta el hecho de que inserciones yborrados ocurren
solamente en el tope y por lo tanto dichas operaciones sólo se efectuarán en un
extremo de la estructura. Obsérvese que la mejora puede ser introducida haciendo
las inserciones y borrados al final de la lista dentro de la implementación
matricial de las listas. Podemos situar el fondo de la pila en el primer elemento de
la matriz y hacer crecer la pila hacia el ultimo elementode la matriz. Un cursor
llamado tope indica la posición actual del primer elemento de la pila.

Para esta implementacion basada en matrices de pilas definimos el tipo de dato
abstracto Pila por
typedef int tElemento

/* Por ejemplo */

typedef struct {
tElemento *elementos;
int Lmax;
int tope;
} tipoPila;
typedef tipoPila *pila;

FUNCIÓN DE ABSTRACCIÓN.
Dado el objeto del tipo...