Pilas

Una pila es una estructura de datos de acceso restrictivo a sus elementos. Se puede entender como una pila de libros que se amontonan de abajo hacia arriba. En principio no hay libros; después ponemos uno, y otro encima de éste, y así sucesivamente. Posteriormente los solemos retirar empezando desde la cima de la pila de libros, es decir, desde el último que pusimos, y terminaríamos por retirar el primero que pusimos, posiblemente ya cubierto de polvo.

Como el último elemento insertado es el primero en recuperarse/borrarse, los desarrolladores se refieren a estas pilas como pilas LIFO (last-in, first-out).
Los datos se push (insertan) dentro y se pop (recuperan/borran) de la parte superior de la pila. La siguiente figura ilustra una pila con tres String cada uno insertado en la parte superior de la pila.

Implementación mediante array
Esta implementación es estática, es decir,...

Esta implementación es estática, es decir, da un tamaño máximo fijo a la pila, y si se sobrepasa dicho límite se produce un error. La comprobación de apilado en una pila llena o desapilado en una pila vacía no se han hecho, pero sí las funciones de comprobación, que el lector puede modificar según las necesidades de su programa.
- Declaración:
struct tpila
{
int cima;
int elementos[MAX_PILA];
};
Nota: MAX_PILA debe ser mayor o igual que 1.

- Procedimiento de Creación:
void crear(struct tpila *pila)
{
pila->cima = -1;
}

- Función que devuelve verdadero si la pila está vacía:
int vacia(struct tpila *pila)
{
return (pila->cima == -1);
}

- Función que devuelve verdadero si la pila está llena:
int llena(struct tpila *pila)
{
return (pila->cima == MAX_PILA);
}

- Procedimiento de apilado:
void apilar(struct tpila *pila, int elem)
{
pila->elementos[++pila->cima] = elem;
}

- Procedimiento de desapilado:
void desapilar(struct tpila *pila, int *elem)
{
*elem = pila->elementos[pila->cima--];
}

Programa de prueba:
#include

int main(void)
{
struct tpila pila;
int elem;

crear(&pila);
if (vacia(&pila)) printf("\nPila vacia.");
if (llena(&pila)) printf("\nPila llena.");
apilar(&pila, 1);
desapilar(&pila, &elem);
return 0;
}


[+/-]Leer más...

Implementación mediante lista enlazada
Para hacer la implementación se utiliza una lista..


Para hacer la implementación se utiliza una lista con cabecera ficticia (ver apartado de listas). Dado el carácter dinámico de esta implementación no existe una función que determine si la pila está llena. Si el usuario lo desea puede implementar un análisis del código devuelto por la función de asignación de memoria.

- Declaración:
struct tpila
{
int clave;
struct tpila *sig;
};
- Procedimiento de creación:
void crear(struct tpila **pila)
{
*pila = (struct tpila *) malloc(sizeof(struct tpila));
(*pila)->sig = NULL;
}
- Función que devuelve verdadero si la pila está vacía:
int vacia(struct tpila *pila)
{
return (pila->sig == NULL);
}

- Procedimiento de apilado (apila al comienzo de la lista):
void apilar(struct tpila *pila, int elem)
{
struct tpila *nuevo;

nuevo = (struct tpila *) malloc(sizeof(struct tpila));
nuevo->clave = elem;
nuevo->sig = pila->sig;
pila->sig = nuevo;
}
- Procedimiento de desapilado (desapila del comienzo de la lista):
void desapilar(struct tpila *pila, int *elem)
{
struct tpila *aux;

aux = pila->sig;
*elem = aux->clave;
pila->sig = aux->sig;
free(aux);
}

Programa de prueba:
int main(void)
{
struct tpila *pila;
int elem;

crear(&pila);
if (vacia(pila)) printf("\nPila vacia!");
apilar(pila, 1);
desapilar(pila, &elem);

return 0;
}

[+/-] Leer más...

Elegir entre implementación con listas o con arrays
El uso del array es idóneo cuando se conoce de antemano el número máximo


El uso del array es idóneo cuando se conoce de antemano el número máximo de elementos que van a ser apilados y el compilador admite una región contigua de memoria para el array. En otro caso sería más recomendable usar la implementación por listas enlazadas, también si el número de elementos llegase a ser excesivamente grande.
La implementación por array es ligeramente más rápida. En especial, es mucho más rápido a la hora de eliminar los elementos que hayan quedado en la pila. Por lista enlazada esto no es tan rápido. Por ejemplo, piénsese en un algoritmo que emplea una pila y que en algunos casos al terminar éste su ejecución deja algunos elementos sobre la pila. Si se implementa la pila mediante una lista enlazada entonces quedarían en memoria una serie de elementos que es necesario borrar. La única manera de borrarlos es liberar todas las posiciones de memoria que le han sido asignadas a cada elemento, esto es, desapilar todos los elementos. En el caso de una implementación con array esto no es necesario, salvo que quiera liberarse la región de memoria ocupada por éste.

El siguiente listado presenta una implementación de Stack utilizando una lista de enlace simple:
// LinkedListStack.java

package com.javajeff.cds;

public class LinkedListStack implements Stack {
private static class Node {
Object o;
Node next;
}

private Node top = null;

public boolean isEmpty () {
return top == null;
}

public Object peek () {
if (top == null)
throw new java.util.EmptyStackException ();
return top.o;
}

public void push (Object o) {
Node temp = new Node ();
temp.o = o;
temp.next = top;
top = temp;
}

public Object pop () {
if (top == null)
throw new java.util.EmptyStackException ();
Object o = top.o;
top = top.next;
return o;
}
}

[+/-] Leer más...