3.17. Implementación de una cola doble en Python¶
Como hemos hecho en las secciones anteriores, crearemos una nueva clase para la implementación del tipo abstracto de datos Cola Doble. Una vez más, las listas de Python proporcionan un muy buen conjunto de métodos sobre los cuales se pueden construir los detalles de la cola doble. Nuestra implementación (el Programa 1) asumirá que el final de la cola doble está en la posición 0 de la lista.
Programa 1
1class ColaDoble:
2 def __init__(self):
3 self.items = []
4
5 def estaVacia(self):
6 return self.items == []
7
8 def agregarFrente(self, item):
9 self.items.append(item)
10
11 def agregarFinal(self, item):
12 self.items.insert(0,item)
13
14 def removerFrente(self):
15 return self.items.pop()
16
17 def removerFinal(self):
18 return self.items.pop(0)
19
20 def tamano(self):
21 return len(self.items)
En removerFrente utilizamos el método pop para eliminar el último elemento de la lista. Sin embargo, en removerFinal, el método pop(0) debe eliminar el primer elemento de la lista. Del mismo modo, necesitamos usar el método insert (línea 12) en agregarFinal, ya que el método append asume la adición de un nuevo ítem al final de la lista.
El CodeLens 1 muestra la clase ColaDoble en acción a medida que realizamos la secuencia de operaciones de la Tabla 1.
Activity: CodeLens Ejemplo de operaciones sobre colas dobles (deqtest)
Pueden verse muchas similitudes con el código de Python ya descrito para pilas y colas. También es probable que usted observe que, en esta implementación, agregar y remover ítems desde el frente es O(1) mientras que agregar y remover del final es O(n). Esto es esperable dadas las operaciones comunes que aparecen para agregar y remover ítems. Una vez más, lo importante es estar seguros de que sabemos dónde se asignan el frente y el final en la implementación.