Capitulo V: Pilas

Una pila es una estructura de datos ordenados lineal de tal manera que estos se obtienen por un solo lado de la estructura. La forma de acceso a sus elementos es de tipo LIFO (del inglés Last In, First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Consecuentemente el acceso queda limitado al último elemento insertado.

Ejemplos de pilas:

• Pilas de llamadas a funciones recursivas
• Pilas de CDs
• Pilas de vajilla

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado. Adicionalmente se pueden implementar otras operaciones relacionadas.

Operaciones

Operación: Apilar (Push)

• Utilidad: agrega un elemento a la pila
• Datos de entrada: elemento e, pila p
• Datos de salida: la pila con un elemento más
• Precondición: que la pila esté creada y no esté llena
• Poscondición: la pila con un elemento adicional agregado por el top de la pila

Operación: Desapilar (Pop)

• Utilidad: eliminar el último elemento que se agregó a la pila.
• Datos de Entrada: pila (p)
• Datos de Salida: la pila con un elemento menos y el elemento que se extrae de la pila
• Precondiciones: que la pila no este vacía
• Postcondiciones: la pila con un elemento menos que fue eliminado en el tope de la pila.

Operación: Vacia

• Utilidad: verifica si la pila esta vacía o no.
• Datos de Entrada: la pila que se va a verificar
• Datos de Salida: valor booleano (trae, false)
• Precondiciones: que la pila exista
• Postcondiciones: ninguna

Operación: Llena

• Utilidad: verifica si una determinada pila está llena o no
• Datos de Entrada: la pila (p) que se va a verificar
• Datos de Salida: valor booleano (trae, false)
• Precondiciones: que la pila exista
• Postcondiciones: ninguna

Implementación en Python

class Pila: 
    top = None 

    def __init__(self): 
        self.sig = None 
        self.dato = None

    def push(self, dato): 
        nuevo = Pila() 
        nuevo.dato = dato 
        nuevo.sig = Pila.top 
        Pila.top = nuevo 

    def pop(self): 
        if self.vacia(): 
            print("No hay elementos en la pila")
        else: 
            Pila.top = Pila.top.sig 
            return Pila.top.dato

    def vacia(self): 
        if Pila.top == None: 
            return True 
        else: 
            return False 

    def imprimir(self): 
        tmp = Pila.top 
        while tmp != None: 
            if tmp.sig != None:
                print (tmp.dato)
            else:
                print (tmp.dato)
            tmp = tmp.sig
`

Ejercicio:

• Crear una pila que contenga las operaciones que se realizarían en la siguiente expresión aritmética de acuerdo al orden de prescedencia de los operadores:

2 + 8 x 3 - 20 + 22/11 + (7 - 5) x 4