Cola en Python

Al igual que la pila, la cola es una estructura de datos lineal que almacena elementos en forma de primero en entrar, primero en salir (FIFO). Con una cola, el elemento agregado menos recientemente se elimina primero. Un buen ejemplo de cola es cualquier cola de consumidores de un recurso donde se atiende primero al consumidor que llegó primero.
 

Las operaciones asociadas con la cola son: 
 

• Poner en cola: agrega un elemento a la cola. Si la cola está llena, se dice que es una condición de desbordamiento – Complejidad de tiempo: O(1)
• Dequeue: elimina un elemento de la cola. Los elementos se abren en el mismo orden en que se empujan. Si la cola está vacía, se dice que es una condición de subdesbordamiento – Complejidad de tiempo: O(1)
• Anverso: obtener el elemento frontal de la cola – Complejidad de tiempo: O (1)
• Posterior: obtenga el último elemento de la cola – Complejidad de tiempo: O (1)

Implementación

Hay varias formas de implementar una cola en Python. Este artículo cubre la implementación de la cola usando estructuras de datos y módulos de la biblioteca de Python.
La cola en Python se puede implementar de las siguientes maneras:
 

• lista
• colecciones.deque
• cola.Cola

Implementación usando lista

List es una estructura de datos incorporada de Python que se puede usar como una cola. En lugar de enqueue() y dequeue(), se utilizan las funciones append() y pop(). Sin embargo, las listas son bastante lentas para este propósito porque insertar o eliminar un elemento al principio requiere cambiar todos los demás elementos por uno, lo que requiere O(n) tiempo.
 

# Python program to 
# demonstrate queue implementation
# using list
  
# Initializing a queue
queue = []
  
# Adding elements to the queue
queue.append('a')
queue.append('b')
queue.append('c')
  
print("Initial queue")
print(queue)
  
# Removing elements from the queue
print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
  
print("\nQueue after removing elements")
print(queue)
  
# Uncommenting print(queue.pop(0))
# will raise and IndexError
# as the queue is now empty

Producción: 
 

Initial queue
['a', 'b', 'c']

Elements dequeued from queue
a
b
c

Queue after removing elements
[]

Traceback (most recent call last):
  File "/home/ef51acf025182ccd69d906e58f17b6de.py", line 25, in 
    print(queue.pop(0))
IndexError: pop from empty list

Implementación usando collections.deque

La cola en Python se puede implementar usando la clase deque del módulo de colecciones. Deque es preferible a list en los casos en los que necesitamos operaciones de adición y extracción más rápidas desde ambos extremos del contenedor, ya que deque proporciona una complejidad de tiempo O(1) para las operaciones de adición y extracción en comparación con la lista que proporciona una complejidad de tiempo O(n) . En lugar de enqueue y deque, se utilizan las funciones append() y popleft().
 

# Python program to
# demonstrate queue implementation
# using collections.dequeue
  
  
from collections import deque
  
# Initializing a queue
q = deque()
  
# Adding elements to a queue
q.append('a')
q.append('b')
q.append('c')
  
print("Initial queue")
print(q)
  
# Removing elements from a queue
print("\nElements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())
  
print("\nQueue after removing elements")
print(q)
  
# Uncommenting q.popleft()
# will raise an IndexError
# as queue is now empty

Producción: 
 

Initial queue
deque(['a', 'b', 'c'])

Elements dequeued from the queue
a
b
c

Queue after removing elements
deque([])

Traceback (most recent call last):
  File "/home/b2fa8ce438c2a9f82d6c3e5da587490f.py", line 23, in 
    q.popleft()
IndexError: pop from an empty deque

Implementación usando queue.Queue

Queue es un módulo integrado de Python que se utiliza para implementar una cola. queue.Queue(maxsize) inicializa una variable a un tamaño máximo de maxsize. Un tamaño máximo de cero ‘0’ significa una cola infinita. Esta cola sigue la regla FIFO. 
Hay varias funciones disponibles en este módulo: 
 

• maxsize : número de elementos permitidos en la cola.
• vacío() : devuelve verdadero si la cola está vacía, falso de lo contrario.
• full() : devuelve True si hay elementos de tamaño máximo en la cola. Si la cola se inicializó con maxsize=0 (el valor predeterminado), full() nunca devuelve True.
• get() : elimina y devuelve un elemento de la cola. Si la cola está vacía, espere hasta que haya un artículo disponible.
• get_nowait() : devuelve un elemento si hay uno disponible de inmediato; de lo contrario, genera QueueEmpty.
• put(elemento) – Poner un elemento en la cola. Si la cola está llena, espere hasta que haya un espacio disponible antes de agregar el artículo.
• put_nowait (elemento) : coloca un elemento en la cola sin bloquearlo. Si no hay un espacio libre disponible de inmediato, genere QueueFull.
• qsize() : devuelve la cantidad de elementos en la cola.

# Python program to
# demonstrate implementation of
# queue using queue module
  
  
from queue import Queue
  
# Initializing a queue
q = Queue(maxsize = 3)
  
# qsize() give the maxsize 
# of the Queue 
print(q.qsize()) 
  
# Adding of element to queue
q.put('a')
q.put('b')
q.put('c')
  
# Return Boolean for Full 
# Queue 
print("\nFull: ", q.full()) 
  
# Removing element from queue
print("\nElements dequeued from the queue")
print(q.get())
print(q.get())
print(q.get())
  
# Return Boolean for Empty 
# Queue 
print("\nEmpty: ", q.empty())
  
q.put(1)
print("\nEmpty: ", q.empty()) 
print("Full: ", q.full())
  
# This would result into Infinite 
# Loop as the Queue is empty. 
# print(q.get())

Producción: 
 

0

Full:  True

Elements dequeued from the queue
a
b
c

Empty:  True

Empty:  False
Full:  False