Comprender la implementación de la cola en Python

Las estructuras de datos juegan un papel clave en el mundo de la programación. Nos ayudan a organizar nuestros datos de manera que se puedan utilizar de manera eficiente. los Cola es una de las estructuras de datos más simples disponibles.

En este artículo, aprenderemos sobre la Cola y su implementación en Python.

What is a Queue?

A Cola es una estructura de datos lineal que sigue el Primero en entrar / primero en salir (FIFO) principio. Es opuesto al Estructura de datos de pila.

Podemos comparar el cola con una vida real cola en la taquilla del cine. Veamos la ilustración de una cola de la siguiente manera.

Si observa la cola en el mostrador, la segunda persona puede ir al mostrador solo después de que la primera persona complete su trabajo. Aquí la primera persona llega al mostrador y luego la segunda persona. Entonces, aquí la gente está siguiendo el FIFO (primero en entrar / primero en salir) principio. Quien llegue primero, completará el trabajo primero. Podemos ver un tipo similar de colas en nuestro día a día.

El Cola La estructura de datos también sigue el mismo principio. Ahora ya sabes qué son las colas y su principio. Veamos las operaciones que se pueden realizar en un cola estructura de datos.

Operations in Queue

De manera similar a la pila, encontraremos dos operaciones principales en una cola estructura de datos.

poner en cola (datos)

Agrega nuevos datos a la cola al final. El lado se llama trasero.

dequeue ()

Elimina datos del principio de la cola. El lado se llama frontal o trasero.

Veamos las ilustraciones de las operaciones de la cola para una mejor comprensión. Una imagen vale más que mil palabras.

Podemos escribir algunas funciones auxiliares para obtener más información sobre la cola. No hay límite en la cantidad de funciones de ayuda que tendrá. Vamos a ceñirnos a lo más importante una vez mencionado a continuación por ahora.

posterior()

Devuelve el primer elemento del final de la cola.

frente()

Devuelve el primer elemento del inicio de la cola.

esta vacio()

Devuelve si la cola está vacía o no.

¿No es aburrido para ti? Me refiero a los temas conceptuales.

Para mi ¡Sí!

Pero no podemos hacer nada sin conocer los conceptos. Tenemos que conocerlo antes de la implementación. No se preocupe, es hora de ensuciarnos las manos con algún código.

Supongo que tienes Python instalado en su PC si no, también puede probar el compilador en línea.

Queue Implementation

La implementación de una cola no le llevará más de 15 minutos a un programador. Una vez que hayas aprendido, lo dirás. Tal vez puedas implementarlo minutos después de este tutorial.

Hay varias formas de implementar la cola en Python. Veamos diferentes implementaciones de colas paso a paso.

#1. Lista

El -- es un tipo de datos integrado en Python. Vamos a utilizar el tipo de datos de lista para implementar un cola en una clase. Lo guiaremos a través de diferentes pasos para implementar la estructura de datos de la cola desde cero sin ningún módulo. Saltemos a eso.

Step1:

Escribe una clase llamada Cola.

class Queue:
	pass

Step2:

Tiene que haber alguna variable para almacenar los datos de la cola en la clase. Vamos a nombrarlo elementos. Y es una lista, por supuesto.

class Queue:

	def __init__(self):
		self.elements = []

Step3:

Para insertar datos en la cola, necesitamos un método en la clase. El método se llama En cola como ya comentamos en la sección anterior del tutorial.

El método toma algunos datos y los agrega a la cola (elementos). Podemos usar el anexar método del tipo de datos de lista para agregar datos al final de la cola.

class Queue:

	# ...

	def enqueue(self, data):
		self.elements.append(data)
		return data

Step4:

La cola debe tener una salida. Y eso se llama quitar. Creo que ya adivinó que vamos a usar el método pop del tipo de datos de lista. Si lo adivinaste o no, aplausos!

El método pop del tipo de datos de lista elimina un elemento de la lista del índice dado. Si no proporcionamos ningún índice, borra el último elemento de la lista.

Aquí, necesitamos eliminar el primer elemento de la lista. Entonces, tenemos que pasar el índice 0 al método pop.

class Queue:

	# ...

	def dequeue(self):
		return self.elements.pop(0)

Eso es suficiente para una cola. Pero, necesitamos las funciones auxiliares para probar si las operaciones de la cola funcionan correctamente o no. Escribamos también las funciones auxiliares.

Step5:

El método posterior() se usa para obtener el último elemento de la cola. La indexación negativa en el tipo de datos de lista nos ayuda a obtener el último elemento de la cola.

class Queue:

	# ...

	def rear(self):
		return self.elements[-1]

Step6:

El método frente() se utiliza para obtener el primer elemento de la cola. Podemos obtener el primer elemento de la cola usando el índice de lista.

class Queue:

	# ...

	def front(self):
		return self.elements[0]

Step7:

El método esta vacio() se utiliza para comprobar si la cola está vacía o no. Podemos comprobar la longitud de la lista.

class Queue:

	# ...

	def is_empty(self):
		return len(self.elements) == 0

