PILAS

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 coloca encima 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 la operació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í donde deseamos 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 DE LAS 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 y borrados 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 elemento de 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 rep p, *p = (elemento, Lmax, tope), el objeto abstracto que representa es:
<p->elemento[p->tope], p->elemento[p->tope - 1],..., p->elemento[0]>.

INVARIANTE DE LA REPRESENTACIÓN.

Dado el objeto del tipo rep p, *p = (elemento, Lmax, tope) debe cumplir:

• p tiene valores obtenidos de llamadas (pila) malloc(sizeof(tipopila));
  
• p->elemento tiene una dirección válida de tipo telemento*.
  
• p->Lmax > 0.
  
• -1 <= p->tope <= p->Lmax - 1.

Las operaciones tipicas sobre las pilas están implementadas en las siguientes funciones y procedimientos.

pila CREAR (int tamanoMax)
 {
  pila P;
  
  P = (pila) malloc(sizeof(tipoPila));
  if (P == NULL)
     error("No hay memoria suficiente");  
  P->Lmax = tamanoMax;
  P->tope = -1;
  P->elementos = (tElemento *) malloc(tamanoMax, sizeof(tElemento));
  if (P->elementos == NULL) 
     error("No hay memoria suficiente.");
  return P;
 }

void DESTRUIR (pila *P)
 {
  free((*P)->elementos);
  free(*P);
  *P = NULL;
 }

int VACIA (pila P)
 {
  return(P->tope == -1);
 }

tElemento TOPE (pila P)
 {
  if (VACIA(P)) {
     error("No hay elementos en la pila.");
  return(P->elementos[P->tope]);
 }

void POP (pila P)
 {
  if (VACIA(P)) {
     error("No hay elementos en la pila.");
  P->tope--;
 }

void PUSH (tElemento x, pila P) 
 {
  if (P->tope==P->Lmax-1) {
     error("Pila llena");
  p->tope++;
  p->elementos[p->tope] = x;
 }

Como puede observar el lector, esta implementación es justamente la realizada sobre las listas mediante vectores pero simplificada de una forma considerable.

IMPLEMENTACIÓN DE LAS PILAS MEDIANTE CELDAS ENLAZADAS.

La representación por celdas enlazadas de una pila es facil, porque PUSH y POP operan sólamente sobre la celda de cabecera. De hecho, las cabeceras pueden ser punteros mejor que celdas completas, ya que no hay noción de posición para las pilas y por tanto no necesitamos representar la posición 1 en una forma análoga a otras posiciones tal y como muestra figura.

Obviamente, el que las funciones sobre pilas sean más especificas que sobre listas implica que en general se simplificará la implementación (que responde a la estructura de la figura anterior).

FUNCIÓN DE ABSTRACCIÓN.

Dado el objeto del tipo rep p, el objeto abstracto que representa es:
<(*p)->elemento, (*p)->siguiente->elemento, ... , (*p)->siguiente-> ⁽ⁿ⁾ ->siguiente->elemento>. con (*p)->siguiente-> ⁽ⁿ⁺¹⁾ ->siguiente = NULL.

INVARIANTE DE LA REPRESENTACIÓN.

Dado un objeto del tipo rep p, debe cumplir:

• p tiene valores obtenidos de llamadas (tiponodo **) malloc(sizeof(tiponodo *));
  
• Los campos siguiente de los nodos tienen direcciones válidas, obtenidas de llamadas a (tiponodo *) malloc(sizeof(tiponodo)). Sólo es NULL el último.
  

 typedef struct pnodo {
  tElemento elemento;
  struct pnodo *siguiente;
 } tipopnodo;

 typedef tipopnodo **pila;

pila CREAR ()
    
    

 {
  pila P;

  P = (tipopnodo **) malloc(sizeof(tipopnodo *));
  if (P == NULL) {
     error("Memoria insuficiente.");
  *P = NULL;
  return P;
 }

void DESTRUIR (pila P)
    
    

 {
  while (!VACIA(P))
    POP(P);
  free(P);
 }

tElemento TOPE (pila P)
    
    

 {
  if (VACIA(P)) 
     error("No existe tope.");
  return((*P)->elemento);
 }

void POP (pila P)
    
    

 {
  tipopnodo *q;
  
  if (VACIA(P)) 
     error("No existe tope.");
  q = (*P);
  (*P) = q->siguiente;
  free(q);
 }

void PUSH (tElemento x,pila P)
    
    

 {
  tipopnodo *q;

  q = (tipopnodo *) malloc(sizeof(tipopnodo));
  if (q == NULL) {
     error("No hay memoria.");
  q->elemento = x;
  q->siguiente = (*P);
  (*P) = q;
 }

int VACIA (Pila P)
    
    

 {
  return (*P == NULL);
 }

4. EJEMPLO DE APLICACIÓN.

Editor de líneas.

#: carácter de borrado
@: carácter de cancelación de línea

IDEA: procesar una línea de texto usando una pila.

• Leer un carácter
• Si el carácter no es '#' ni '@' meterlo en la pila
• Si el carácter es '#' sacar de la pila
• Si el carácter es '@' vacia la pila

El código podría ser:

editar (void) {
   pila p, q;
   char c;
   p = crear();
   while ((c = (char)getchar()) != EOF) {
	if (c == '#')
		quitar(p);
	else
		if (c == '@') {
			destruir(&p);
			p = crear();
		} else
			poner(c, p);
   };
   q = crear();
   while (!vacia(p)) {
	poner(tope(p), q);
	quitar(p);
   };
   while (!vacia(q)) {
	printf("%c", tope(q));
	quitar(q);
   };
   destruir(&q);
   destruir(&p);
}