Las estructuras de datos desempeñan un papel fundamental en el mundo de la programación. Nos ayudan a organizar nuestros datos de forma que puedan utilizarse de manera eficiente. La Cola es una de las estructuras de datos más simples que existen
En este artículo, aprenderemos sobre la Cola y su implementación en Python
¿Qué es una Cola?
Una Cola es una estructura de datos lineal que sigue el principio FIFO (Primero en entrar/Primero en salir ). Es opuesta a la estructura de datos Pila
Podemos comparar la cola con una cola de la vida real en la taquilla del cine. Veamos la siguiente ilustración de una cola
Si observa la cola en el mostrador, la segunda persona puede ir al mostrador sólo después de que la primera persona termine su trabajo. Aquí la primera persona acude al mostrador y después la segunda. Por lo tanto, aquí la gente sigue el principio FIFO (primera entrada/primera salida) . Quien llegue primero, completará primero el trabajo. Podemos ver un tipo similar de colas en nuestra vida cotidiana
La estructura de datos Cola también sigue el mismo principio. Ahora ya sabe lo que son las colas y su principio. Veamos las operaciones que se pueden realizar en una estructura de datos de colas
Operaciones en cola
De forma similar a la pila, encontraremos dos operaciones principales en una estructura de datos de cola
enqueue(datos)
Añade nuevos datos a la cola al final. El lado se denomina posterior
dequeue()
Elimina datos de la parte delantera de la cola. El lado se denomina frontal
Veamos las ilustraciones de las operaciones de la cola para una mejor comprensión. Una imagen dice más que mil palabras
Podemos escribir algunas funciones auxiliares para obtener más información sobre la cola. No hay límite en cuanto al número de funciones auxiliares. Limitémonos por ahora a las más importantes, una vez mencionadas a continuación
cola()
Devuelve el primer elemento desde el final de la cola
delante()
Devuelve el primer elemento desde el principio de la cola
está_vacío()
Devuelve si la cola está vacía o no
¿No le resulta aburrido? Me refiero a los temas conceptuales
Para mí sí
Pero, no podemos hacer nada sin conocer los conceptos. Tenemos que terminar de conocerlo antes de la implementación. No se preocupe es hora de ensuciarnos las manos con algo de código
Asumo que tiene python instalado en su PC si no también puede probar el compilador en línea
Implementación de colas
Implementar una cola no le llevará más de 15 minutos a un programador. Una vez que lo haya aprendido, lo dirá. Tal vez pueda implementarla en pocos minutos después de este tutorial
Hay múltiples formas de implementar la cola en Python. Veamos diferentes implementaciones de colas paso a paso
#1. Lista
La lista es un tipo de datos incorporado en Python. Vamos a utilizar el tipo de datos lista para implementar una cola en una clase. Le guiaremos a través de diferentes pasos para implementar la estructura de datos de cola desde cero sin ningún módulo. Pongámonos manos a la obra
Paso1
Escriba una clase llamada Cola
clase Cola
:
pasar
Paso2
Tiene que haber alguna variable para almacenar los datos de la cola en la clase. Llamémosla elementos. Y es una lista, por supuesto
clase Cola:
def __init__(self):
self.elementos = []
Paso3
Para insertar datos en la cola, necesitamos un método en la clase. El método se llama poner en cola como ya comentamos en la sección anterior del tutorial
El método toma algunos datos y los añade a la cola (elementos). Podemos utilizar el método añadir del tipo de datos lista para añadir datos al final de la cola
class Cola:
# ...
def enqueue(self, datos):
self.elementos.append(datos)
return datos
Paso 4
La cola necesita tener una salida. Y eso se llama dequeue. Creo que ya ha adivinado que vamos a utilizar el método pop del tipo de datos lista. Si lo ha adivinado o no, ¡salud!
El método pop del tipo de datos lista borra un elemento de la lista del índice dado. Si no hemos dado ningún índice, entonces borra el último elemento de la lista
Aquí, necesitamos borrar el primer elemento de la lista. Por lo tanto, tenemos que pasar el índice 0 al método pop
class Cola:
# ...
def dequeue(self):
return self.elements.pop(0)
Esto es suficiente para una cola. Pero, necesitamos las funciones ayudantes para comprobar si las operaciones de la cola funcionan correctamente o no. Escribimos también las funciones ayudantes
Paso 5
El método atrás() se utiliza para obtener el último elemento de la cola. La indexación negativa en el tipo de datos lista nos ayuda a obtener el último elemento de la cola
class Cola:
# ...
def rear(self):
return self.elementos[-1]
Paso6
El método frontal() se utiliza para obtener el primer elemento de la cola. Podemos obtener el primer elemento de la cola utilizando el índice de la lista
class Cola:
# ...
def front(self):
return self.
elementos
<x>[0]</x>
Paso 7
El método is_empty() se utiliza para comprobar si la cola está vacía o no. Podemos comprobar la longitud de la lista
class Cola:
# ...
def is_empty(self):
return len(self.elementos) == 0
Uf! hemos completado la parte de implementación de la estructura de datos de la cola . Necesitamos crear un objeto para que la clase Cola lo use
Hagámoslo
class Cola:
# ...
if __name__ == '__main__':
queue = Cola()
Ahora, tenemos un objeto Cola . Vamos a probarlo con una serie de operaciones
- Compruebe si la cola está vacía o no utilizando el método is_empty . Debería devolver Verdadero.
- Añada los números 1, 2, 3, 4, 5 a la cola utilizando el método poner en cola .
- El método is_empty debería devolver Falso. Compruébelo.
- Imprima los elementos anterior y posterior utilizando los métodos anterior y posterior respectivamente.
- Retire el elemento de la cola utilizando el método dequeue .
- Compruebe el elemento delantero . Debería devolver el elemento 2.
- Ahora, elimine todos los elementos de la cola.
- El método is_empty debería devolver Verdadero. Compruébelo.
Creo que es suficiente para probar nuestra implementación de la cola. Escriba el código de cada paso mencionado anteriormente para probar la cola
¿Ha escrito el código?
No, no se preocupe
Compruebe el código a continuación
class Cola:
def __init__(self):
self.elements = []
def enqueue(self, data):
self.elements.append(data)
return data
def dequeue(self):
return self.elements.pop(0)
def rear(self):
return self.elements[-1]
def front(self):
return self.elements<x>[0]</x>
def is_empty(self):
return len(self.elementos) == 0
if __name__ == '__main__':
queue = Queue()
## comprobando el método is_empty -> True
print(queue.is_empty())
## añadiendo los elementos
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
## comprobando de nuevo el método is_empty -> False
print(queue.is_empty())
## imprimiendo los elementos anterior y posterior usando los métodos anterior y posterior respectivamente -> 1, 5
print(queue.front(), end=' ')
print(queue.rear())
## eliminando el elemento -> 1
queue.dequeue()
## comprobando los elementos anterior y posterior usando los métodos anterior y posterior respectivamente -> 2 5
print(queue.front(), end=' ')
print(queue.rear())
## eliminando todos los elementos
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()
## comprobando el método is_empty por última vez -> True
print(queue.is_empty())
Ejecute el programa anterior. Puede obtener una salida similar al siguiente resultado
Verdadero
Falso
1
5
2
5
Verdadero
Podemos utilizar directamente el tipo de datos lista como estructura de datos de cola . La implementación anterior de la cola le ayudará a comprender mejor la implementación de la cola en otros lenguajes de programación
También puede utilizar la implementación de clase anterior de una cola en un programa diferente de un proyecto simplemente creando el objeto como hacemos antes
Hemos implementado la cola desde cero utilizando el tipo de datos lista. ¿Existen módulos incorporados para la cola? Sí, tenemos implementaciones de cola incorporadas. Veámoslas
#2. deque de colecciones
Se implementa como una cola de doble extremo. Dado que admite la adición y eliminación de elementos desde ambos extremos, podemos utilizarla como pila y cola. Veamos la implementación de la cola utilizando dequeue
Se implementa utilizando otras estructuras de datos denominadas lista doblemente enlazada. Así, el rendimiento de la inserción y eliminación de elementos es coherente. Acceder a los elementos de la lista doblemente enlazada requiere un tiempo O(n) . Podemos utilizarla como una cola , ya que no es necesario acceder a los elementos del medio desde la cola
Comprobemos los distintos métodos que nos ofrece la dequeue
- append(datos ) - se utiliza para añadir los datos a la cola
- popleft() - se utiliza para eliminar el primer elemento de la cola
No hay métodos alternativos para la parte delantera, trasera e is_empty. Podemos imprimir toda la cola en lugar de los métodos frente y trasera . A continuación, podemos utilizar el método len para comprobar si la cola está vacía o no
Hemos seguido una serie de pasos para probar la implementación de la cola en lo anterior. Sigamos también aquí la misma serie de pasos
from collections import deque
## crear objeto deque
queue = deque()
## comprobar si la cola está vacía o no -> True
print(len(queue) == 0)
## empujar los elementos
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)
## comprobando de nuevo si la cola está vacía o no -> Falso
print(len(queue) == 0)
## imprimiendo la cola
print(queue)
## eliminando el elemento -> 1
queue.
popleft
()
## imprimir la cola
print(queue)
## eliminar
todos los elementos
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()
##
comprobar si la cola está vacía o no por última vez -> Verdadero
print(len(queue) == 0)
Obtendrá un resultado similar al siguiente
Verdadero
Falso
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
Verdadero
#3. Cola de la cola
Python tiene un módulo incorporado llamado cola que sirve a una clase llamada Cola para la implementación de la cola. Es similar a la que hemos implementado anteriormente
Primero, revisemos diferentes métodos de la clase Cola
- poner(datos) - añade o empuja los datos a la cola
- consiga () - elimina el primer elemento de la cola y lo devuelve
- vacío () - devuelve si la pila está vacía o no
- qsize () - devuelve la longitud de la cola.
Implementemos la cola con los métodos anteriores
from cola import Cola
## crear objeto cola
queue_object = Cola()
## comprobar si la cola está vacía o no -> True
print(queue_object.empty())
## añadir los elementos
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## comprobando de nuevo si la cola está vacía o no -> Falso
print(queue_object.empty())
## eliminar todos los elementos
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## comprobar el tamaño de la cola
print("Tamaño", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## comprobación
de si queue_object está vacío o no por última vez -> True
print(queue_object.empty())
Compruebe la salida del código anterior
Verdadero
Falso
1
2
3
Tamaño 2
4
5
Verdad
ero
Existen algunos otros métodos en la clase Cola . Puede explorarlos utilizando la función incorporada dir
Conclusión
Espero que haya aprendido sobre la estructura de datos de la cola y su implementación. Eso es todo para la cola. Puede utilizar la cola en diferentes lugares donde se necesite procesar en orden FIFO (primera entrada/primera salida) . Utilice la cola en la resolución de problemas siempre que se dé el caso de utilizarla.
¿Le interesa dominar Python? Eche un vistazo a estos recursos de aprendizaje
Feliz Codificación 🙂 👨💻