Tarea I Unidad II

Pilas 

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 de lista 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:

Pila de datos abstractos

A modo de resumen tipo de datos, la pila 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 primera placa 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 son ilustrados 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. 

Operaciones

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

- Crear: se crea la pila vacía. (constructor)

- Tamaño: regresa el número de elementos de la pila. (size)

- Apilar: se añade un elemento a la pila.(push)

- Desapilar: se elimina el elemento frontal de la pila.(pop)

- Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)

- Vacía: devuelve cierto si la pila está vacía o falso en caso contrario (empty)

Push

Definición:

Push es simplemente el método por el cual va agregando un Dato nuevo a la Pila tomando en cuenta la Capacidad Máxima (Max) de almacenar un dato.

Algoritmo:

Push(Pila, Top, Max, Elemento) Si Top ≠ Max

Top ←- Top + 1

Pila[Top] ←- Elemento

Si no:

Imprimir “Pila Llena”

Salir

Diagrama:

Pop

Definición:

Pop es simplemente el método por el cual va sacando el ultimo Dato de la Pila, basándose únicamente en el Top.

Detalle:

Compara para determinar si la pila esta vacío, de otra forma lo que hace es Imprimir el  valor  de Pila[Top] (Que es el dato que esta apunto de Eliminar) y enseguida a Top le resta 1, de esta forma el dato ya no existe.

Algoritmo: 

Top ←- Top - 1

Si no:

Imprimir “Pila Vacía”

Salir

Diagrama: