Además de las estructuras de datos que nos ofrece Python, nosotros también podemos crear nuestras propias estructuras.
Por ejemplo, podemos crear una estructura que nos permita hacer tres cosas simples:
Si a esa estructura la llamamos Pila, podría tener una estructura similar a la siguiente:
class Pila(object):
def apilar(self, elemento):
"""Guarda el elemento a insertar al final de la pila"""
...
def desapilar(self):
"""Quita y retorna eltimo elemento insertado en la pila"""
...
def esta_vacia(self):
"""Devuelve True si la pila no contiene elementos y
False en el caso de que tenga al menos un elemento"""
...
Y si suponemos que la guardamos en un archivo llamado pcl.py podríamos usarla de la siguiente forma:
In [1]:
from pcl import Pila
# Creo la pila
p = Pila()
print 'La pila vacía se ve como:', p
# Le agrego elementos
p.apilar(5)
print 'Luego de agregar el 5, la pila se ve como:', p
p.apilar(7)
print 'Luego de agregar el 7, la pila se ve como:', p
p.apilar(9)
print 'Luego de agregar el 9, la pila se ve como:', p
print 'Despues de agregar los elementos 5, 7 y 9 me queda la pila con los elementos ', p
ultimo = p.desapilar()
print 'Saco el elemento {elemento} y me queda {pila}'.format(elemento=ultimo, pila=p)
ultimo = p.desapilar()
print 'Saco el elemento {elemento} y me queda {pila}'.format(elemento=ultimo, pila=p)
print '¿La lista esta vacía?: {esta_vacia}'.format(esta_vacia=p.esta_vacia())
ultimo = p.desapilar()
print 'Saco el elemento {elemento} y me queda {pila}'.format(elemento=ultimo, pila=p)
print '¿Esta vacía?: {esta_vacia}'.format(esta_vacia=p.esta_vacia())
También podemos crear una estructura que nos permita hacer tres cosas simples:
Si a esa estructura la llamamos Cola, podría tener una estructura similar a la siguiente:
class Cola(object):
def encolar(self, elemento):
"""Guarda el elemento a insertar al final de la cola"""
...
def desencolar(self):
"""Quita y retorna el primer elemento insertado"""
...
def esta_vacia(self):
"""Devuelve True si la cola no contiene elementos y
False en el caso de que tenga al menos un elemento"""
...
In [2]:
from pcl import Cola
c = Cola()
# Agrego elementos
c.encolar(5)
print 'Despues de agregar el 5 tengo: ', c
c.encolar(7)
print 'Despues de agregar el 7 tengo: ', c
c.encolar(9)
print 'Despues de agregar los elementos 5, 7 y 9 tengo: ', c
primero = c.desencolar()
print 'Saco el elemento {elemento} y me queda {cola}'.format(elemento=primero, cola=c)
primero = c.desencolar()
print 'Saco el elemento {elemento} y me queda {cola}'.format(elemento=primero, cola=c)
print '¿La lista esta vacía?: {esta_vacia}'.format(esta_vacia=c.esta_vacia())
primero = c.desencolar()
print 'Saco el elemento {elemento} y me queda {cola}'.format(elemento=primero, cola=c)
print '¿Esta vacía?: {esta_vacia}'.format(esta_vacia=c.esta_vacia())
Y así como creamos estas dos estructuras, también podemos crear una nueva estructura que nos permita:
Si a esa estructura la llamamos Lista, podría tener una estructura similar a la siguiente:
class Lista(object):
def obtener_elemento(self):
"""Retorna el elemento de la posición actual"""
...
def insertar_siguiente(self, elemento):
"""Guarda el elemento a insertar en la posición siguiente a la actual"""
...
def eliminar(self, posicion):
"""Elimina el elemento de la posición indicada"""
...
def ir_al_primero(self):
"""Posiciona el cursor apuntando al primer elemento de la lista"""
...
def siguiente(self):
"""Avanza el cursor al siguiente elemento de la lista"""
...
def esta_vacia(self):
"""Devuelve True si la cola no contiene elementos y
False en el caso de que tenga al menos un elemento"""
...
Y un ejemplo de uso podría ser:
In [3]:
from pcl import Lista
l = Lista()
print l
l.insertar_siguiente(5)
print l
l.insertar_siguiente(15)
print l
l.insertar_siguiente(25)
print l
l.ir_al_primero()
print l.obtener_elemento()
l.siguiente()
print l.obtener_elemento()
l.insertar_siguiente(20)
print l
l.eliminar(2)
print l
l.eliminar(2)
print l
l.eliminar(2)
print l
l.eliminar(1)
print l
Haciendo uso de que en Python se puede considerar a las variables como etiquetas en lugar de cajas:
| Ejemplo | Cajas | Etiquetas |
|---|---|---|
| Si a la variable a le asignamos el número 1 | Guardamos el valor 1 en la caja a |
Hacemos que la referencia a apunte al valor 1 |
| Y cuando a esa variable queremos asignarle el número dos | Pisamos el valor de a y guardamos el valor 2 |
Nuestra referencia deja de apuntar a donde lo hacía antes y ahora apunta a una nueva posición de memoria quedando el número 1 sin ser apuntado por nadie |
| Y al decir que la variable a es igual a la variable b lo que sucede es que se copia el contenido de a en b | En este caso se crea una nueva caja con el valor 2 |
Al copiar el contenido, lo que se copia es la referencia |
Podemos armar una estructura que nos permita guardar un valor y, a su vez, apuntar a otra posición de la memoria que también tenga una variable del mismo tipo:
class Nodo(object):
def __init__(self, valor, siguiente=None):
self.siguiente = siguiente
self.valor = valor
In [4]:
class Nodo(object):
def __init__(self, valor, siguiente=None):
self.siguiente = siguiente
self.valor = valor
n1 = Nodo(5)
n2 = Nodo(15)
n1.siguiente = n2
print 'El valor del nodo 1 es {0}'.format(n1.valor)
print 'El nodo 1 se encuentra en la posición {0}'.format(id(n1))
print 'El siguiente del nodo 1 es {0}'.format(id(n1.siguiente))
print
print 'El valor del nodo 2 es {0}'.format(n2.valor)
print 'El nodo 2 se encuentra en la posición {0}'.format(id(n2))
print
print 'El valor del nodo 2 es {0}'.format(n1.siguiente.valor)
Teniendo en cuenta esto, podríamos armar una cadena de 4 números de la siguiente forma:
In [5]:
cadena = Nodo(9, Nodo(13, Nodo(14, Nodo(16))))
print cadena.valor # 9
print cadena.siguiente.valor # 13
print cadena.siguiente.siguiente.valor # 14
print cadena.siguiente.siguiente.siguiente.valor # 16
Si bien parece una estructura simple, cuando se la quiere usar no suele ser tan práctica, por lo que se suelen armar estructuras a partir de ella.
Las pilas, también conocidas como estructuras LIFO (Last In, First Out), nos permiten guardar una gran cantidad de elementos, pero obtener siempre el ultimo elemento guardado.
class Pila(object):
def __init__(self):
self.primero = None
self.tamanio = 0
def __str__(self):
pila = '<Pila: '
siguiente = self.primero
while siguiente:
pila += '{} | '.format(siguiente.valor)
siguiente = siguiente.siguiente
pila +='>'
return pila
def apilar(self, elemento):
"""Guarda el elemento a insertar al final de la pila"""
nodo = Nodo(elemento, self.primero)
self.primero = nodo
self.tamanio += 1
def desapilar(self):
"""Quita y retorna último elemento insertado en la pila"""
nodo = self.primero
try:
elemento = nodo.valor
except AttributeError:
raise Exception(u'No se puede desapilar elementos de una pila vacía')
self.primero = nodo.siguiente
self.tamanio -= 1
return elemento
def esta_vacia(self):
"""Devuelve True si la pila no contiene elementos y
False en el caso de que tenga al menos un elemento"""
return not self.tamanio
Entonces, cuando nosotros creemos una pila simplemente haciendo:
p = Pila()
Lo que podríamos ver en la memoria es:
Al agregarle el número 5 a esa pila nos queda:
p.apilar(5)
Y al agregar el número 7 nos queda:
p.apilar(7)
Y al agregar el número 9 nos queda:
p.apilar(9)
Y luego comenzamos a quitar elementos de la pila
ultimo = p.desapilar() # 9
ultimo = p.desapilar() # 7
Teniendo en cuenta que una vez que desapilamos el 7 y la variable llamada último pasa a apuntar al nodo recientemente desapilado, el nodo anterior no queda referenciado por nadie,por lo que el mismo python se encargará de liberar esa memoria donde se guardaba el número 9.
ultimo = p.desapilar() # 5
Las colas, también conocidas como estructuras FIFO (First In, First Out), nos permiten guardar una gran cantidad de elementos y después ir quitandolos en el mismo orden en que los ingresamos.
class Cola(object):
def __init__(self):
self.primero = None
self.ultimo = None
self.tamanio = 0
def __str__(self):
cola = '<Cola: | '
siguiente = self.primero
while siguiente:
cola += '{} | '.format(siguiente.valor)
siguiente = siguiente.siguiente
cola +='>'
return cola
def encolar(self, elemento):
"""Guarda el elemento a insertar al final de la cola"""
nodo = Nodo(elemento)
self.tamanio += 1
if not self.primero:
self.primero = nodo
else:
self.ultimo.siguiente = nodo
self.ultimo = nodo
def desencolar(self):
"""Quita y retorna el primer elemento insertado"""
nodo = self.primero
try:
elemento = nodo.valor
except AttributeError:
raise Exception(u'No se puede desencolar más elementos')
self.primero = nodo.siguiente
self.tamanio -= 1
return elemento
def esta_vacia(self):
"""Devuelve True si la cola no contiene elementos y
False en el caso de que tenga al menos un elemento"""
return not self.tamanio
Entonces, cuando nosotros creemos una cola simplemente haciendo:
c = Cola()
Lo que podríamos ver en la memoria es:
Al agregarle el número 5 a esa pila nos queda:
c.encolar(5)
Como tenemos un único elemento, tanto primero como último apuntan al mismo nodo. Y al agregar el número 7 nos queda:
c.encolar(7)
c.encolar(9)
Y luego comenzamos a quitar elementos de la cola:
primero = c.desencolar() # 5
En este caso vemos que se modifica la referencia al primero, pero no al último.
primero = c.desencolar() # 7
primero = c.desencolar() # 9
A diferencia de las estructuras anteriores, las listas soportan agregar, obtener y eliminar elementos de cualquier posición.
class Lista(object):
def __init__(self):
self.primero = None
self.cursor = None
self.tamanio = 0
def __str__(self):
lista = '<Lista: '
siguiente = self.primero
while siguiente:
lista += '{} | '.format(siguiente.valor)
siguiente = siguiente.siguiente
lista +='>'
return lista
def obtener_elemento(self):
"""Retorna el elemento de la posición actual"""
try:
return self.cursor.valor
except AttributeError:
raise Exception(u'La lista se encuentra vacía')
def insertar_siguiente(self, elemento):
"""Guarda el elemento a insertar en la posición actual"""
nodo = Nodo(elemento)
if not self.primero:
self.primero = nodo
else:
nodo.siguiente = self.cursor.siguiente
self.cursor.siguiente = nodo
self.cursor = nodo
self.tamanio += 1
def eliminar(self, posicion):
"""Elimina el elemento de la posición indicada"""
if posicion > self.tamanio:
msg = u'Se quiere borrar la posición {0} y la lista sólo tiene' \
u' {1} elementos'
raise Exception(msg.format(posicion, self.tamanio))
elif posicion == 1:
nodo = self.primero
self.primero = self.primero.siguiente
else:
nodo_anterior = self.primero
pos_nodo = 2
while pos_nodo < posicion:
nodo_anterior = nodo_anterior.siguiente
pos_nodo += 1
nodo = nodo_anterior.siguiente
if self.cursor == nodo_anterior.siguiente:
self.cursor = nodo_anterior.siguiente.siguiente
if nodo_anterior.siguiente:
nodo_anterior.siguiente = nodo_anterior.siguiente.siguiente
self.tamanio -= 1
return nodo
def ir_al_primero(self):
"""Posiciona el cursor apuntando al primer elemento de la lista"""
self.cursor = self.primero
def siguiente(self):
"""Avanza el cursor al siguiente elemento de la lista"""
try:
self.cursor = self.cursor.siguiente
except AttributeError:
msg = u'Error: La lista tiene {0.tamanio} elementos y quiere ' \
u'acceder a la posición {1}'
pos = self.tamanio + 1
raise IndexError(msg.format(self, pos))
def esta_vacia(self):
"""Devuelve True si la cola no contiene elementos y
False en el caso de que tenga al menos un elemento"""
return not self.tamanio
Si creamos una lista vacía:
l = Lista()
La podríamos ver en la memoria como:
Entonces, al insertar un elemento vemos que las referencias de primero y cursor apuntan al mismo elemento:
l.insertar_siguiente(5)
Cuando insertamos un segundo elemento, lo que hace es agregarlo y apuntar el cursor a la posición del nuevo elemento:
l.insertar_siguiente(15)
Lo mismo pasa al ingrear ahora el número 25:
l.insertar_siguiente(25)
Si luego invocamos al método ir_al_primero el cursor pasa a apuntar el primer elemento y al imprimir el resultado de obtener_elemento se mostrará el número 5, sin quitarlo de la lista.
l.ir_al_primero()
print l.obtener_elemento()
Al invocar al método llamado siguiente avanzará el cursor a la siguiente posición. El print en este caso imprimirá el número 15.
l.siguiente()
print l.obtener_elemento()
Si luego, parados en esa posición, insertamos el número 20, lo que va a pasar es que la referencia a siguiente del nodo que contiene el número 15 pasa a apuntar el nuevo número 20. Y este nuevo nodo tiene que apuntar al nodo que contiene el número 25.
l.insertar_siguiente(20)
Si luego eliminamos el número de la posición 2, tenemos que reasignar la referencia del nodo que tiene el número 5 al nodo que tiene el número 20. A su vez,como el cursor apunta a esa posición, también tenemos que apuntarlo a la siguiente posición.
l.eliminar(2)
l.eliminar(2)
l.eliminar(2)
l.eliminar(1)