3.5. Implementación de una pila en Python

Ahora que hemos definido claramente la pila como un tipo abstracto de datos, centraremos nuestra atención en usar Python para implementar la pila. Recuerde que cuando a un tipo abstracto de datos se le da una implementación física, dicha implementación se denomina una estructura de datos.

Como hemos descrito en el Capítulo 1, en Python, como en cualquier lenguaje de programación orientado a objetos, la implementación elegida para un tipo abstracto de datos como por ejemplo una pila es la creación de una nueva clase. Las operaciones de la pila se implementarán como métodos de la clase. Además, para implementar una pila, que es una colección de elementos, tiene sentido usar el poder y la simplicidad de las colecciones primitivas suministradas por Python. Nosotros usaremos una lista.

Recuerde que la clase List en Python proporciona un mecanismo de colección ordenada y un conjunto de métodos. Por ejemplo, si tenemos la lista [2,5,3,6,7,4], sólo tenemos que decidir qué extremo de la lista se considerará el tope de la pila y cuál será la base. Una vez que se toma esa decisión, las operaciones se pueden implementar usando los métodos de listas como append y pop.

En la siguiente implementación de la pila (ActiveCode 1) se asume que el final de la lista contendrá el elemento del tope de la pila. A medida que la pila crece (cuando se producen operaciones incluir), se añadirán nuevos elementos al final de la lista. Las operaciones extraer manipularán ese mismo extremo.

class Pila: def __init__(self): self.items = [] def estaVacia(self): return self.items == [] def incluir(self, item): self.items.append(item) def extraer(self): return self.items.pop() def inspeccionar(self): return self.items[len(self.items)-1] def tamano(self): return len(self.items)

Recuerde que cuando hacemos clic en el botón Run no ocurre nada más que la definición de la clase. Debemos crear un objeto Pila y luego usarlo. El ActiveCode 2 muestra la clase Pila en acción a medida que realizamos la secuencia de operaciones de la Tabla 1. Observe que la definición de la clase Pila se importa desde el módulo pythoned.

Note

El módulo pythoned contiene las implementaciones de todas las estructuras de datos discutidas en este libro. Está estructurado de acuerdo con las secciones: básicas, árboles y grafos. El módulo se puede descargar de pypi.org.

from pythoned.basicas.pila import Pila p=Pila() print(p.estaVacia()) p.incluir(4) p.incluir('perro') print(p.inspeccionar()) p.incluir(True) print(p.tamano()) print(p.estaVacia()) p.incluir(8.4) print(p.extraer()) print(p.extraer()) print(p.tamano())

Es importante tener en cuenta que podríamos haber elegido implementar la pila usando una lista donde el tope esté al principio en lugar de estar al final. En este caso, los métodos pop y append anteriores ya no funcionarían y tendríamos que indizar la posición 0 (el primer ítem de la lista) explícitamente usando pop e insert. La implementación se muestra en CodeLens 1.

Activity: CodeLens Implementación alternativa de la clase Pila (stack_cl_1)

Esta capacidad de cambiar la implementación física de un tipo abstracto de datos mientras se mantienen las características lógicas es un ejemplo de abstracción en funcionamiento. Sin embargo, aunque la pila funcionará en todo caso, si consideramos el desempeño de las dos implementaciones, definitivamente hay una diferencia. Recuerde que las operaciones append y pop() resultaron ser O(1). Esto significa que la primera implementación realizará las operaciones incluir y extraer en tiempo constante sin importar cuántos ítems están en la pila. El desempeño de la segunda implementación sufre en que las operaciones insert(0) y pop(0) requerirán un tiempo O(n) para una pila de tamaño n. Evidentemente, aunque las implementaciones son lógicamente equivalentes, tendrían tiempos muy diferentes al realizar las pruebas de referencia (benchmark).

Autoevaluación

Q-4: Dada la siguiente secuencia de operaciones de pila, ¿cuál es el ítem en el tope de la pila cuando se completa la secuencia?

m = Pila()
m.incluir('x')
m.incluir('y')
m.extraer()
m.incluir('z')
m.inspeccionar()

• 'x'
• Recuerde que una pila se construye de abajo hacia arriba.
• 'y'
• Recuerde que una pila se construye de abajo hacia arriba.
• 'z'
• ¡Bien hecho!
• La pila está vacía
• Recuerde que una pila se construye de abajo hacia arriba.

Q-5: Dada la siguiente secuencia de operaciones de pila, ¿cuál es el ítem en el tope de la pila cuando se completa la secuencia?

m = Pila()
m.incluir('x')
m.incluir('y')
m.incluir('z')
while not m.estaVacia():
   m.extraer()
   m.extraer()

• 'x'
• Quizás usted desee comprobar la documentación para estaVacia
• la pila está vacía
• Hay un número impar de cosas en la pila, pero cada vez a través del ciclo se extraen 2 cosas
• ocurrirá un error
• ¡Bien hecho!
• 'z'
• Quizás usted desee comprobar la documentación para estaVacia

Escriba una función cadenaInversa(miCadena) que utilice una pila para invertir los caracteres de una cadena.

from test import testEqual class Pila: def __init__(self): self.items = [] def estaVacia(self): return self.items == [] def incluir(self, item): self.items.append(item) def extraer(self): return self.items.pop() def inspeccionar(self): return self.items[len(self.items)-1] def tamano(self): return len(self.items) def cadenaInversa(miCadena): # Escriba aquí su código testEqual(cadenaInversa('casa'),'asac') testEqual(cadenaInversa('x'),'x') testEqual(cadenaInversa('1234567890'),'0987654321')

You have attempted of activities on this page