Alternativo

Solo disponible en BuenasTareas
  • Páginas : 12 (2985 palabras )
  • Descarga(s) : 0
  • Publicado : 23 de enero de 2011
Leer documento completo
Vista previa del texto
1-. Pila.
Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop", respectivamente "empujar" y "tirar". Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Estas características implican un comportamiento delista LIFO (Last In First Out), el último en entrar es el primero en salir.
El símil del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo.
El nodo típico para construir pilas es el mismo que vimos en el capítulo anterior para la construcción de listas:
struct nodo {
int dato;struct nodo *siguiente;
};
Las pilas suelen emplearse en los siguientes contextos:
• Evaluación de expresiones en notación postfija (notación polaca inversa).
• Reconocedores sintácticos de lenguajes independientes del contexto
• Implementación de recursividad.
2-. Declaraciones.
Los tipos que definiremos normalmente para manejar pilas serán casi los mismos que para manejarlistas, tan sólo cambiaremos algunos nombres:
typedef struct _nodo {
int dato;
struct _nodo *siguiente;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;
tipoNodo es el tipo para declarar nodos, evidentemente.
pNodo es el tipo para declarar punteros a un nodo.
Pila es el tipo para declarar pilas.
3-. Tipos de pilas.
Tipo abstracto:
A modo de resumen tipo de datos, lapila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). 'Push' añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primeraplaca es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas. A medida que la placa superior se elimina de la pila, la segunda placa se convierte en la parte superior de la pila. Dos principios importantes sonilustrados por esta metáfora: En primer lugar la última salida es un principio, la segunda es que el contenido de la pila está oculto. Sólo la placa de la parte superior es visible, por lo que para ver lo que hay en la tercera placa, el primer y segundo platos tendrán que ser retirados.

4-. Operaciones.

Las pilas tienen un conjunto de operaciones muy limitado, sólo permiten las operaciones de"push" y "pop":
• Push: Añadir un elemento al final de la pila.
• Pop: Leer y eliminar un elemento del final de la pila.

Push, insertar elemento

Las operaciones con pilas son muy simples, no hay casos especiales, salvo que la pila esté vacía.

Push en una pila vacía

Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero a lapila valdrá NULL:
[pic]
Push en vacía

El proceso es muy simple, bastará con que:
1. nodo->siguiente apunte a NULL.
2. Pilaa apunte a nodo.

Push en una pila no vacía

[pic]
Push en pila no vacía

Podemos considerar el caso anterior como un caso particular de éste, la única diferencia es que podemos y debemos trabajar con una pila vacía como con una pila normal.
De nuevopartiremos de un nodo a insertar, con un puntero que apunte a él, y de una pila, en este caso no vacía:
[pic]
Resultado

El proceso sigue siendo muy sencillo:
1. Hacemos que nodo->siguiente apunte a Pila.
2. Hacemos que Pila apunte a nodo.

Pop, leer y eliminar un elemento

[pic]

Ahora sólo existe un caso posible, ya que sólo podemos leer desde un extremo de la pila.
Partiremos de...
tracking img