¡Uf! Completó la parte de implementación del cola estructura de datos. Necesitamos crear un objeto para el Cola clase para usar.

Vamos a hacerlo.

class Queue:

	# ...

if __name__ == '__main__':
	queue = Queue()

Ahora tenemos un Cola objeto. Probémoslo con una serie de operaciones.

Compruebe si la cola está vacía o no utilizando el esta vacio método. Debería volver Edición colaborativa.
Suma los números 1, 2, 3, 4, 5 al cola usando el En cola método.
El esta vacio el método debería regresar Falso. Revisalo.
imprimir el frontal o trasero y trasero elementos que utilizan el frontal o trasero y trasero métodos respectivamente.
Quite el elemento de la cola usando el quitar método.
Asegúrate de leer frontal o trasero elemento. Debería devolver el elemento 2.
Ahora, elimine todos los elementos de la cola.
El esta vacio el método debería regresar Edición colaborativa. Revisalo.

Creo que eso es suficiente para probar nuestra implementación de cola. Escriba el código de cada paso mencionado anteriormente para probar la cola.

¿Escribiste el código?

No, no se preocupe.

Verifique el código a continuación.

class Queue:

	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[0]

	def is_empty(self):
		return len(self.elements) == 0

if __name__ == '__main__':
	queue = Queue()

	## checking is_empty method -> True
	print(queue.is_empty())

	## adding the elements
	queue.enqueue(1)
	queue.enqueue(2)
	queue.enqueue(3)
	queue.enqueue(4)
	queue.enqueue(5)

	## again checking is_empty method -> False
	print(queue.is_empty())

	## printing the front and rear elements using front and rear methods respectively -> 1, 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing the element -> 1
	queue.dequeue()

	## checking the front and rear elements using front and rear methods respectively -> 2 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing all the elements
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()

	## checking the is_empty method for the last time -> True
	print(queue.is_empty())

Creo que ejecuta el programa anterior. Puede obtener un resultado similar al siguiente.

True
False
1 5
2 5
True

Podemos usar directamente el -- tipo de datos como cola estructura de datos. La implementación anterior de la cola le ayuda 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 un cola en un programa diferente de un proyecto simplemente creando el objeto como lo hicimos anteriormente.

Hemos implementado el cola desde cero utilizando el tipo de datos de lista. ¿Hay módulos integrados para la cola? ¡Si! tenemos implementaciones de cola incorporadas. Veámoslos.

#2. deque de colecciones

Se implementa como una cola de dos extremos. Dado que admite la adición y eliminación de elementos de ambos extremos, podemos usarlo como montón y cola. Veamos la implementación de la cola usando quitar.

Se implementa utilizando otras estructuras de datos llamadas doblemente ligado lista. Entonces, el desempeño de la inserción y eliminación de elementos es consistente. Acceder a elementos de la lista de enlaces intermedios tomó O (n) hora. Podemos usarlo como cola ya que no es necesario acceder a los elementos intermedios desde el cola.

Veamos los diferentes métodos que quitar nos ofrece.

añadir (datos) - utilizado para agregar los datos a la cola
popleft () - utilizado para eliminar el primer elemento de la cola

No existen métodos alternativos para delantero trasero, y esta vacio. Podemos imprimir toda la cola en lugar de frontal o trasero y trasero métodos. A continuación, podemos usar el len método para comprobar si el cola está vacío o no.

Hemos seguido una serie de pasos para probar el cola implementación en la anterior. Sigamos aquí también la misma serie de pasos.

from collections import deque

## creating deque object
queue = deque()

## checking whether queue is empty or not -> True
print(len(queue) == 0)

## pushing the elements
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

## again checking whether queue is empty or not -> False
print(len(queue) == 0)

## printing the queue
print(queue)

## removing the element -> 1
queue.popleft()

## printing the queue
print(queue)

## removing all the elements
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()

## checking the whether queue is empty or not for the last time -> True
print(len(queue) == 0)

Obtendrá un resultado similar al siguiente.

True
False
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
True

#3. Cola de 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 al que hemos implementado antes.

Primero, veamos los diferentes métodos de Cola clase.

poner (datos) - agrega o empuja los datos a la cola
get () - 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 queue import Queue

## creating Queue object
queue_object = Queue()

## checking whether queue is empty or not -> True
print(queue_object.empty())

## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)

## again checking whether queue is empty or not -> False
print(queue_object.empty())

## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())

## checking the queue size
print("Size", queue_object.qsize())

print(queue_object.get())
print(queue_object.get())

## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())

Verifique la salida del código anterior.

True
False
1
2
3
Size 2
4
5
True

Hay algunos otros métodos en el Cola clase. Puede explorarlos usando el dir función incorporada.

Para concluir

Espero que haya aprendido sobre la estructura de datos de la cola y su implementación. Eso es todo por la cola. Puede usar la cola en diferentes lugares donde es necesario procesar en FIFO (primero en entrar / primero en salir) orden. Utilice la cola en la resolución de problemas siempre que tenga el caso para usarla.

¿Interesado en dominar Python? Mira estos recursos de aprendizaje.

Codificación feliz 🙂 👨‍💻