Comprender la implementación de colas en Python

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 🙂 👨‍💻